Algorithm Design ECS 122A
Popular in Course
Popular in Engineering Computer Science
This 28 page Class Notes was uploaded by Ashleigh Dare on Tuesday September 8, 2015. The Class Notes belongs to ECS 122A at University of California - Davis taught by Zhaojun Bai in Fall. Since its upload, it has received 23 views. For similar materials see /class/187716/ecs-122a-university-of-california-davis in Engineering Computer Science at University of California - Davis.
Reviews for Algorithm Design
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/08/15
Discussion 6 Yuanbo Zhu Homework 3 is on desk Important Notice Checklist for midterm Solution sheets of hw1 hw4 Outline Hw 4 Review Hw 4 1 Suppose we have a set of activities to schedule among a large number of lecture halls We wish to schedule all the activities using few lecture halls as possible Give an efficient greedy algorithm to determine which activity should use which lecture hall intervalgraph coloring Solution Ansn39ss Lst in tin sst ni n sniisitiss Snintinn 1 Tbs nininns snlniinn sf nsing i3rsssiynntisitifsSslsntnr is tn nsi s Insnilnnlnsiss sst 31 nf nninpntibls sstisitiss innnn inn tins rst lsstnrs hsli tinsn using it sgnin tn nnn Innsininnisiss sst 5393 ni snlnpstibls sniisitiss from 539 5391 inn the sssnnd hsiii snn nn nntil nil ths sstisitiss sis sssignsi This rsnninss Bing inns in the snrst nsss sings Nntn inn will inns this ns s nnnnnnt nnsn39ns inn ginning Sorting by finishing time ncreasing order 6 g Onlog n 1 3 5 9 2 4 7 6 8 1 3 5 9 2 4 7 6 8 1 3 5 9 2 4 7 6 8 1 3 5 9 Coloring Hw 4 2 2 the are given 71 jehs jnjg j with known ninning tinne t1st2in eespeetinety the tense n e nvnnsge enmpietinn time quot 39iinn39 ZCt singie ptocessen the tent to seheetnie these jobs so as to 111 We assume nnnpeee npthn scheduling he once n jnh is stanteet it nest sun to enmphetinn Speeih n gneeety nignnithnn ion the jnh seheetniing penhhnn nnet pines the npthnnhty e Answer The grimly solution is to arrange 1hr jobs in shortest job rst We ran show that this yields an nptimal schedule Let the running timc is of n jobs be sorted well that s n s n 35quot31 11 Then the i st jnh nishes in nine 11 AM the second job nishes nftnr 9 iw and the third job lllb llli a zii39ler 17 I r95 nnLl an on Hence the average uinpleuion time is 1 C InArign 43413 l 7 illii i ml lll2lili21 13iu lquot 1 1 m l n F201 hllik1gt2tw lrtih Kl i1 i1 Note that thn rst term is indrpendcnt of tho job ordering so only the recond term n ncts the average cmnplebion tinw Let I lt hm minim In Then ii is any to see that by pping Ll an 1 the second term lecrencesi increasing the total average comple J11 est Therr f e C is optimal 3 The in knapwwk niniiieni itmm W n in in mi in any the Value Mid Wiligm uf 11mm n 19313 im given aw follows The Luml weight W 100 n Find tho gu mly solutions by using fallowing poss wilitios i h m ly by Valun in ni oarh up soloi ii mm thc remaining itoms the one with iin iiiniim Valiic ii Greedy by weight 10 ni and step sninci imin iiic i39cuminin n items hhi inn with the innsi weight iii Greedy by 110 Value per pmmiL 14m mi Biwh m39p 010 from the i39mimining i39iums Wifih he largest 1min iiL m h CUmth he column by ilyiiaiiiic pruni aiiiuiiiig iiimrli n mpy ni39 ynui39 pi39ngi39aiii 0 Brie y comment ulll iiiniinnn b Code omit the selectBIl item given by the DP is shown in the last column of the above table 0 sketch In all three approoi hes generate feasible solutions but none of them generate the optimal solution 011 the other hand the solution given by the dynamic progrannning is optimal Hw 4 4 4 Give a Huffman mm E far the jllmving String ACCGGTCGAGTG3GCGGAAGCCGGCOGAA theamihe hath ymur BEBE and the actual binary amending ANSWEF char EElLlE F Backward 3 12 I E El 10 A 5 iii T 13 11 1 Hw 4 5 what is an optimal Huffman code for the following set of frequencies based on the first 8 Fibonacci numbers 1 12 3 5 8 13 21 Can you generalize your answer to find the optimal code when the frequencies are the first n Fibonacci numbers Solution char equeneje cede fn2 3 ft 11 21 1 l g 13 01 f C fnll Jon 3 e 5 111101 1 3 01111111 39111 2 f e 2 1101111111 h 1 1101111001 case f1 3311 f1 51 1 neeeeee In generel the eede fer the 11th ehereeteh in e eequenee ef h ehereetere where the frequeneiee ere the rst 11 Fiheeeeei numhere is 11 l he when 1 end GW3931 fee 2 1L ECSl22A Algorithm Design and Analysis Handout Midterm Review Checklist May 7 2009 Here are a list of algorithm design and analysis techniques algorithms math concepts and de nitions that you should know from lecture discussion and homework This is not meant to be comprehensive It is merely a reminder of what we have covered so far Algorithm design and analysis techniques and case stdudies 1 Divide and Conquer Computing the nth Fibonacci number MergeSort vs lnsert sort Strassen s algorithm for matrix multiplication Maximum and minimum nding Searching for i in an array A to Dynamic Programming Assembly line scheduling Longest common subsequence Maximum common substring 0 1 knapsack problem Money changing 03 Greedy algorithms ActiVity selection problem Activity lecture hall scheduling problem Data compression Via Huffman coding Knapsack problem 0 1 and fractional Job scheduling problem De nitions and concepts 1 Mathematical induction 2 Worst case and average case analysis 3 Order of growth 4 09 9 notations 5 Recurrences 6 The master theorem ECS122A Handout The 01 Knapsack Problem Problem statement A thief robbing a store nds 71 items the 2th item is worth 1 dollars and weights w pounds He wants to take as valuable a load as possible but he can carry at most W pounds in his knapsack Here 1 w and W are all positive integers What items should be taken Formally the problem can be stated as follws Given 71 items of values 11111211n and of the weight 101102 wn and a total weight W where 1 w and W are positive integers Find a subsect S Q 1 2 n of the items such that 2w 3 W and 1 is maximized 13968 13968 This is called the 01 knapsack problem because each item must either be taken or left behind the thief cannot take a fractional amount of an item or take an item more than once The knapsack problem is an abstraction of many real problems from investing to telephone routing Dynamic Programming 1 The solution is based on the optimal substructure observation Let k be the highest numberd item in an optimal solution 8 of W pounds and items 12 n Then S S 7 is an optimal solution for W 7 wk pounds and items 12 k 71 and the value of the solution 8 is 1 plus the value of the subproblem solution S D We can express the optimal substructure observation in the following recursive formula De ne cz w to be the value of an optimal solution for items 1z39 and maximum weight w Then 0 if z3900rw0 cz w max1cz3971w7wic 71w if gt0andwigw cz3971w if gt0andwigtw This says that the value of a solution for item 239 is 0 either includes item 239 in which case it is 1 plus a subproblem solution for 2397 1 items and the weight excluding 10 0 or does not include item 239 in which case it is a subproblem solution ofz39 7 1 items and the same weight This is if the thief picks item 239 he takes 1 value and he can choose from items 1z39 7 1 up to the weight limit w 7 10 and get ch 7 1w 7 10 additional value On the other hand if he decides not to take item 239 he can choose from items 1z3971 up to the weight limit w and get ch 7 1 w value The better of these two choices should be made 1 3 Although the 0 1 knapsack problem doesnt seem analogus to the LCS problem7 the above formula for c is similar to the LCS formula initial values are 07 and other values are computed from the inputs and earlier values of 0 So the 0 1 knapsack problem is like the LCS LENGTH algorithm for nding the LCS of two sequences The pseudocode is presented below The algorithm takes as inputs the maximum weight lV7 the number of items 717 and the two sequences 1 ltUl711271ngt and w ltw17w27 10 It stores the chm values in the table of clOn7 whose entries are computed row major order This is7 the rst row of c is lled from left to right7 then the second row7 and so on At the end of the computation7 elm W contains the maximum value the thief can take 7 Dynamic O l Knapsackvwnw for w O to W COw O for i 1 to n ci0 O for w 1 to W if wi lt w then if vi Ci 1w wi gt Ci 1w then Ciw Vi Ci 1W Wi else Ciw Ci 1w else Ciw Ci 1w 5 The set of items to take can be deduced from the c table by starting at cn7 W and tracing where the optimal values came from o If chm clz 7 17w7 item 239 is not part of the solution7 and we continue tracing with c 717w 0 Otherwise itemz39 is part ofthe solution7 and we continue tracing with c 717w7wi 6 The above algorithm takes nW time total 0 nW to ll in the 0 table 7 n 1 W 1 entries each requiring 91 time to compute o 0n time to trace the solution since it starts in row 71 of the table and moves up 1 row at each step Example Let 7197 1 lt273737474757 77878gt7 w lt375777473797271175gt7 W15 By the program Dynamic O l KnapsackVwnw7 the calculated C table is w gt 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 239 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 239 1 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 239 2 0 0 0 2 2 3 3 3 5 5 5 5 5 5 5 5 239 3 0 0 0 2 2 3 3 3 5 5 5 5 6 6 6 8 239 4 0 0 0 2 4 4 4 6 6 7 7 7 9 9 9 9 239 5 0 0 0 4 4 4 6 8 8 8 10 10 11 11 11 13 239 6 0 0 0 4 4 4 6 8 8 8 10 10 11 11 11 13 239 7 0 0 7 7 7 11 11 11 13 15 15 15 17 17 18 18 239 8 0 0 7 7 7 11 11 11 13 15 15 15 17 17 18 18 239 9 0 0 7 7 7 11 11 15 15 15 19 19 19 21 23 23 Optimal value cn7 W c9715 23 The set of items to take 97 77 57 4 ECSlQ2A Handout May 21 2009 A priority queue is a data structure for maintaining a set S of elements7 each with an associated value called a key There are maxpriority queue and minpriority queue7 supporting the following operations A disjointset data structure maintains a collection of S S17S2 lNSERTSx inserts the element x into the set S SHSUJE DELETEltS7 deletes the element x from the set S S H S 7 MAXIMUMS returns z E S with largest key MINIMUMS returns z E S with smallest key SEARCHltS7 k returns z E S with keyM k EXTRACT MAXS removes and returns z E S with largest key EXTRACT MINS removes and returns z E S with smallest key lNCREASE KEYS7x7k increases the value of element z7s key to the new value k7 which is assumed to be at least as large as z7s current key value DECREASE KEYS7z7k decreases value of element z7s key to the new value k7 which is assumed to be at least as small as z7s current key value 7Sk of disjoint dynamic sets Each set is identi ed by a representative7 which is some member of the set A disjoint set data structure supports the following operations MAKE SETz creates a new set whose only member and thus representative is x UNION7y unites the sets that contain z and y say S1 and Sy7 into a new set that is the union of these two sets Sm U Sy The representative is any member of S1 U Sy FIND SETz returns a pointer to the representative of the unique set containing x ECSl22A Handout May 26 2009 Bellrnan FordG7 w7 s 1 INIT SINGLE SOURCEV5 2 forz391toV71do 3 for each edge um E E do 4 RELAxu1w 5 endfor 6 endfor 7 for each edge um E E do 8 if dM gt du wuv then check pass gtk 9 return false 10 endif 11 endfor 12 return true INIT SINGLE SOURCEW s 1 for each vertex 1 E V do 2 db oo 3 y NIL 4 endfor 5 d5 0 Notes dM 6570 the shortest path weight from the source vertex 5 to 1 y the parent predecessor of 1 Bellman Ford algorithm returns true if no negative weight cycles reachable from source vertex 57 false otherwise How quickly dM converges depends on order of relaxation processing edges But guar anteed to converge after V 7 1 passes7 assuming no negative weight cycles ECS122A Handout Money Changing 1 D 00 r The money changing problem starts with a given set of positive integers called denomi nations 1727 zn think of them as the integers 17 57 107 and 25 and an integer A7 we want to nd nonnegative integers 117 7a 2 0 such that n A Z ai i i1 First7 we note that A can be expressed as a linear combination of the m if and only if m 1 for some 239 Here is a proof If one of your denominations xi is 17 you will certainly be able to express every integer A as 221 am for some nonnegative integers 117 7an Conversely7 in order to express A 1 as a linear combination7 you must have xi 1 for some 239 In general not necessarily satisfying the condition in the rst part7 a necessary condi tion that A ELI am is that g gcdz17 divides A In fact7 glA turns out to be both necessary and suf cient for A 2 X for some large X Here is a proof From the extended Euclidean algorithm we know we can write 9 221 gixi with some possibly negative 91 Now let G 21 lgilxi xmm mini xi k zmmg7 and X kG First note that the k consecutive multiples of g in the set S kG7kG gkG 297 7kG k 7 1g all have nonnegative coef cients when written as ELI aizi The next multiple of g is kG kg kGmm7 which has even larger nonnegative coef cients than kG The next k 7 1 multiples of g consequently also have nonnegative coef cients until we get to kG 2mm and so on Note that the coef cients are not necessarily unique all the xi could be identical7 but we have shown that there is at least one set of nonnegative coef cients for all multiple of g at least equal to X Optimal money changing problem is that for a given A7 nd the nonnegative as that satisfy A 2 am and such that the sum of all as is minimal 7that is7 you use the smallest possible number of coins Here is a greedy algorithm for solving this problem Order your denominations such that 1 gt 2 gt gt x Then the greedy algorithm for this problem would be Given A7 let 11 be the largest integer such that a l S A If A 7 a l gt 07 let 12 be the largest integer such that 1ng S A 7 alzl If you have nothing left over after doing this for 239 17 7n7 then A 221 aixi 5 CT Let us show that the greedy algorithm nds the optimum as in the case of the denom inations 1 5 10 and 25 Here is a proof Since 1 divides 5 and 5 divides 10 it is clear that if we have a case in which the greedy algorithm would not nd the optimal solution it must involve 25 ie A must be greater than 25 Assume the greedy algorithm does not nd the optimal solution for A A gt 25 Then A 2211 1x 2211 bix and 21 1 gt 2211 b where the a were determined by the greedy algorithm and the b are optimal in that 2211 b is minimal Wlog a4 b4 since 14 S 4 any change of the number of 1 cent coins must occur in 5 unit steps to give the same sum this is obviously worse than changing b3 in addition to that note that as S 1 By the above considerations we must have 11 gt b1 Let s 11 7191 We have three cases to consider a2 b2 12 gt b2 and 12 lt b2 If we set y a2 7 b2 then we can compute b3 5x 2y 13 Thus the number of coins changes by 2211 b 7 221 1 4x y If we can show that this number is positive this is a contradiction and we are done In cases 1 and 2 z and y are 2 0 Therefore 4x y is clearly positive In case 3 y is negative But as we have to ensure that b3 5x 2y a3 is 2 0 and we know that as is at most 1 we have y 2 73z 7 Hence 4x y 2 3x 7 and it is again positive You can extend this problem and ask What are good necessary and suf cient conditions on a currency such that the greedy algorithm always gives the minimum amount of coins77 This problem is still open Partial answers and a light7hearted discussion give a M J Magazine G L Nemhauser L E Trotter Jr When the Greedy Solution Solves a Class of Knapsack Problems Operations Research 23 1975 p 207 7 217 b John Dewey Jones Orderly Currencies American Mathematical Monthly 101 1994 p 36 7 38 c Stephen B Maurer Disorderly Currencies American Mathematical Monthly 101 1994 p 419 ECS122A Handout May 28 2009 I Introduction 1 to DJ Tractable easy not so hard and intractable hard problems Generally we think of problems that are solvable by polynomial time algorithms are being tractable and problems that require superpolynomial time as being intractable Almost all the algorithms we have studied thus far have been polynomial time algorithms on inputs of size n their worst case running time is 0nk for some constant k We now turn to a class of problems called the NP complete problems which is a class of very diverse problems that share the following properties we only know how to solve those problems in time much larger than polynomial namely exponential time and if we could solve one NP complete porblem in polynomial time then there is a way to solve every NP complete porblem in polynomial time Two reasons to study NP complete porblems a The practical one is that if you recognize that a problem is NP complete then you have three choices 0 you can use a known algorithm for it and accept that it will take a long long time to solve if n is large 0 you can settle for approximating the solution eg nding a nearly best solution rather than the optimum or c you can change your problem formulation so that it is solvable in polynomial time A T V One of the most famous open problem in computer science concerns it We stated above that we only know77 how to solve those problems in time much larger than polynomial not that we have proven that NP complete problems require exponential time Indeed this is the million dollar question httpwwwclaymathorgprizeproblems one of the most famous problem in computer science the question is whether P NPY or whether the class of NP complete problems have polynomial solutions rst posed in 1971 A particular tantalizing aspect of the NP complete problems is that several of them seem on the surface to be similar problems that have polynomial time algorithms In each of the following pairs of problems one is solvable in polynomial time and the other is NP complete but the difference between problems appears to be slight o Shortest and longest simple paths Shortest path from a single source in a directed graph G Longest path nding the longest simple path between two vertices in a directed graph G 0 Minimum spanning tree MST and traveling salesperson problem TSP 7 MST given a weighted graph and an integer k is there a spanning tree whose total weight is k or less 7 TSP given a weighted graph and an integer k is there a cycle that visits all vertices exactly once of the graph whose total weight is k or less o Euler cycle and Hamilton cycle 7 Euler cycle given a directed graph G is there a cycle that visits each edge exactly once 7 Hamilton cycle given a directed graph G is there a cycle that visits each vertex exactly once 0 Circuit value and Circuit satis ability SAT 7 Circuit value given a Boolean formula and its input is the output True 7 Circuit SAT Given a Boolean formula is there a way to set the inputs so that the output is True 4 Optimization problems and decisions problems Most of problems occur naturally as optimization problem but they can also be formulated as decision problem that is problems for which the output is a simple Yes or No answer for each input Examples 0 Graph coloring A coloring of a graph G V E is a mapping C V 7 S where S is a nite set of colors such that if 1412 6 E then Cu 7 C12 7 optimization problem given G determine the smallest number of colors needed 7 decision problem given G and a positive integer k is there a coloring of C using at most k colors If so G is said to be k colomble 0 Traveling salesperson problem TSP 7 optimization problem given a weighted graph nd a minimum Hamilton cycle 7 decision problem Given a weighted graph and an integer k is there is Hamilton cycle with total weight at most k 0 Hamilton cycle A Hamilton cycle in a graph directed or undirected is cycle that passes through every vertex exactly once 7 decision problem Does a given graph have a Hamilton cycle 7 optimization problem Give a list of vertices of an Hamilton cycle To simplify the discussion we can consider only the decision problems with Yes No answers rather than the optimization problems II P and NP 1 to 03 U ugt P is the class of decision problems that can be solved in polynomial time or say that that are polynomial bounded An algorithm is said to polynomial bounded if its worst case complexity is bounded by a polynomial function of the input size ie Tn Examples MST Eular cycle Circuit value NP is the class of decision problems that are veri able in polynomial time What we mean here is that if we were somehow given a certi cate a solution then we could verify that the certi cate is correct in time polynomial in the size of input to the problem Examples Hamiltonian cycle Circuit SAT graph coloring P Q NP since if a problem is in P then we can solve it in polynomial time without even being given a certi cate The open question is Does P NP or whether or not P is a proper subset of NP The size of the input P or NP7 Knowing the effect on complexity of restricting the set of inputs for a problem is important Examples 0 Primetesting problem 0 Knapsack problem Remark Unfortunately even with quite strong restrictions on the inputs many NP complete problems are still NP complete For example 3 CNF satis ability problem III NPcomplete 1 to 03 q 01 a 1 Theorem Graph coloring HC TSP NP complete is the term used to describe decision problems that are the hardest ones in NP in the sense that if there were a polynomial bounded algorithm for an NP complete problem then there would be a polynomial bounded time for each problem in NP Polynomial reduction Let A and B be two decision problems we say that A is polynomially reducible to B denoted as A 1 B if and only if there is a poly time computable function T such that Yes instance of A gt Yes instance of B and No instance of A gt No instance of B Formal de nition of NP complete A decision problem A is NP complete NPC if 1 A E NP and 2 every other problems A in NP is reducible to A How most theoretical computer scientists View the relationships among P NP and NPC Both P and NPC are wholly contained within NP and P H NPC Q NP If a problem satis es property 2 but not necessarily property 1 we say the problem is NP hard It is important to realize that NP hard does not mean in NP and hard It means at least as hard as any problem in NP Thus a problem can be NP hard and not be in NP Cook s theorem 1971 The circuit satis ability circuit SAT problem is NP complete Cook s theorm is the rst major theorem deomonstrating that a speci c problem is NP complete are all NP complete IV How to prove a problem is NPcomplete 1 Since the reducibility relation is transitive to prove that a problem A in NP is NP complete it suf ces to prove that some other NP complete problem B is polynomially reducible to it Speci cally choose some known NP complete problem B and reduce B to A not the other way around ie show that B 1 A The logic is as follows Since B is NP complete all problems in NP is reducible to B Show B is reducible to A Then all problems in NP is reducible to A Therefore A is NP complete 2 Examples to show how to prove a problem A is NP complete o Directed HC 1quot Undirected HC Since the directed HC problem is known to be NP complete we conclude that the undirected HC problem is also NP complete o SUBSET SUM gT JOB SCHEDULING Since the subset sum problem is known to be NP complete we conclude that the job scheduling problem is also NP complete
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'