Algorithm Design ECS 122A
Popular in Course
Popular in Engineering Computer Science
This 66 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 36 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.
Date Created: 09/08/15
Discussion Section 3 Yuanbo Zhu Outline Dynamic Programming Asymptotic running time Master method Dynamic Programming Greedy Algorithm Midas drives a car crosscountry Gas tank can hold enough gas to drive k miles Gas stations g1 g2 gn are separated by distances d1 d2 dn Whenever he stops he lls up his tank Greedy alg for Midas Drive car as far as possible Only stops for gas if he could not make it to the next stop otherwise Gas Stations f 4stops decides to stop here k the furthest he could have gone How to prove it Properties of greedy algorithm 1 Optimal substructure 2 Greedy choice property locally optimal choice is also globally optimal gt Assume an Optimal solution OPT comparing OPT and Greedy on some metric induction on How to prove it Base case OWEN 2 DOPTU because Midas travels as far as possible on the first gas tank Inductive step Assume Dmydadm 2 DOPTm Then on step m1 both OPT and Midas can cover up to l additional miles Midas stops at the last gas station before DWdaSm k On this step OPT started no further than Midas and travelled the same distance so OPT can not reach any further gas station Therefore DWdaSm1 2 DOPTm1 Since Midas can always cover at least as much distance as OPT in in steps then Midas is guaranteed to use no more stops than OPT on any fixed distance OPT K Midas 1 the choice set of Madis gt the choice set of OPT Outline Dynamic Programming Asymptotic running time Master method notati on For function gn we de ne gn bigTheta of n as the set 392 01 gn fn El positive constants cl CZ and n0 f M such that Vn 2 no we have 0 S clgn S fn S czgn 2 Intuitively Set of all functions that have the same rate of growth as gn 502 n no fn gn gn is an asymptotically tight bound for fn Onotatlon For function gn we de ne 0gn bigO of n as the set go 0gn fn El positive constants c and no such that Vn 2 no we have 0 S fn S cgn Intuitively Set of all functions Whose rate ofgmwth is the same as or lower than that of gn I quot0 fn 0w gn is an asymptotic upper bound for fn fn gn gtfn 0gn gn C 0gn Q notatlon For function gn we de ne Qgn bigOmega of n as the set fn Q501 fn El positive constants c and no such that Vn 2 no we have 0 S cgn S n Intuitively Set of all functions I Whose rate of growth is the same 1 n as or higher than that of gn quot0 fol g2 goo gn is an asymptotic lower bound for fn fn gn 10 9gn gn C 9gn Relations Between 9 O Q Relations Between 9 Q 0 39 le gn 09quot Q907 In practice asymptotically tight bounds are obtained from asymptotic upper and lower bounds Comparison of Functions flt gtg z alt gtb f n Ogn z a s b fn Qgn z a 2 b fn 9n a b fn 09n a lt b fnwgn a gt b Limits Ligwfn 907 0 gt 7 0 e 0gn ligwfn 907 lt 00 gt 7 0 E 0gn 0 lt mow 907 lt 00 gt 7 0 e gn 0 lt Inig n 90 gt 7 0 e Q9707 IIQOUW 907 00 gt 7 07 E wgn Practice asymptotic running time a Show that F13 is not 0mg I Show that togn OW for any positive 6 Use the fact that tog39n n tn 2 1 a Show that HE Ofe for any 1osittve E 39 fngn ltigt fnlt091n fnlt lim C W god I Common functions Example 371 E Proof In order to prove this we must show that for all 17 greater than some no there do not exist any constants c such that 3 ltcquot 239l 3 quot lt c For any constant c that we pick we can always find an n such that n is greater than c Growth rates of common functions 28 for every bgt1 and every xgt0 we have x 10gb n orn gt 29 for every rgt1 and every dgt0 we have nd 2 Or Solution Solution Outline Dynamic Programming Asymptotic running time Master method Master Method 4 3 Recurrent formula Tn aTnb fn 1 if f n 0n1 gb 8for some a gt 0 then Tn embgb 2 if fn n1 gb then Tn nlogbalogn 3 if fn Qn1 gb 8 for some a gt O and a fnbs C fn for some C lt 1 then T n f 11 Master Method Examples Merge sort Tn 2Tn2 n n1 g22 n n 3 CaseZ Tn nlog 72 Tn 7Tn2 6907 nlog27 8 quot281 081 0n2 Z Casel nlog27 N n2807 Discussion 7 Yuanbo Zhu May 15 2009 Outline Graph notation BFS DFS What is a graph A set of vertices and edges GV E DirectedUndirected WeightedUnweighted CyclicAcyclic Representation of Graphs GV E Two common ways 1 4 2 4 AdJacency LIStS 3 5 5 39 39 4 1 2 5 AdJacency Matrix 5 2 34 mwa x OAOOO Representation of Graphs Adjacency Adjacency Matrix Linked List Memory OV2 OVE Storage Check whether 01 Odegu uv is an edge Find all OV Odegu adjacent vertices of a vertex u degu the number of edges connecting vertex u Graph Searching Why do we do graph searching What do we search for What information can we find from graph searching How do we search the graph Do we need to visit all vertices In what order Breadthfirst Search amp Deepfirst Search Breadthfirst Search Problem statement For a given graph G and a specified 5 in the graph find all vertices v that are reachable from s and determine the shortest path in G from s to v Strategy begins at the root vertex and explores all the neighboring vertices Then for each of those nearest vertices it explores their unexplored neighbor vertices and so on until it finds the goal DepthFirst Search DFS Strategy Go as far as you can if you have not visit there otherwise go back and try another way DFS vertex u mark u as visited for each vertex v directly reachable from u if v is unvisited DFS v Difference Between BFS and DFS Breath first ensures that all the nearest possibilities have been explored Depth first keeps going as far as it can then goes back to look at other options Application of BFS Shortest path in an unweighted graph A good way of showing BFS Practical Applications Cheapest international phone call Most reliable emailinternet route Quickest travel time between two towns Weighted graphs numbers on edges make searching more complex BFS uses queues First In First Out 1 24 45 5 367 67 78 8 Pathis12568 Find the shortest path between nodes 1 and 8 Keep a queue of nodes and a note of which nodes we have visited and how we got to This algorithm passes along each edge at most once so it has time complexity OE Depth First Search DFS Go as far as we can if we don39t have a solution backtrack to an unvisited branch and try another route Backtracking is not found in BFS DFS uses stacks Last In First Out not queues 0 Example topological sort Finding the topological order of a directed acyclic graph Summary These searches are very common Adaptable to many problems But not all Used widely outside graphs Eg backtracking and tree searching Topological Sort Topological order A numbering of the vertices of a directed acyclic graph such that every edge from a vertex numbered i to a vertex numberedj satisfies iltj Topological Sort Finding the topological order of a directed acyclic graph Problem Given as input a weighted directed acyclic graph where the edge weights can be positive or negative design the following and provide an analysis of their running times a An algorithm that nds the longest path in the graph b An algorithm that nds the shortest path in the graph Will Dijkstralike Algorithm work Consider the negative link weight Explanation From s to all other nodes Shortest path agtb 2 agtcgtb agtc 1 agtc agtd 6 agtcgtbgtd Lonqest path agtb 3 agtb agtc 1 agtc agtd 10 agtcgtd Discussion 4 Yuanbo Zhu Outline Review of Assemblyline scheduling Review of Longest common sequence Dynamic programming VS Greedy algorithm What is dynamic programming Is an algorithm method that solves a problem by combining solutions of subproblems This sounds similar to divideandconquer However there s a difference between the two ln divideandconquer the subproblems don t overlap ln dynamic programming the subproblems overlap Subproblems share subsubproblems Sequence in the development of a dynamic programming algorithm Characterize the structure of an optimal solution Recursively define the value of an optimal solution Compute the value of an optimal solution in a bottomup fashion smaller subproblems first Construct an optimal solution from computed information Step 4 omitted if only the value of the best solutions is required Assemblyline scheduling There are Iwo parallel assembly lines lor assembling a car Each of them panorms lhe same sequence of operations but at di erem rales II is also possible at some cost 01 time to lransler the carlrom one assembly line to the other All the values in circles are limes laliun i J W many ML 7 mums MlllnmSl mum x mum 51 when 31 xl in A4 The problem is in lind a shortesl palh lrom start to linish Assemblyline scheduling Each assembly line has 1 stations Notation gt 5 is the jth station in line 1 gt u is the processing time at station SM gt rm is the time to transter tram sw to SW i 1 gt e is the entry time tor line i gt Y is the exit time for line i i12and1i2 Assemblyline scheduling mature at the fastestway through Ihe lacluly The Car quotIn 39 L Sage ram stage j 71 in the same assemb y ine or by lransterring with a cost 1mm stage j 71 in the oxher assemb y ne The s es iseihe N Thus Khe taste 5 way V39T slest way through 3 and then passing through 3 or gt Ihefaslestwaylhrough Saw a lransfer from inez to line 1 and than passing Assemblyline scheduling Step 2 A recursive solution Let i be the least possible time to get a car lrom the starting point through station S Then we have ftl1llt itlii a1lt 2uzt fillV minifili 11Uilf2l Harva l 21 fall minif U 11 247ill 1 tri 2 The overall shortest time to complete the cat is mint fln quot f392nx2 l station SLl stntiun SL2 statiun Sm station SM statinn SL5 station 5L6 Assamny line i SlaLion 52 station S station 52393 station Sm station 525 station 516 apttableau with costs 2 11L j t and x indicated my anghthe factory Ir quotm values of f i f Longest Common Subsequence LCS Problem Given sequences x1m and y1n find a longest common subsequence of both Example xABCBDAB and yBDCABA BCA is a common subsequence and BCBA and BDAB are two LCSs Xi and end with xiyj i IX1 X2 Xi1 Ixil Yj IY1 Y2 yjl ijXi Zk Iz1 zzzk1 zkyixi Zk is Zk1 followed by zk yj xi Where Zk1 is an LCS 0f Xi1 and Yj1 and CiDCi1j11 Xi and end with Xi 2 yj i X1 X2 Xi1 Xil IXI X2 Xi1in Y Iy1 y2 yi1 39in lin1 Y2 yi1 yil Zk Iz1 zzzk1 zk yi Zk Iz1 zzzk1 Zk Xi The recurrence equation 0 ifi 00rj 0 Cij Ci 1j 11ifijgtOandxi yj maXCi 1jCij 10therwise Example yj B D C A xj 0 0 0 0 0 A 0 r 0 10 19 L B 0 1 1 1 1 C 0 41 41 a a B 0 1 1 42 42 To find an LCS follow the arrows for each diagonal arrow there is a member of the LCS Dynamic Programming and Greedy algorithm Interval scheduling Input set of intervals on the line represented by pairs of points ends of intervals Output the largest set of intervals such that none two of them overlap Generic greedy solution Consider intervals one after another using some rule 16 Rule 1 Select the interval that starts earliest but is not overlapping the already Chosen intervals Underestimated solution optimal A I algorithm 17 Rule 2 Select the shortest interval but is not overlapping the already Chosen intervals Underestimated solution optimal A r 18 Rule 3 Select the interval intersecting the smallest number of remaining intervals but still is not overlapping the already Chosen intervals Underestimated solution optimal algorithm 19 Rule 4 Select the interval that ends first but still is not overlapping the already chosen intervals 20 Analysis Algorithm gives nonoverlapping intervals obvious since we always choose an interval which does not overlap the previously chosen intervals Let A be the set of intervals obtained by the algorithm Opt be the largest set of painNise non overlapping intervals We show that A must be as large as Opt 21 Analysis Let A A1Ak and Opt B1Bm be sorted By definition of Opt we have k s m Fact for every is k A finishes not later than 8 Proof by induction For i 1 by definition of the first step of the algorithm From i1 to i Suppose that A1 finishes not laterthan B1 From the definition of a single step of the algorithm A is the first interval that finishes after A1 and does not overlap it If Bifinished before A then it would overlap some of the previous A1 A1 and consequently by the inductive assumption it would overlap or end before B1 Which would be a contradiction Bi 1 B A1 L 522 Analysis Theorem A is the exact solution Proof we show that k m Suppose to the contrary that k lt m We already know that Ak finishes not later than Bk Hence we could add Bk1 to A and obtain a bigger solution by the algorithm a contradiction B f BM Ab1 algorithm finishes selection 23 Weighted Interval scheduling Weighted Interval scheduling Input set of intervals with weights on the line represented by pairs of points ends of intervals Output the largest maximum sum of weights set of intervals such that none two of them ovedap 24 Example Greedy algorithm Repeatedly select the interval that ends first but still not overlapping the already chosen intervals Exact solution of unweighted case weight 1 weight 3 weight 1 Greedy algorithm gives total weight 2 instead of optimal 3 25 Basic structure and definition Sort the intervals according to their right ends Define function p as follows 101 0 pI is the number of intervals which finish before ith interval starts weiqht 1 p10 weight 3 p21 weiq ht 2 p30 weight1 p42 26