DataStructuresandAlgorithmAnalysisAlgorithmDesign

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Data Structures and Algorithm Analysis,Algorithm Design Techniques,Lecturer: Jing Liu,Email:,Homepage:,1,The Greedy Approach,Greedy algorithms,are usually designed to solve,optimization problems,in which a quantity is to be minimized or maximized.,Greedy algorithms typically consist of a,n iterative procedure,that tries to find a,local optimal solution,.,In some instances, these local optimal solutions translate to global optimal solutions. In others, they fail to give optimal solutions.,2,The Greedy Approach,A greedy algorithm makes a,correct guess,on the basis of little calculation without worrying about the future. Thus, it builds a solution step by step. Each step increases the size of the partial solution and is based on local optimization.,The choice make is that which produces the,largest immediate gain,while maintaining feasibility.,Since each step consists of little work based on a small amount of information, the resulting algorithms are typically efficient.,3,The Fractional Knapsack Problem,Given,n,items of sizes,s,1,s,2, ,s,n, and values,v,1,v,2, ,v,n,and size,C, the knapsack capacity, the objective is to find nonnegative real numbers,x,1,x,2, ,x,n,that maximize the sum,subject to the constraint,4,The Fractional Knapsack Problem,This problem can easily be solved using the following greedy strategy:,For each item compute,y,i,=,v,i,/,s,i, the ratio of its value to its size.,Sort the items by decreasing ratio, and fill the knapsack with as much as possible from the first item, then the second, and so forth.,This problem reveals many of the characteristics of a greedy algorithm discussed above:,The algorithm consists of a simple iterative procedure that selects that item which produces that largest immediate gain while maintaining feasibility.,5,Suppose we are given a file, which is a string of characters. We wish to compress the much as possible in such a way that the original easily be reconstructed.,Let the set of characters in the,C,=,c,1,c,2, ,c,n,. Let also,f,(,c,i,), 1,i,n, be the frequency of character,c,i,in the file, i.e., the number of times,c,i,appears in the file.,6,Using a,fixed number of bits,to represent each character, called the encoding of the character, the size of the only on the number of characters in the file.,Since the frequency of some characters may be much larger than others, it is reasonable to use variable length encodings.,7,Intuitively, those characters with large frequencies should be assigned short encodings, whereas long encodings may be assigned to those characters with small frequencies.,When the encodings vary in length, we stipulate that the encoding of one character must not be the prefix of the encoding of another character; such codes are called,prefix codes,.,For instance, if we assign the encodings 10 and 101 to the letters “a” and “b”, there will be an ambiguity as to whether 10 is the encoding of “a” or is the prefix of the encoding of the letter “b”.,8,Once the prefix constraint is satisfied, the decoding becomes unambiguous; the sequence of bits is scanned until an encoding of some character is found.,One way to “parse” a given sequence of bits is to use a,full binary tree, in which each internal node has exactly two branches labeled by 0 an 1. The leaves in this tree corresponding to the characters. Each sequence of 0s and 1s on a path from the root to a leaf corresponds to a character encoding.,9,The algorithm presented is due to Huffman.,The algorithm consists of repeating the following procedure until,C,consists of only one character.,Let,c,i,and,c,j,be two characters with minimum frequencies.,Create a new node,c,whose frequency is the sum of the frequencies of,c,i,and,c,j, and make,c,i,and,c,j,the children of,c,.,Let,C,=,C,-,c,i,c,j,c,.,10,Example:,C,=,a,b,c,d,e,f,(,a,)=20,f,(,b,)=7,f,(,c,)=10,f,(,d,)=4,f,(,e,)=18,11,The Greedy Approach,Other examples:,Dijkstras,algorithm for the shortest path problem,Kruskals,algorithm for the minimum cost spanning tree problem,12,Divide and Conquer,A divide-and-conquer algorithm divides the problem instance into a number of subinstances (in most cases 2), recursively solves each subinsance separately, and then combines the solutions to the subinstances to obtain the solution to the original problem instance.,13,Divide and Conquer,Consider the problem of finding both the minimum and maximum in an array of integers,A,1,n, and assume for simplicity that,n,is a power of 2.,Divide the input array into two halves,A,1,n,/2 and,A,(,n,/2)+1,n, find the minimum and maximum in each half and return the minimum of the two minima and the maximum of the two maxima.,14,Divide and Conquer,Input,: An array,A,1,n, of,n,integers, where,n,is a power of 2;,Output,: (,x,y,): the minimum and maximum integers in,A,;,1.,minmax,(1,n,);,minmax,(,low,high,),1. if,high,-,low,=1 then,2. if,A,low,A,high, then return (,A,low,A,high,);,3. else return(,A,high,A,low,);,4. end if;,5. else,6.,mid,(,low,+,high,)/2;,7. (,x,1,y,1,),minmax,(,low,mid,);,8. (,x,2,y,2,),minmax,(,mid,+1,high,);,9.,x,min,x,1,x,2,;,10.,y,max,y,1,y,2,;,11. return(,x,y,);,12. end if;,15,Divide and Conquer,How many comparisons does this algorithm need?,16,Divide and Conquer,Given an array,A,1,n, of,n,elements, where,n,is a power of 2, it is possible to find both the minimum and maximum of the elements in,A,using only (3,n,/2)-2 element comparisons.,17,The Divide and Conquer Paradigm,The divide step,: the input is partitioned into,p,1 parts, each of size strictly less than,n,.,The conquer step,: performing,p,recursive call(s) if the problem size is greater than some predefined threshold,n,0,.,The combine step,: the solutions to the,p,recursive call(s) are combined to obtain the desired output.,18,The Divide and Conquer Paradigm,(1) If the size of the instance,I,is “small”, then solve the problem using a straightforward method and return the answer. Otherwise, continue to the next step;,(2) Divide the instance,I,into,p,subinstances,I,1,I,2, ,I,p,of approximately the same size;,(3) Recursively call the algorithm on each subinstance,I,j, 1,j,p, to obtain,p,partial solutions;,(4) Combine the results of the,p,partial solutions to obtain the solution to the original instance,I,. Return the solution of instance,I,.,19,Selection: Finding the Median and the,k,th Smallest Element,The media of a sequence of,n,sorted numbers,A,1,n, is the “middle” element.,If,n,is odd, then the middle element is the (,n,+1)/2th element in the sequence.,If,n,is even, then there are two middle elements occurring at positions,n,/2 and,n,/2+1. In this case, we will choose the,n,/2th smallest element.,Thus, in both cases, the median is the,n,/2th smallest element.,The,k,th smallest element is a general case.,20,Selection: Finding the Median and the,k,th Smallest Element,If we select an element,mm,among,A, then,A,can be divided in to 3 parts:,21,Selection: Finding the Median and the,k,th Smallest Element,According to the number elements in,A,1,A,2,A,3, there are following three cases. In each case, where is the,k,th smallest element?,22,Selection: Finding the Median and the,k,th Smallest Element,Input,: An array,A,1,n, of,n,elements and an integer,k, 1,k,n,;,Output,: The,k,th smallest element in,A,;,1.,select,(,A, 1,n,k,);,23,Selection: Finding the Median and the,k,th Smallest Element,select,(,A,low,high,k,),1.,p,high,-,low,+1;,2. if,p,44 then sort,A,and return (,A,k,);,3. Let,q,=,p,/5. Divide,A,into,q,groups of 5 elements each.,If 5 does not divide,p, then discard the remaining elements;,4. Sort each of the,q,groups individually and extract its media.,Let the set of medians be,M,.,5.,mm,select,(,M, 1,q, ,q,/2);,6. Partition,A,low,high, into three arrays:,A,1,=,a,|,a,mm,;,7. case,|,A,1,|,k,: return,select,(,A,1, 1, |,A,1,|,k,);,|,A,1,|+|,A,2,|,k,: return,mm,;,|,A,1,|+|,A,2,|,k,: return,select,(,A,3, 1, |,A,3,|,k,-|,A,1,|-|,A,2,|);,8. end case;,24,Selection: Finding the Median and the,k,th Smallest Element,What is the time complexity of this algorithm?,25,Selection: Finding the Median and the,k,th Smallest Element,The,k,th smallest element in a set of,n,elements drawn from a linearly ordered set can be found in,(,n,) time.,26,Selection: Finding the Median and the,k,th Smallest Element,Write the codes for the above algorithm.,27,Divide and Conquer,Other example:,Quicksort,28,Dynamic Programming,Dynamic programming resorts to evaluating the recurrence in a bottom-up manner, saving intermediate results that are used later on to compute the desired solution.,This technique applies to many,combinatorial optimization problems,to derive efficient algorithms.,29,Dynamic Programming,Fibonacci sequence:,f,1,=1,f,2,=1,f,3,=2,f,4,=3,f,5,=5,f,6,=8,f,7,=13,f(,n,),1. if (,n,=1) or (,n,=2) then return 1;,2. else return f(,n,-1)+f(,n,-2);,This algorithm is far from being efficient, as there are many duplicate recursive calls to the procedure.,30,Dynamic Programming,f,(,n,),1. if (,n,=1) or (,n,=2) then return 1;,2. else,3. ,4.,fn,_1=1;,5.,fn,_2=1;,6. for,i,3 to,n,7.,fn,=,fn,_1+,fn,_2;,8.,fn,_2=,fn_,1;,9.,fn,_1=,fn,;,10. end for;,11. ,12. Return,fn,;,Time:,n,-2 additions, (,n,),Space: (1),31,The Longest Common Subsequence Problem,Given two strings,A,and,B,of lengths,n,and,m, respectively, over an alphabet, determine the length of the longest subsequence that is common to both,A,and,B,.,A subsequence of,A,=,a,1,a,2,a,n,is a string of the form,a,i,1,a,i,2,a,ik, where each,i,j,is between 1 and,n,and 1,i,1,i,2,0 and,j,0, is the maximum of the following two quantities:,The Knapsack Problem,V,i,-1,j,: The maximum value obtained by filling a knapsack of size,j,with items taken from ,u,1,u,2, ,u,i,-1, only in an optimal way.,V,i,-1,j,-,s,i,+,v,i,: The maximum value obtained by filling a knapsack of size,j,-,s,i,with items taken from ,u,1,u,2, ,u,i,-1, in an optimal way plus the value of item,u,i,. This case applies only if,j,s,i,and it amounts to adding item,u,i,to the knapsack.,45,Then, we got the following recurrence for finding the value in an optimal packing:,The Knapsack Problem,Using dynamic programming to solve this integer programming problem is now straightforward. We use an (,n,+1),(,C,+1) table to evaluate the values of,V,i,j,. We only need to fill the table,V,0,n, 0,C, row by row using the above formula.,46,Example,:,C,=9,U,=,u,1,u,2,u,3,u,4,S,i,=2, 3, 4, 5,V,i,=3, 4, 5, 7,The Knapsack Problem,47,Input,: A set of items,U,=,u,1,u,2, ,u,n, with sizes,s,1,s,2, ,s,n,and values,v,1,v,2, ,v,n,and a knapsack capacity,C,.,Output,: The maximum value of the function subject to for some subset of items,S,U,.,1. for,i,0 to,n,2.,V,i, 00;,3. end for;,4. for,j,0 to,C,5.,V,0,j,0;,6. end for;,7. for,i,1 to,n,8. for,j,1 to,C,9.,V,i,j,V,i,-1,j,;,10. if,s,i,j,then,V,i,j, max,V,i,j,V,i,-1,j,-,s,i,+,v,i,;,11. end for;,12. end for;,13. return,V,n,C,;,The Knapsack Problem,48,What is the time and space complexity of this algorithm?,The Knapsack Problem,49,An optimal solution to the Knapsack problem can be found in,(,nC,) time and (,C,) space.,The Knapsack Problem,50,Dynamic Programming,Other example:,Floyd Algorithm for the All-Pairs Shortest Path Problem,51,Backtracking,In many real world problems, a solution can be obtained by exhaustively searching through a large but finite number of possibilities. Hence, the need arose for developing systematic techniques of searching, with the hope of cutting down the search space to possibly a much smaller space.,Here, we present a general technique for organizing the search known as,backtracking,. This algorithm design technique can be described as an organized exhaustive search which often avoids searching all possibilities.,52,The 3-Coloring Problem,Given an undirected graph,G,=(,V,E,), it is required to color each vertex in,V,with one of three colors, say 1, 2, and 3, such that no two adjacent vertices have the same color. We call such a coloring,legal,; otherwise, if two adjacent vertices have the same color, it is,illegal,.,A coloring can be represented by an,n,-tuple (,c,1,c,2, ,c,n,) such that,c,i,1, 2, 3, 1,i,n,.,For example, (1, 2, 2, 3, 1) denotes a coloring of a graph with five vertices.,53,The 3-Coloring Problem,There are 3,n,possible colorings (legal and illegal) to color a graph with,n,vertices.,The set of all possible colorings can be represented by a complete ternary tree called the,search tree,. In this tree, each path from the root to a leaf node represents one coloring assignment.,An incomplete coloring of a graph is,partial,if no two adjacent colored vertices have the same color.,Backtracking works by generating the underlying tree one node at a time.,If the path from the root to the current node corresponds to a legal coloring, the process is terminated (unless more than one coloring is desired).,54,The 3-Coloring Problem,If the length of this path is less than,n,and the corresponding coloring is partial, then one child of the current node is generated and is marked as the current node.,If, on the other hand, the corresponding path is not partial, then the current node is marked as a,dead node,and a new node corresponding to another color is generated.,If, however, all three colors have been tried with no success, the search backtracks to the parent node whose color is changed, and so on.,55,Example:,a,The 3-Coloring Problem,b,c,d,e,56,The 3-Coloring Problem,There are two important observations to be noted, which generalize to all backtracking algorithms:,(1) The nodes are generated in a depth-first-search manner.,(2) There is no need to store the whole search tree; we only need to store the path from the root to the current active node. In fact, no physical nodes are generated at all; the whole tree is implicit. We only need to keep track of the color assignment.,57,The 3-Coloring Problem,Recursive Algorithm,Input,: An undirected graph,G,=(,V,E,).,Output,: A 3-coloring,c,1,n, of the vertices of,G, where each,c,j, is 1, 2, or 3.,1. for,k,1 to,n,2.,c,k,0;,3. end for;,4.,flag,false;,5.,graphcolor,(1);,6. if,flag,then output,c,;,7. else output “no solution”;,graphcolor,(,k,),1. for,color,=1 to 3,2.,c,k,color,;,3. if,c,is a legal coloring then set,flag,true and exit;,4. else if,c,is partial then,graphcolor,(,k,+1);,5. end for;,58,The 3-Coloring Problem,Iterative Algorithm,Input,: An undirected graph,G,=(,V,E,).,Output,: A 3-coloring,c,1,n, of the vertices of,G, where each,c,j, is 1, 2, or 3.,1. for,k,1 to,n,2.,c,k,0;,3. end for;,4.,flag,false;,5.,k,1;,6. while,k,1,7. while,c,k,2,8.,c,k,c,k,+1;,9. if,c,is a legal coloring then set,flag,true and exit from the two while loops;,10. else if,c,is partial then,k,k,+1;,11. end while;,12.,c,k,0;,13.,k,k,-1;,14. end while;,15. if,flag,then output,c,;,16. else output “no solution”;,59,The 8-Queens Problem,How can we arrange 8 queens on an 8,8 chessboard so that no two queens can attack each other?,Two queens can attack each other if they are in the same row, column or diagonal.,The,n,-queens problem is defined similarly, where in this case we have,n,queens and an,n,n,chessboard for an arbitrary value of,n,1.,60,The 8-Queens Problem,Consider a chessboard of size 4,4. Since no two queens can be put in the same row, eac