Analysis of Algorithms
Analysis of Algorithms CS 5633
Popular in Course
Popular in ComputerScienence
verified elite notetaker
This 26 page Class Notes was uploaded by Mireya Heidenreich on Thursday October 29, 2015. The Class Notes belongs to CS 5633 at University of Texas at San Antonio taught by Staff in Fall. Since its upload, it has received 56 views. For similar materials see /class/231391/cs-5633-university-of-texas-at-san-antonio in ComputerScienence at University of Texas at San Antonio.
Reviews for Analysis of Algorithms
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/29/15
Optimization Optimization problems have the form Find a solution minimizing maximizing some value Examples Multiply a sequence of matrices minimbizing the number of multiplications From two strings nd a common subsequence of maximum length Give change minimizing the number of coins Schedule a room to maximize the number of meetings Find a character code to minimize the length of a string Find a spanning tree with the minimum sum of weights Find a path between two vertices of minimum weight Find the smallest set of edges covering all ver tices Dynamic Programming Dynamic programming is a technique for solving some optimization problems A dynamic programming solution to a problem usually involves 1 Characterize the structure of an optimal so lution 2 Recursively de ne an optimal solution in terms of optimal solutions for smaller problems 3 Design an algorithm that computes the opti mal value for each subproblem once 4 Construct an optimal solution Notation Use opt to denote optimal value Use arg to denote optimal parameters Matrix Chain Multiplication Suppose A1 A2 and A3 are matrices of size kxllgtltmandmgtltn A1A2A3 results in klmkmn multiplications A1A2A3 results in mm kln multiplications Structure To perform A1AkAk1An use opti mal solutions for A1 Ak and Ak1An Recursive de nition Let AZ have dimensions pi1 gtlt pi Let optz39 j be the minimum number of multi plications for AZ Aj ifz39 j then optz39j 0 else optz39j ifl grin optz k OthC 173 pi 1pkpjgt Z Algorithm P 0 are the dimensions MATRIXCHAIN ORDERPO n for 2 H 1 to 22 do opt22 H 0 forj H 2 to 22 do for 2 H j 1 downto 1 do opt2j 9 00 for k H 2 to j 1 do q H opt2 k optk 1j P2 1PkPj if q lt opt2j then opt2j H q argiidi H k Construction is the 2th matrix MATRIXCHAIN MULTIPLYA 239 j if239 j then return else X H M C MA 2 arg2j Y H M C MAarg2j 1j return MATRIXMULTIPLYX Y Longest Common Subseqeunce Longest common subsequence LCS of kahijedcdelln and thidysvdquen is hidden An example application is diff Structure Let X 1xmgt andY lty1yngt Let Z 21zkgt be an LCS ofX and Y 11fxmyn then 2k xmyn and Zlk l isanLCSofXlm l and Yln l 21fxm7 yn then zky xm or zky yn soZisanLCSofX1m 1andY orZis an LCS ofX andY1n 1 Recursive De nition Let optm n be the LCS length of 1 mm and 31 yngt if m 0 or n 0 then optm n 0 else if xm yn then optmn 1 optm 1 n 1 else optm n maxltoptltm 1 n optm n 1 Single Source Shortest Paths The single source shortest paths problem is nd ing the shortest path from a source vertex 5 to all other vertices in a weighted graph If all nonnegative weights then Dijkstra s alg If some neg weights then Bellman Ford alg Algs work for directed and undirected graphs Notation Let wu v be the weight of edge u v If p is a path let wltpgt sum of weights on p More Notation Let 65 21 shortest distance from s to 21 Let dM 2 6sv with ds 65 5 0 Let s g 21 stand for shortest path from s to v Key Properties Triangle Inequality If uv is an edge then 65 21 3 65 u wu v pr is a path from u to 21 then 65 21 3 65 u Proof 6sv gt 6su wuv contradicts 6 s de nition So does 65 21 gt 68 u Optimal Subpath Property If u is on 5 RP 21 then 65 21 65 u 6u 21 Proof Let p1 and p2 be the subpaths from s to u and from u to 21 65 u lt wltp1 or 6u v lt wltp2 contradicts 65 21 wltp1 wltp2 Convergence Property If s M u gt v is a short est path then 65 21 65 u wu 21 Proof Follows from the optimal subpath prop erty Path Relaxation Property If dM gt 6sv then some edge xy satis es elm and dy gt dx wx Proof Sorne edge xy on s g 21 must be the rst edge with elm 6sx and dy gt elm wx y 65 3 These properties justify the following procedures INITIALIZESiNGLE SOURGEG s for each vertex v in G do dv 9 oo 7TU H NIL d8 O Initializing to 00 ensures that dv 2 65 21 for all 21 ds 0 ensures that ds 65 5 RELAXu v 10 if dM gt du wu 2 then dv H du wu 2 optional DECREASE KEYQ v dM u H u If du 2 65 u and dM 2 65 21 before RELAX then they remain true afterwards Also if d v gt 65 21 then the Path Relaxation Property implies that some call to RELAX will improve d Dijkstra s Algorithm This assumes weights are nonnegative DIJKSTRAG w s INITIALIZESiNGLE SOURGEG s S Z Q 9 vertices of G using kegM dv while Q is not empty do u H EXTRACTMINQ S S U for each 21 adjacent from u do RELAXu v w Proof of Correctness Basis s is assigned to u ds 0 65 5 Assume For all x E S elm 65 x Show du 65 u when u is extracted Induction Suppose 65 u lt Sorne edge x y in 5 R115 It goes from S to Q dy 65 y because x y has been relaxed but du g dy 6sy 3 65 u lt du contradicts to being extracted instead of y DIJKSTRA is 0E lg V with binary heaps Bellman Ford Algorithm This works with negative weights FALSE is re turned if a negative cycle is detected BELLMAN FORDG w s INITIALIZESINGLE SOURCEG s forz lt 1toV 1 do for each edge u v in G do RELAXu v w for each edge u v in G do if dM gt dM wu 1 then return FALSE return TRUE Proof of Correctness All nite shortest paths have 3 V 1 edges The 2th iteration relaxes ith edge in the path If shortest path is nite then after V 1 iter ations dM 65 21 If there is an in nite shortest path then dM gt du wu v for some edge u v BELLMAN FORD is 0VE Difference Constraints A difference constraint is xj xi 3 bk where xi and xj are variables and bk is a constant Difference constraints can represent time rela tionships between events If x2 must occur within 2 hours after m then x2 2 3 x1 If x2 must occur at least 2 hours after x1 then x2 2 2 x1 The triangle inequality for shortest paths is a difference constraint 65 21 3 68 uwu v is equivalent to 65 21 65 u g wu v A set of difference equations xj xi 3 bk can be reduced to a weighted graph by cowl vj bk and ws vj ws vi 0 There is a solution for single source shortest paths if and only if there is a solution to the difference equations All Pairs Shortest Paths The all pairs shortest paths problem is nding the shortest path for each pair of vertices Algs for this problem can be adapted for transitive closure Let 62 j m be the shortest length from 239 to j using 3 m edges 0 iii j 6ij 1 wij if ij is an edge 00 otherwise 6a j m nal k mgt 6c j mgtgt This recursive de nition is correct Basis Equation for 62 j 1 is correct Assume 62 j m is correct Show Equation for 62 j 2m is correct Induction Optimal path of 3 2m edges consists of two optimal paths of g m edges All Pairs Shortest Paths ALLPAIRSG w n 9 number of vertiees in G D 9 an n x n matrix initialized to 62 j 1 m H 1 while m lt n 1 do EXTENDD m 9 2m return D EXTENDltD1n1 n forz3991t0nd0 forj H1t0nd0 for k H1t0 n d0 ALLPAIRS is 0V3 1g V Floyd Warshall Algorithm FLOYD WARSHALLG w n 9 number of vertiees in G D 9 an n x n matrix initialized to 6i j 1 for k H 1 to n do for i H 1 to n do forj H 1 to n do Dij H minDij Di k Dkj return D Let Mi j k be the shortest distance from i to j with all intermediate vertiees g k Basis Dij g Mij 0 due to initialization Assume Di j 3 Mi j 6 1 before kth iteration Show Di j 3 Mi j 16 after kth iteration Induction Either Mij k Mij k 1 or k7 FLOYDWARSHALL is 003 Weighted Graphs A weighted graph is a graph in which each edge uv has a weight wuv Each weight is a real number Weights can represent distance cost time capacity etc Optimization Problems for Weighted Graphs Find a minimum spanning tree Find shortest paths between vertices Maximize ow from a source to a sink Traveling salesman problem Variations on Problems Undirected directed graphs Negative weights Minimum Spanning Trees A spanning tree T of a graph G is a subset T of the edges that form a free tree If G has V vertiees then T has V 1 edges A minimum spanning tree MST is a spanning tree with a minimum sum of weights Consider any partition of vertiees V1 and V2 Let E be the edges between V1 and V2 Theorem MST has a min wgt edge from El Proof Suppose T is a MST with no such edge Let u v be a min wgt edge from E T has a path between to and 21 Some edge x y on this path is in E Replacing x y with u v is better Kruskal s Algorithm MST KRUSKALG w T H Z for each vertex v in G do MAKE SETltUgt for each edge u v in ascending order do if FINDSETu 7 FIND SETltUgt then T H T U u 21 UNIONu 21 exit loop if all vertioes are unioned return T Proof of correctness u v is a minimum weight edge between as set and other vertioes Use disjoint set forest for union nd almost Use 0E lg E sorting algorithm or binary heap MSTKRUSKAL is 0Elg E 0Elg V Lower Bounds for Comparison Sorting Sorting returns a permutation of its input There are n permutations of n elements ai g aj determines if ai is before after aj ai g aj chooses between two sets of permuta tions Map to a binary decision tree Map each comparison to a node in a tree Map sets of permutations to subtrees Map singleton sets to leaves A binary tree with height b has 3 2h leaves A binary tree with n leaves has h 2 lgn lgn E n lg n so h E Qltnlg Worst case of comparison sorting is Mn lg 3 2d leaves at depth 3 d if d lt lgn 1 then 2d lt nlQ 2 Til2 leaves have d 2 lgn 1 Average case of comparison sorting is Mn lg COUNTING SORT is n k and stable It assumes that each AU 6 1 2 COUNTING SORTA B k C lt an array of k zeros forj lt 1 to lengthA do 01141211 e 0114121 1 D C is the number of elements equal to 2 for 239 lt 2 to k do lt Cz 1 D C is the number of elements 3 2 forj lt lengthA downto 1 do 191011412111 e Am 01141211 e 01141211 1 lt3 2 1 2 1 after rst loop 1 3 after second loop B D D2 D C 124 B 1 D2 D C 024 8 122n 0 014 B 12 23 0 013 RADiX SORT is dn k It assumes that each value has d digits Each digit has one of k values RADiX SORTA d for 239 H 1 to d do use COUNTING SORT to sort A on digit 239 238 230 230 045 796 934 934 230 756 045 537 238 045 gt 796 gt 238 gt 537 537 756 045 756 230 537 756 796 934 238 796 934 T T T Assuming k is 0n RADIX SORT will outper form n lg n if d is 01g Direct Address Tables Let U 0 m 1 be the set of possible keys Use array T 0 m 1 as a direct address table There is a 1 1 correspondence between keys and slots DIRECTADDREssSEARCHT k return TVs DIRECT ADDREssINSERTT51 Tikeyiwii lt CC D1RECT ADDRESS DELETET k Tkeyx lt NIL Advantage operations are 91 Disadvantage U space required Hash Tables Let K be the set of keys to be stored Goal use K space and 91 timeop Idea Use array T0 m 1 as a hash table and use a 91 hash function h where h U gt 0 m l maps from keys to slots A collision is when two keys map to the same slot Good Hash Functions Division method k mod m m is prime not close to any 2 Division variation k mod mod m M is a big prime not close to any 2 m is any number much smaller than M Multiplication method mod 1 m is a power of 2 A 12 Horner s Method for Division Hash Function If k km kW and ifO g lt 7 then compute hash function by h 9 km mod m for 239 H 2 to l do h 9 Th mod m Universal Hashing Let H be a set of hashing functions H is universal if Mk with prob lm m is a prime number k ltk1klgt where 0 g lt m Assign am 9 RANDOMO m 1 am gtllt rnod m The set of possible functions is universal Mk with prob lm If y 16 am gtIlt k rnod m has equally likely results Chaining ln chaining slots are linked lists of the elements that hash to that slot ie collisions Consider m slots n elts load factor 04 n m Worst case n if all elts hash to same slot Best case 1 04 each slot has 04 or 04 Average case Assume each slot is equally likely Unsuccessful search 1 04 This is because average slot length oz Successful search 1 04 Before ith elt inserted avg length 1 m Expected position of 2th elt 1 Expected search length is the summation 21 n elements to search for 171 Prob for 2th element is 171 1 1 m Expected position of 2th elt n l i 1 Oz 1 Z 21 TL Open Address Hashing ln open addressing when a collision occurs probe for an empty slot and insert the new elt there The hash function becomes h2Ugtlt 0m 1 gt0m 1 The probe sequence Mk 0 Mk m 1 should include all the slots HASHINSERTT cc for 239 H 0 to m 1 doj H Miterltd i if TU NIL then TU H X returnj error hash table overflow HASH DELETE marks the slot as deleted HASH SEARCH must continue past deleted slots HASH INSERT can put new elts in deleted slots Uniform Hashing Analysis Uniform hashing assumes each probe sequence is equally likely Unsuccessful Search Let pi prob exactly 239 probes nd full slots Let qi prob rst 239 probes nd full slots pi Qt Qi1 q1nmozandq2gtltmgt lt04 z ln k Sngtii Average number of probes is 1 1 04 n n 00 2 12 ZP 1Z CHE 2 06 z1 21 20 Successful Search 9 ln Inserting ith elt unsuccessful search i 1 elts Average number of probes is l n1 i 1m 1 1 g ln 04 1 04 n 2 21