### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Analysis Of Algorithms CS 3343

UTSA

GPA 3.55

### View Full Document

## 26

## 0

## Popular in Course

## Popular in ComputerScienence

This 222 page Class Notes was uploaded by Mireya Heidenreich on Thursday October 29, 2015. The Class Notes belongs to CS 3343 at University of Texas at San Antonio taught by Staff in Fall. Since its upload, it has received 26 views. For similar materials see /class/231393/cs-3343-university-of-texas-at-san-antonio in ComputerScienence at University of Texas at San Antonio.

## Reviews for Analysis Of Algorithms

### 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: 10/29/15

cs 3343 Spring 2009 ALGDRlTHMS Dynamic Programming Carola Wenk Slides courtesy of Charles Leiserson with small 3mm changes by Carola Wenk c fidiAmlym 17 ng Dynamic programming u I Algorithm design technique I A technique for solving problems that have I overlapping subproblems I and when used for optimization have an optimal substructure property I Idea Do not repeatedly solve the same subproblems but solve them only once and store the solutions in a dynamic programming table 3mm 5 liAmlym army th Example Fibonacci numbers I F00 Fll FnFn1Fn2 for n 2 2 I Implement this recursion naively Solve same subproblems F n I Fnl Fn2 many times I Fol 2 Fol 3 Fol 3 Fn 4R1mtlmels exponential in n I Store 1D DPtable and ll bottomup in 001 time 3mm c fidiAmlym 17 ng Longest Common Subsequence Lu Example Longest Common Subsequence LCS I Given two sequences xl m and yl n nd a longest subsequence common to them both a not the x A B C B D A B BCBA y B D c A B A mm mctional notation but not a function 3mm 5 liAmlym army th M Bruteforce LCS algorithm Check every subsequence ofxl m to see ifit is also a subsequence ofyl 14 Analysis 2 subsequences of x each bitvector of length m determines a distinct subsequence of x Hence the runtime would be exponential 31709 assummtym 112341517 th s Towards a better algorithm TwoStep Approach 1 Look at the length of a longestcommon subsequence 2 Extend the algorithm to nd the LCS itself Notation Denote the length of a sequence s by s Strategy Consider pre xes of x and y De ne cij LCSx1 iyl j 39 Then cm n LCSx y 31709 minimum 11234197 th Recursive formulation Theorem Cli 1j 1l1 ifxlil yD39l CD J T maxciilj cijil otherwise Proof Case xi yU l 2 x Let zl k LCSxl iyl j where cij k Then zk xi or else 2 could be extended Thus zl kil is CS ofxl 13971 andyl jil Cs AmlqufAlgamhm 7 V Proof continued Claim zl kil LCSxl zgt1y1 141 Suppose w is a longer CS ofx l 13971 and yl jil thatis w gtkil Then cut and paste w H zk w concatenated with zk is a common subsequence ofxl i and yl j with lw H zk gt k Contradiction proving the cl 39 Thus ciiljil kil which implies that cij ciiljil 1 Other cases are similar I 31709 minimum 11234197 th Dynamicprogramming 39N hallmark 1 Optimal substructure An optimal solution to a problem instance contains optimal solutions to subproblems Retulrente Ifz LCSx y then any pre x ofz is an LCS ofa pre x ofx and a pre x ofy 31709 mummy mtg th LCSOC y Lj if xi yj then cij lt LCSxy iilj71 1 else cij lt max LCSxy i71j LCSan 114 Worstcase xi yj in which case the 39thm evaluates two subproblems each with only one parameter decremented 31709 Cs tmmlym qulgrmhm Recursive algorithm for LCS Recursion tree Height m n gt work potentially exponential but we re solving subproblems already solved 31709 mummy mtg th u 39 Dynamicprogramming hallmark 2 Overlapping subproblems A recursive solution contains a small number ofdistinct subproblems repeated many times The number of distinct LCS subproblems for two strings of lengths m and n is only mn 31709 Cs tmmlym qulgrmhm FE There are two variants of dwamic programming 1 Memoization 2 Bottomup dynamic programming o en referred to as d3mamic programming 31709 mmmtm 112341517 th 1Mquot Dyn amicprogr amming Memoization LCSxy76 6i6 75 5 634 45 54 53 31709 mmmtm 112341517 th Nd Memoization algorithm Memnizatinn A er subprobl computing a solution to a em store it in a table Subsequent ca s check the table to avoid redoing Wor for all ij ci00 and c0j0 LC y 11139 if ci j NIL then ifxi y39 then cij ltLCSxy i71j71 1 else cij e maxLCSx y i71j same LIX LCSx y 139 171 before Time mn constant workper table entry Space mn 31709 mmmtm 11234197 th 31709 Recursive formulation 7 ci71 j711 ifxiyf Clhjl maxci71j ciJ1 otherwise mmmtm 11234197 th CS 3343 Fall 2007 ALGORiTHMs 1x P and NP Carola Wenk Slides courtesy of Piotr lndyk with small changes b nk nusm c iidemlym 17 ng l nusm Have seen so far Algorithms for various problems 7 Running times OnmzOnZ On log n On etc 7 Le polynomial in the input size Can we solve all or most of interesting problems in polynomial time Not really CS lfAnalym army th Example dif cult problem Traveling Salesperson Problem TSP 7 Input undirected graph with lengths on edges 7 Output shortest tour that visits each vertex exactly once Best known algorithm On 2 time nusm c iidemlym 17 ng nusm Another dif cult problem Clique 7 Input undirected graph VaE 7 Output largest subset C of V such that every pair ofvertices in C has an edge between them Best known algorithm On 2 time CS lfAnalym army th What can we do Spend more time designing algorithms for those pro lems 7 People tried for a few decades no luck Prove there is no polynomial time algorithm for those pro ems 7 Would be great 7 Seems really dif cult 7 Best lower bounds for natural problems Qn2 for restricted computational models 45n for unrestricted computational models 111 517 Us 5555 Analysx afAtgamm What else can we do 0 Show that those hard problems are essentially equivalent Ie if we can solve one of them in polynomial time then all others can be solved in polynomial time as well 0 Works for at least 10 000 hard problems 1115n7 Us 5555 Analyn afAlganthm The bene ts of equivalence Combines research e orts If one problem has polynomial time P1 solution then all of them do P2 More realistically Once an exponential lower bound is shown for one problem it holds for all of them P3 111 517 Us 5555 Analysx afAtgamm 1115n7 Summing up If we show that a problem H is equivalent to ten thousand other well studied problems without ef cient algorithms then we get a very strong evidence that H is hard We need to 7 Identify the class of problems of interest 7De ne the notion of equivalence 7 Prove the equivalences Us 5555 Analyn afAlganthm Class of problems NP Decision problems answer YES or NO Eg is there a tour of length S K Solvable in non deterministic polynomial time 7 Intuitively the solution can be veri ed in polynomial time 7 Eg ifsomeone gives us a tour T we can verify in polynomial time if T is a tour of length S K Therefore TSP is in NP 111sn7 Us 5555 Analysx afAtgamm Formal definitions of P and NP A decision problem H is solvable in polynomial time or HEP if there is a polynomial time algorithm A such that for any input X HXYES iff AXYES A decision problem H is solvable in non deterministic polynomial time or HENP if there is a polynomial time algorithm A such that for any input X HXYES iff there eXists a certi cate y of size polyX such that AXyYES 1 11sn7 Us 5555 Analyn afAlganthm 1n Examples of problems in NP Is Does there eXist a clique in G of size 2K in NP Yes AXy interprets X as a graph G y as a set C and checks if all vertices in C are adjacent and if C EK Is Sorting in NP No not a decision problem Is Sortedness in NP Yes ignore y and check if the input X is sorted 111sn7 Us 5555 Analysx afAtgamm 11 Reductions H to H YES X NO YES X a a a NO 1 11sn7 Us 5555 Analyn afAlganthm 1z Reductions H to H nusD7 CSKilfAmlly ifAlgpvvhm u s n Reductions quotquot quot A fur Fl I H ispolynomial time reducible to H 1T 5 H iff there is a polynomial time function f that maps inputs X for H into inputs x for H such that for any X H X FHKX I Fact 1 ifHeP andH S chenH eP I Fact 2 ifHeN39P and 1T 5 H then H EN39P I Fact 3 transitivity iflT 11 and 11 SchenH 5H nusD7 CS lfAmlym 19mm to Recap I We de ned a large class ofinteresting problems namely N I We have a way of saying that one problem is not harder than another If g H I Our goal show equivalence between hard problems nusD7 CSKilfAmlly ifAlgpvvhm Showing equivalence between dif th problems Options TS 7 Show reductions between all pairs ofproblems 7 Reduce the number of refdultctions using transitivity 0 7 P Clique nusD7 CS lfAmlym 19mm 15 Showing equivalence between dif th problems Options TS 7 show reductions between all m pairs ofproblems C ique 7 Reduce the number of refductions using transitivity 0 w 7 Show that all problems in N are reducible to a Med p3 p4 To showthat some V problem new 39s equiwlent A 0 H P t all di icult oblemswe 5 only shown 5 1T Husm cmumlym our th l7 The rst problem H Satis ability problem SAT 7 Given a formula p with m clauses over n variables eg leXZvXS x3 v axis 7 Check if there exists TRUEFALSE assignments to the variables that makes the formula satis able Husm CS lfAmlym 19mm IE Cliquc TS SAT is NP complete SAT Fact SAT ENP P3F4 Theorem Cook 7l For any H ENP M i we have H S SAT n P39 De nition A problem H such that for any H ENP we have H S H is called NPhard De nition An NPhard problem that belongs to NP is called NPcomplete Corollary SAT is NPcomplete Husm cmumlym our th 19 Plan of attack SAT Clique thanks Steve 3 Independent set Follow from Cook39s Theorem Vertex cover Conclusion all of the above problems are NP complete nusm mummy 197nm m Clique again Clique decision variant 7 Input undirected graph GVE K 7 Output is there a subset C of V lClZK such that every pair ofvertices in C has an edge between them nusD7 CS lfAmlym ifAlgpvvhmt SAT 5 Clique reduction For each literal t occurring in p create a Create an edge vL 7 vv iff 7t and t are not in the same clause and 7 t is not the negation of t nusD7 CS liAmlym ifAlgpvvhmt SAT 5 Clique I quot Amrl39 A39 for H x x H Given a SAT formula pC1Cm over X1 xn we need to produce G7VE and K H4 fx such that p satis able iffG has a clique of size 2 K Notation a literal is either X or x nusD7 assume 19mm An SAT 5 Clique example in the same clause and IS not the negation oft Formula xlvxzwx3 pxzvpxp pxl vXZ Graph Claim p satisfiable iffG has a clique of size 2 m nusD7 CS liAnalym 19mm u e Proof Edge VL 7 Vt ltgt t and t are not in the same clause and t is not the negation of t 1115u7 gt pan 7 Take any assignment that satis es 1 Eg X1F X2T X3F 7 Let the set C contain one satis ed literal per clause 7C is a clique Us 5555 Analysx afAtgamm zs Proof t and t are not in the same clause and t is not the negation of t Edge Vt 7 Vt ltgt H pan 7 Take any clique C of size 2 m ie m 7 Create a set of equations that satis es selected literals Eg X3T X2F X1F 7 The set of equations is consistent and the solution satis es q 1 11sn7 Us 5555 Analyn afAlganthm za 1115u7 Altogether We constructed a reduction that maps 7 YES inputs to SAT to YES inputs to Clique 7N0 inputs to SAT to NO inputs to Clique The reduction works in polynomial time Therefore SAT S Clique gtClique NP hard Clique is in NP gt Clique is NP complete Us 5555 Analysx afAtgamm 27 Independent set IS 0 Input undirected graph GVE Output is there a subset S of V lSlEK such that no pair of vertices in S has an edge between them 1 11sn7 Us 5555 Analyn afAlganthm 28 Chapter 2 Fundamentals of the Analysis of Algorithm Efficiency Matrix Multiplication 16 Number of Bits in an Integer 17 Mathematical Analysis of Recursive Algorithms 18 Plan for Analyzing Recursive Algorithms 18 Factorial Function 19 Recurrence for Factorial Function 20 Solving the Factorial Recurrence 21 The first rule of any technology used in a busi Towers of Hanoi Algorithm 22 Recurrence for Towers of Han0i 23 Solving the Towers of Hanoi Recurrence 24 ness is that automation applied to an efficient operation will magnify the efficiency The sec Number of Bits in an Integer 25 0nd is that automation appied to an inef cient Recurrence for BitCount Function 26 Solving the BitCount Recurrence operation Will magnify the inefFICIency Bill Gates Recurrence for Fibonacci Function 29 Approximating the Fibonacci Recurrence 30 Empirical Analysis of Algorithms 31 Plan for Empirical Analysis of Algorithms 31 Empirical Analysis of UniqueElements 32 Analysis Framework 2 Results of Empirical Analysis Comparisons 33 Analysis of Algorithms 2 ReSUItS 0f Empirical AnalYSiSi Timings 34 Efficiency as a Function of Input Size 3 Algorithm Visualization 35 Measuring Running Time 4 V i is AI h 35 isua ization o orting gorit ms worstbestaverage 5 Asymptotic Notation 6 Order of Growth 6 Asymptotic Order of Growth 7 Illustration of Asymptotic Order 8 Examples of Asymptotic Order 9 Properties of Order of Growth 10 Basic Asymptotic Efficiency Classes 11 Mathematical Analysis of Nonrecursive Algorithms 12 Plan for Analyzing Nonrecursive Algorithms 12 Useful Summation Formulas and Rules 13 Finding the Maximum 14 Element Uniqueness 15 1 AnalySIs Framework Measuring Running Time Analysis of Algorithms Analyze time efficiency by D identifying the basic operations the operations contributing the most to D lssueS running time D characterizing the number of times it is performed as a function of input size We can crudely estimate running time by Tn cap as Cn r Correctness Is the algorithm correct 7 Time Efficiency How much time does the algorithm use 7 Space Efficiency How much extra space in addition to the space needed for the input and output does the algorithm use D T01 runn39ng me 35 a funCtlon 0f 71 D Approaches D cop running time of a single basic operation D Cn number of basic operations as a function of n 7 Theoretical Analysis Proof of correctness and bigOh and related CS 3343 Analysis ofAlgorithms Chapter 2 Slide 7 4 notations 7 Empirical Analysis Testing and measurement over a range of instances CS 3343 Analysis ofAlgorithms Chapter 2 shde a 2 worSt39Casev BeSt39Casev and Average case algorithm SequentialSearcMAlOn 7 1K Searches for a value in an array Input An array A and a search key K Output The index where K is found or 71 forilt0ton71do 7 if K then return i Analyze effICIency as a function of nisize ofinput return 71 Efficiency as a Function of Input Size Typically more time and space are needed to run an algorithm on bigger inputs eg more numbers longer strings larger graphs D Searchingsorting nnumber of items in list D String processing n length of strings D Matrix operations n dimension of matrix n x n matrix has n2 elements D Graph processing nV number of vertices and nE number of edges Basic Operation The comparison in the loop WorstCase n comparisons BestCase 1 comparison AverageCase n12 comparisons assuming each element equally likely to be searched llllllll CS 3343 Analysis ofAlgorithms Chapter 2 Slide 7 3 CS 3343 Analysis ofAlgorithms Chapter 2 Slide 7 5 Asymptotic Notation Order of Growth the order ofgrowth often some simple function such as TABLE 21 Values some approximate of several functions important for analysis of algorithms n logz n n n logz n n2 n3 2 n 10 33 101 33101 102 103 103 36106 102 66 102 66102 104 106 131030 9310157 103 10 103 10104 106 109 104 13 104 13105 108 1012 105 17 105 17106 1010 1015 106 20 106 20107 1012 1018 CS 3343 Analysis of Algorithms Typically the basic operation count can be approximated as cgn where gn is Chapter 2 Slide 6 Illustration of Asymptotic Order 20 n 3 sin n 2n q 39 IIII E III o E O 39 3913 Q E III LB 5 0 0 5 10 15 20 n Graph suggests and we can prove n Ssinn is 0n n Ssinn g 2n when n 2 3 n Ssinn 2 712 when n 2 6 CS 3343 Analysis of Algorithms Chapter 2 Slide 8 Asymptotic Order of Growth D Big Oh Ogn functions g cgn tn E Ogn if there are positive constants c and no such that tn g cgn for all n 2 n0 D Big Omega functions 2 cgn tn E if there are positive constants c and no such that tn 2 cgn for all n 2 n0 D Big Theta gn functions m cgn Both tn E Ogn and tn E CS 3343 Analysis of Algorithms A way of comparing functions that ignores constant factors and small input sizes Chapter 2 Slide 7 Examples of Asymptotic Order 750 00 0012 0013 90709012 9013 log2 n T T T F F F ton 5 T T T T F F nn 12 F T T T T F n 13 F F T T T T 2 F F F T T T For example 1071 5 is Assuming n 2 5 10n5 E 0n because 10n5 g 10nn 1171 10m 5 E because 1071 5 2 1071 CS 3343 Analysis of Algorithms Chapter 2 Slide 9 Properties of Order of Growth D If f1n is order 91n and f2n is order 9271 then f1n f2n is order mw91n192n D If I gt 1 then logbn E logn D Polynomials of degree 10 E nk that is aknk akzlnk 1ag E D Exponential functions aquot have different orders of growth for different as D order logn lt order n where k gt 0 lt order aquot where a gt 1 lt order n lt order 71quot CS 3343 Analysis ofAlgorithms Chapter 2 5w 10 Mathematical Analysis of Nonrecursive Algorithms 11 Plan for Analyzing Nonrecursive Algorithms D Decide on parameter 71 indicating input size D Identify algorithm s basic operations D Determine worst average and best cases for input of size n B Set up a sum for the number of times the basic operation is executed D Simplify the sum using standard formulas and rules see Appendix A cs 3343 Analysis ofAlgorithms Chapter 2 5m 12 Basic Asymptotic Efficiency Classes Class Name Example 1 constant access array element logn logarithmic binary search 71 linear find median nlogn n lognquot mergesort n2 quadratic insertion sort 713 cubic matrix multiplication aquot exponential generating all subsets n factorial generating all permutations cs 3343 Analysis ofAlgorithms Chapter 2 5w 11 Useful Summation Formulas and Rules a 1111n69n 11 7 n1 2 E 1 2 9 D Hz 7 2 E n quot k1 41 k an k1 D 11 12 n k1En D E al1aaquota 1 aquot a 1 11 D Znaibzialiibz icmciaz 11 11 11 11 11 cs 3343 Analysis ofAlgorithms Chapter 2 5m 13 Finding the Maximum algorithm MazElemenKAlOHn7 1 Returns the maximum value in an array Input A nonempty array A of real numbers Output The maximum value in A mazch lt7 AlO forilt71ton71do if gt maxval then maxch lt7 return mazval Basic Operation comparison in loop 1171 Performs E 1 n 71 comparisons 11 cs 3343 Analysis ofAlgorithms Chapter 2 Shae s 14 Matrix Multiplication algorithm Mctm39cMultz39plgA7 B n gtlt nmatrices Multiplies matrix A times matrix B Input Two n gtlt n matrices A and B Output Matrix 0 AB forilt70ton71do forjlt70ton71do Clij lt7 0 forklt70ton71do 011117 01M Mime e 131le return 0 Basic Operation inner loop multiplications 7271 7271 7271 Performs n3 multiplications 10 30 160 cs 3343 Analysis ofAlgorithms Chapter 2 Shae s 15 Element Uniqueness algorithm UniqueElementsA011n 7 1 Returns true if all elements are different lnput An array A Output Returns true if there are no duplicates for i lt7 0 to n 7 forjlt7i1ton71do if Alj then return false return true D Basic Operation inner loop comparison D BestWorst Case from 1 to nn7 12 ghet1he1he2 1Ehhn712 61 10 CS 3343 Analysis ofAlgorithms Chapter 2 Shde 7 15 Number of Bits in an Integer algorithm BitCounKm lnput A positive integer m Output The number of bits to encode m count lt7 1 while m gt 1 do count lt7 count 1 m lt7 return count n length of m in bits Basic Operation The division by 2 in loop Performs n 7 1 operations because n count cs 3343 Analysis ofAlgorithms chapter 2 shde a 17 Mathematical Analysis of Recursive Algorithms 1s Plan for Analyzing Recursive Algorithms D Decide on parameter n indicating input size D Identify algorithm s basic operations D Determine worst average and best cases for input of size n B Set up a recurrence relation expressing the basic operation count D Solve the recurrence at least determine its order of growth cs 3343 Analysis ofAlgoritlwms Chapter 2 Slide 7 1s Factorial Function algorithm FactoriaKn Computes n recursively Input A nonnegative integer n Output The value of n if n 0 then return 1 else return Facton39aln 7 1 7 n Input Size Use number n actually n has about log n bits Basic Operation multiplication CS 3343 Analysis of Algorithms Chapter 2 Slide 7 19 Recurrence for Factorial Function B Let multiplication count to compute Facto rialn D M0 0 because no multiplications are performed to compute Facton39aKO D If n gt 0 then Facton39aKn performs recursive call plus one multiplication Mn7 1 1 to compute to multiply Factorialw 7 1 Factorialw 7 1 by n CS 3343 Anaiysis ofAlgoritlwms Chapter 2 Slide 7 2o Solving the Factorial Recurrence Make a reasonable guess D Forward substitution M1 M0 1 1 M2M112 M3M213 D Backward substitution Mn7 1 1 Mn7211Mn722 Mn7312Mn733 Prove n by mathematical induction D Basis if n 0 then M0 0 n D Induction ifMn71 n71 then MnMn711n711n cs 3343 Analysis ofAlgoritlwms Chapter 2 Slide 7 21 Towers of Hanoi Algorithm algorithm Towersnij Moves n disks from peg i to pegj Input Integers n gt 01gm39g 3 i j Output Specifies disk moves in correct order if n 1 then move disk 1 from peg i to pegj else T0wersn71i67i7j move disk n from peg i to pegj T0wersn7 17 671397j7 j Input Size Use number n Basic Operation moving a disk cs 3343 Analysis ofAlgorithms Chapter 2 siida7 22 Recurrence for Towers of Hanoi Number of Bits in an Integer B Let move count to compute Towe39rsn7 algorithm BitCoumKn D M1 1 because 1 move is needed for Towe39ns 7 I t A t t npu posI Ive In eger n D If n gt 1 then Towe39rsn7 performs 2 recursive calls plus one move output The number of bits to encode n if m 1 then return 1 MW ZMW 1 1 else return BitCoumK 1 to compute to move T01UETSH1 3 dusk n Input Size Use number n actually n has about log n bits tWICE Basic Operation division by 2 cs 3343 Anziysis ofAigorithms Chapter 2 Shd27 25 cs 3343 Anziysis ofAigorithms Chapter 2 Shd27 23 Recurrence for BitCount Function Solving the Towers of Hanoi Recurrence B Let Dn ClIVISIOn count to compute thCountn Make a reasonable guess Forward substitution M2 2M11 3 M3 2M21 7 M42M3115 DnD1n21 1 Backward substitution 2Mn71 1 to compute to compute 22Mn 7 2 1 1 4Mn 7 2 3 Bz tComthnQj W2 42Mn731 2 8Mn737 Prove 2quot 71 by mathematical induction D D1 0 because no divisions are performed to compute BitCount El D If n gt 1 then BitCoumKn performs recursive call on plus one division El cs 3343 Anziysis ofAigorithms Chapter 2 5m 7 25 D Basis ifn1then Mn12quot71 D Induction if Mn7 1 2quot 171 then Mn2Mn711272quot 17112quot7212quot71 cs 3343 Anziysis ofAigorithms Chapter 2 5m 7 24 Solving the BitCount Recurrence Make a reasonable guess using powers of 2 D Forward substitution D2 D1 1 1 D4 D21 2 D8 D41 3 D Backward substitution Dn Dn2 1 Dn4 1 1 Dn4 2 Dn8 1 2 Dn8 3 Prove D2k k by mathematical induction D Basis if k 0 then D2k D1 0 k D Induction ifD2k 1 k 71 then D2k D2k 11k 711 10 C5 3343 Analysis ofAIgorithms Chapter 2 Shda a 27 Recurrence for Fibonacci Function El Let An addition count to compute El 241 240 0 because no additions are performed to compute F0 or D If n gt 1 then performs two recursive caIIs plus one addition An An71 An7 2 1 to compute to compute to add Fn 71 Fn 71 Fn 7 2 and Fn 7 2 CS 3343 Analysis ofAIgorithms Chapter 2 SI1d27 2g Fibonacci Function algorithm Computes nth Fibonacci number recursively Input A nonnegative integer n Output The nth Fibonacci number ifn 0 or n 1 then return n else return Fn 7 1 Fn 7 2 Input Size Use number n actually n has about log n bits Basic Operation addition in else statement CS 3343 Analysis ofAIgorithms Chapter 2 SI1d27 28 Approximating the Fibonacci Recurrence Make a reasonable guess at a lower bound D Forward substitution 242 1 243 2 244 4 245 7 246 12 D Backward substitution AnAn71An721 An72An731 An7 21 2An7 2An732 Prove An Z 2quot when n 2 4 D Basis True for 244 and 245 D Induction An 2An 7 2 An 7 3 2 gt 2An 7 2 2 2 e 2W2 2 C5 3343 Analysis ofAIgorithms Chapter 2 Shda a 30 Empirical Analysis of Algorithms at Plan for Empirical Analysis of Algorithms Understand the experiments purpose D D Decide on the metric M and the measurement unit D Decide on characteristics of input D Prepare program implementing algorithms and generating a sample of inputs D Run the algorithms on the sample and record the data D Analyze the data CS 3343 Anzlysls ofAlgorlthms Chapter 2 Sllda e 31 Empirical Analysis of UniqueElements D Analyze UniqueElements comparing arrays with unique elements vs one duplicate D Measure number of comparisons on different input sizes from 50 to 1000 by 50 D For arrays with a duplicate randomly choose a pair of positions that will have the same value Also run 10 times for each input size D Prepare UniqueElementsExperiment java D Run program record data and create graph D Analyze the data CS 3343 Anzlysls ofAlgorlthms Chapter 2 Sllda e 32 Results of Empirical Analysis Comparisons 500000 No Duplicates One Duplicate x 400000 300000 200000 Number atCampansans gtlt 100000 0 0 200 400 500 800 1000 n D No duplicates line is nn712 B One duplicate line is least squares fit resulting in 024s n2 17s n7 2042 n24 D Predict Half the time with one duplicate CS 3343 Anzlysls ofAlgorlthms Chapter 2 Sllda e 33 Results of Empirical Analysis Timings NoDuphcates One Duplicate gtlt 0 200 400 500 300 1000 D No duplicates and one duplicate lines are 70037 00016 s n 84 x 106 s n2 70073 000047 s n 52 x 106 s n2 CS 3343 Anzlysls ofAlgorlthms Chapter 2 Sllda e 34 CS 3343 Spring 2009 Have seen so far ALGORiTHMs Algorithms for various problems 7 Running times 0nmzOnZ On log n V On etc 7 Le polynomial in the input size P and NP Can we solve all or most of interesting 9 Carola Wenk eroblegls in polynomial time Slides courtesy of Piotr lndyk with small changes 0t re y39 quot b nk M2er ErmiAmwwugmm 1 mm cummwmmm Example dif cult problem Another dif cult problem Traveling Salesperson Ch39que Problem TSP 7 Input Undirected graph with lengths on edges 7 Output Shortest tour that visits each vertex 7 Input Undirected graph CHIE 7 Output Largest subset C of V exactly once C is called a clique Best known algorithm Best known algorithm On 2 time On 2 time mm c iidemlym 17 ng 3 mm c lfAmlym army th What can we do What else can we do Spend more time designing algorithms for those 0 Show that those hard problems are problems 7 People tried for a few decades no luck essentially eqmvalent39 i39equot1fwe can SOlve Prove there is no polynomial time algorithm for one Of them In pOIymm1a1 t1me ther all those pro lems others can be solved 1n polynom1al t1me as 7 Would be great well seems really dlf cult Works for at least 10 000 hard problems 7 Best lower bounds for natural problems 2012 for restricted computational models 4511 for unrestricted computational models 421u5 cs 5555 Analysx afAgamm 5 421u5 cs 5555 Analyn afAgamhm The bene ts of equivalence Summing up Combines research If h h b1 H 1 e orts we s owt at a pro em 1s equ1va ent If one problem has to ten thousand other well studied problems polynomial time P1 w1thout ef c1ent algonthmsthen we get a solution then all of very strong ev1dence that H 1s hard them do P2 0 We need to More realistically Once an exponential 7Ident1fy the class of problems of 1nterest lower bound 5 Show 7De ne the notion of equivalence for one problem it holds for all of them P3 7 Prove the equ1valences 421u5 cs 5555 Analysx afAgamm 7 421u5 cs 5555 Analyn afAgamhm Class of problems NP Decision problems answer YES or NO Eg is there a tour of length S K Solvable in non deterministic polynomial time 7 Intuitively the solution can be veri ed in polynomial time 7 Eg ifsomeone gives us a tour T we can verify in polynomial time if T is a tour of length S K Therefore the decision variant of TSP is in NP 42115 Us 5555 Analysx afAtgamm 5 Decision problem vs optimization problem 3 variants of Clique 1 Input Undirected graph GVE and an integer k2 0 Output Does G contain a clique ofC such that C 2 k Input Undirected graph GVE Output Largest integer k such that G contains a clique C with CFk Input Undirected graph GVE Output Largest clique C of V 3 is harder than 2 is harder than 1 So ifwe reason about the decision problem 1 and can show that it is hard then the others are hard as well Also every algorithm for 3 can solve 2 and 1 as well 42119 Us 5555 Analyrx afAlganthm 1 n Decision problem vs optimization problem cont Theorem a If1 can be solved in polynomial time then 2 can be solved in polynomial time b If2 can be solved in polynomial time then 3 can be solved in polynomr me Proof a Run 1 for values 15111 Instead of linear search one could also do binary search b Run 2 to nd the size keptofalargest clique in G Now check one edge a er the other Remove one edge from G compute the new size of the largest clique in this new graph Ifit is still kopt then this edge is not necessary for a clique Ifit is less than kopt then it is part ofthe clique 42115 Us 5555 Analysx afAtgamm 11 42119 Formal definitions of P and NP A decision problem H is solvable in polynomial time or HEP if there is a polynomia time algorithmA such that for any input x HxYES iffAxYES A decision problem H is solvable in non deterministic polynomial time or HENP if there is a polynomial time algorithmA such that for any input x HxYES iff there eXists a certi cate y of size polyx such thatAxyYES Us 5555 Analyrx afAlganthm 1 z I Is Does there exist a clique in G of size 2K in NP 7 Yes Axy interprets x as a graph G y as a set C and checks if all vertices in C are adjacent and if CEK I Is Sorting inNP 7 No not a decision problem I Is Sortedness inNP 7 Yes ignore y and check ifthe input x is sorted mung CS liAImlym ifAlgpvvhm Examples of problems in NP Reductions H to H I 1 YES x YES 4 N 0 mm assume mm m Reductions H to H YES 4 NO mung CS liAImlym ifAlgpvvhm 7 m u s Reductions Wm A39 For H I ispolynomial time reducible to H S H iff there is a polynomial time function f that maps inputs 6 for IT into inputs x for H such that for any x 39u a H X Hfx FactlifHePandH SchenH eP n39 n I Fact2ifHEN39P andH EchenH eN39P I Fact3transitivity iflT SH andH Schean SH mung assume 1mm 15 Clique again I Clique decision variant 7 Input Undirected graph GEOE and an integer K20 7 Output Is there a clique C ie a subset C of Vsuch that every pair of venices in C has an edge between them such that CEK 7 mm CS liAmlym ifAlgpvvhm n mung Independent set IS Input Undirected graph GVE and an integer K20 Output Is there a subset S of V S EK such that no pair ofvertices in S has an edge between them S is called an independent set CS liAnalym 1mm IE Clique 5 IS xnwsxmf s quot A39 as I39I ZChque x r H Given an input GVE K to Clique need to construct an input G V E K to IS H l fx such that G has clique of size 2K iff G has IS of size EK Construction K KV VE E Reason Cis a clique in Giffit is an IS in G s comp ement mung CS liAmlym ifAlgpvvhm 19 t M mung Vertex cover V C Input undirected graph GVE and K20 Output is there a subset C of V C S K such that each edge in E is incident to at least one vertex in C CS liAnalym mm m lt VC ISVC mourn A39I39urlT S x z H I Given an input G VE K to IS need to construct an input G V E K to vc such that f X X G has an IS ofsize 2K iffG has VC of size SK I Construction V V E E K lIlK I Reason Sis an IS in Giff VS is a C in G mung CS liAImlym ifAlgpvvhm 2i Recap I We de ned a large class of interesting problems namely NP I We have a way of saying that one problem is not harder than another If 7 H I Our goal show equivalence between hard problems mung ammonium 1mm Showing equivalence between dif th problems Options TS h 7 Show reductions between all i pairs ofproblems Clique 7 Reduce the number of reductions using transitivity of Squot mung CS liAImlym ifAlgpvvhm 2 Showing equivalence between dif th problems Options TS 7 Show reductions between all F pairs ofproblems C ique 7 Reduce the number of refdultctions using transitivity 0 of 7 Show that all problems in NP are reducib1eto a Med p3 p4 To show that so e V problem new is equiwlent A 0 all di p5 t iricuit ob1erns we only show 1391 5 1T mung ammonium 1mm The rst problem H Satis ability problem SAT 7 Given a formula y with m clauses over n variables eg 7 Check if there exists TRUEFALSE assignments to the variables that makes the formula satis able xlvxzwx5 xgvnx5 mung CS liAImlym ifAlgpvvhm 25 SAT is NP complete Fact SAT ENP Theorem Cook 71 For any H ENP we have H S SAT SA P3 n De nition A problem H such that for any H ENP we have H S H is called NPhard De nition An NPhard p oblem th r a belongs to NP is called NPcomplete Corollary SAT is NPcomplete mung CS lfAnalym 19mm t TS Ciquc T p4 P5 Plan of attack SAT Clique thanks Steve 3 Independent set Follow from Cook39s Theorem Vertex cover Conclusion all of the above problems are NP complete mung CS lfAmlym ifAlgpvvhm 27 ICl mung Clique again ique decision variant Input Undirected graph GEOE and an integer K20 Output 15 there a clique C an edge between them such that CEK 7 CS lfAnalym 19mm SAT 5 Clique 39 Nquot Amrn A39 Yarn x H Given a SAT formula Cl Cm over x1xn we need to produce G7VE and K H J x x such that y satis able iffG has a clique of size 2 K Notation a literal is either x or x mung summon ifAlgpvvhm m m mung SAT 5 Clique example Edge v lt2 z and r are not in the same clause and 39snot the negation o l Formula xlvxzvx3 nxzwnxp nx1 vxz Graph Claim y satis nable G has a clique of size 2 m summon ifAlgpvvhm i SAT 5 Clique reduction For each literal I occurring in g create a vertex vL Create an edge Vt 7 1 iff 7 t and t are not in the same clause and 7 t is not the negation of t mung summon 19mm Proof lt3 tandt are not in the same clause and z is not the negation oft Heepa 7 Take any assignment that satis es g1 Eg x F xfT x F 7 Let the set C contain one satis ed literal per clause 7 C is a clique mung summon 19mm CS 3343 Fall 2007 Dynamic Programming Carola Wenk Slides courtesy of Charles Leiserson with changes and additions by Carola Wenk 101807 CS 334Analysis ofAlgorithms l i Dynamic programming 7 x V 139 Algorithm design technique like divide and conquer Is a technique for solving problems that have overlapping subproblems and when used for optimization have an optimal substructure property Idea Do not repeatedly solve the same subproblems but solve them only once and store the solutions in a dynamic programming table 101807 CS 334 Analysis ofAlgorilhms 2 N Example Fibonacci numbers l 33939 FOO F11 FnFn1Fn2 for n 2 2 Implement this recursion naively Solve same Fm subproblems FUN Fn2 many times Fn2 Fn3 Fn3 Fn4Runt1m 15 exponential in n Store 1D DP table and fill bottomup in 001 time F0112 358 II 101807 CS 334 Analysis ofAlgorilhms 3 Longest Common Subsequence Vr a2 Example Longest Common Subsequence LCS Given two sequences x1 m and y1 n nd a longest subsequence common to them both 663939 Cthe 39 x A B I BD i B BCBA y B D C A B A LCSO functional notation but not a function 101807 CS 334 Analysis ofAlgorilhms 4 Bruteforce LCS algorithm l 33939 Check every subsequence of xl m to see if it is also a subsequence of yl n Analysis 2 subsequences of x each bitvector of length m determines a distinct subsequence of x Hence the runtime would be exponential 101807 CS 334 Analysis ofAlgorilhms Towards a better algorithm TwoStep Approach 1 Look at the length of a longestcommon subsequence 2 Extend the algorithm to nd the LCS itself Notation Denote the length of a sequence s by ls Strategy Consider pre xes of x and y De ne cz39j LCSx1 iy1 j Then cm n LCSx y 101807 CS 334 Analysis ofAlgorilhms ci 1J 1 1 ifxm ym CW maXcl39 1j cl39j 1 otherwise Proof Case xl39 yj Let z1 k LCSx1 iy1 j Where cz j k Then zk xz or else 2 could be extended Thusz1 k l is CS 0fx1z39 1andy1 j 1 101807 CS 334 Analysis ofAlgorilhms v 27 Proof continued Claim z1 k 1LCSx1 i ly1 j 1 Suppose w is a longer CS of x1 i l and y1 j l that is w gt 1 Then cut and paste w H zk w concatenated with zk is a common subsequence of x1 z39 and y1 j with lw zk I gt k Contradiction proving the claim Thus cz 1j 1 k l which implies that cz j cl39 1j 1 1 Other cases are similar 101807 CS 334 Analysis ofAlgorilhms r Dynamicprogramming 15quot hallmark 1 Optimal substructure An optimal solution to a problem instance contains optimal solutions to subproblems Recurrence If 2 LCSx y then any pre x ofz is an LCS of a pre x of x and a pre x of y 101807 CS 334 Analysis ofAlgorilhms Recursive algorithm for LCS LCSx y 139 j if xl39 yj then cl39j lt LCSx y i 1j 1 1 else cl39j lt maXLCSx y 241 LCSxy l39j 1 Worstcase xz 7t yj in which case the algorithm evaluates two subproblems each with only one parameter decremented 101807 CS 334 Analysis ofAlgorilhms lO l GO Rl THMS quot Recursion tree m3n4 same subproblem Height m n gt work potentially exponential but we re solving subproblems already solved 101807 CS 334 Analysis ofAlgorilhms Dynamicprogramming hallmark 2 Overlapping subproblems A recursive solution contains a small number of distinct subproblems repeated many times The number of distinct LCS subproblems for two strings of lengths m and n is only mn 101807 CS 334 Analysis ofAlgorilhms 12 Dynamicprogramming 1 33939 There are two variants of dynamic programming 1 Memoization 2 Bottomup dynamic programming often referred to as dynamic programming 101807 CS 334 Analysis ofAlgorilhms 13 39 19d Memoization algorithm Memoization After computing a solution to a subproblem store it in a table Subsequent calls check the table to avoid redoing work for all l39j cl3900 and COj0 LCSOC y 11 if cl39j NIL then if xl39 y39 then cl39j LCSx y i 1j 1 1 same as else clj maXLCSx y i lj before LCSOC y l1 Time mn constant work per table entry Space mn 101807 CS 334 Analysis ofAlgorilhms l4 LCSxy76 6E6 715 5 i 64 45 54 53 101807 1B 2D 3C 4A 5B 6A CS 334 Analysis ofAlgorilhms Memoization owP OUU ogto Ow nil nil nil nil nil nil nil nil NgtHgtgt gtO w N nil nil nil nil O 9 r K 0 pOpo O gtH E nil nil nil nil nil E nil nil nil nil nil nil nil nil nil nil Bottomup dynamic programming algorithm IDEA A B C B D A B Compute the O O O 0 table bottomup B Time mn O O O O O O O gtw gtOU 12233 101807 CS 334 Analysis ofAlgorilhms cs 3343 Spring 2009 ALGDRlTHMS Single Source Shortest Paths Carola Wenk Slides courtesy of Charles Leiserson with small anges by Carola Wenk Min c fidemzlyJu 17 ng Paths in graphs Consider a digraph G V E with edgeweight mction w E gt R The weight of pathp v1 gt vZ gt gt vkis de ned to be kil wpZWVDVH1 11 Example mm summon ifAlgamhm 2 Shortest paths A shortestputh from u to v is a path of minimum weight from u to v The shortest puth weight from u to v is de ned as 5u v minwp p is a path from u to v Note 5u v oo ifno path from u to 1 exists may a fidemzlyJu 17 ng Optimal substructure Theorem A subpath of a shortest path is a shortest path Proof Cut and paste mm summon ifAlgamhm a Triangle inequality Wellde nedness of shortest t paths Theorem For all u v x E V we have If a graph G contains a negativeweight cycle 5u v g 50 x 50 v then some shortest paths may not exis Proof Example 6uv minimizes over all paths from 14 to V Concatenating two shortest paths from t v yields one specific 4mm CS Amlym mtg th 5 4mm mummy qulgmihmr Singlesource shortest paths 5 39 Dij kstra s algorithm Problem From a given source vertex 5 e V nd d e 0 the shortestpath Weights 55 v for all v e V for each v e V7 s do dv e 00 Assumption All edge Weighs wu v are nannegative It follows that all shortestpath Weighs must exist gt Venices for which dvdvv Q e V lgt Q is apriority queue maintaining V7S while Q Q do IDEA Greedy u e EXTRAiTMINQ 1 Maintain asetSofverIices whose shoitestpath weights S e U 1 from s are known ie dVd sv for eachv 6 Ad u d 2 At each step 0 e vertex v a VrSwhose distance if reluxutmn estimate from s is minimal it step 3 Update the distance estimates ofvertices adjacent to v Implicit DECREASEKEY 4mm CS Amlym mtg th 7 4mm mummy qulgmihmr m Q lt V PREVI S algorithm 9 D1 kstra k2yv e no for al IV E V k2ys e o for some arbitrary s a V dv e 0 while Q a for eachv e V7 51 do u eEXTRACTMIMQ do dv e 00 for each v a Ad u e Q 39 do m a Q and W14Vlt MM 0 e V D Q is then k2yv e W14V vvvhile Q 3 do ueEXTR HSU ACT39MINQ It suf ces to only check v a Q S u but it doesn t mm to check all v I u for eachv 39 r39 ll relaxation s e Implicit DECREASEKEY 9 4mm minimums mtg th Graph with nonnegative edge weights 4mm Example of Dijkstra s algorithm while Q 25 in u e EXTRACTVMIMQ e SU m mummtm afAlmmhm Example of Dijkstra s algorithm Initialize d S m each v 6 Ad 1m ifdv gt dbl w v am am e d u w v 4mm mummme m w s A 4mm mummtm mu Example of Dijkstra s algorithm A EXTRACTMINQ210 while Q a an n e EXTRACTVMIMQ e Su u Aliu dn ifdv gt dbl w v am am e am w v Example of Dijkstra s algorithm Relax all edges avingA Example of Dijkstra s 10 w algorithm 2 C EXTRACTMJNQ e 10 s A s A C Q B C D E Q B D E Ooooooooo Ooooooooo Magda w e n 10 3 1 3 ueEXTRACTVMnMQ Sexy 11gt 111 each v e Ariu dn 1mm am wuvd12n am e 1414 w v AMIOQ csmmmtym am myth 1 4mm mumm 1mm 1 Example of Dijkstra s Example of Dijkstra s 1 w 39 algorlthm 7 11 algorlthm 7 11 Relax all edges 2 E EXTRACTMINQ 2 leaving C SAC SACE 0 Q B Q B D 0 no no 0 no no no hi 5 w e n 10 3 10 3 u e EXTRACTVMIIMQ 7 11 5 Se S 1 11gt 111 each v e Ariu an 111 each v e Ariu an ifdvgtduwuvth2n ifdvgtduwuvd12n dv eduwu v dv eduwuv 4mm minimumA11 mm 1 4mm magnumA11th Example of Dij kstra s Example of Dijkstra s algorlthm 7 1 1 algorlthm 7 1 1 Relax all edges B EXTRACTMINQ leav39ng E 10 SACE SACEB 0 Q B Q D 0 0 no no no no M Q m 5 w e n n 10 3 10 3 1 e ExTRAcTeMme 7 7 11 5 SeSv 11gt 7 7 11 fur each v e Adh an ifdv am wuvd12n dv e am wu v 4mm mambomm We WWWWm Example of Dij kstra s Example of Dijkstra s cm 39 algorlthm 7 9 algorlthm 7 9 Relax all edges D EXTRACTMINQ leaving B 10 SACEB 0 SACEBD0 Q D Q 0 no no 0 no no no no hi 5 w e n n 10 3 10 3 1 e EXTRACT M1NQ 7 11 11 5 Se 1 ngt 7 11 fur each v e Adh an 7 11 fur each v e Adh an ifdvgtduwuvthen ifdvgtduwuvthen dv edhwh v dv edhwuv 4mm mambomm e We mommamm in Analysis of Dijkstra while Q Q do u e EXTRACTMINQ V S e S u u for eaehv 6 Ad39 u d times 1 35 quot1 if dv gt du wu v then mes dv e du wu v Handshaking Lemma gt ED implicit DECREASEKEY s Time iVi39TEmcherN iEDITDECREASEVKEY Note Same formula as in the analysis of Prim s minimum spanning tree algorithm AMIOQ 15 summon 112341527 th 21 Analysis of Dijkstra continue Time iViITEXTRACTVMIN iEDITDECREASEVKEY Q TEXTRACTVlVllN TDECREASE39KEY Tomi may OOVD 01 WW b11122 ang M oaogM Fibonacci Olog 14 01 005 m log 14 heap amortized t amortized wors case 4mm minimum qulgrmhmr 22 Correctness Theorem i For all 1 E S dv 55 v ii For all 1 e S dv weight of shortest path from s to 1 that uses only besides v itself vertices in S Corollary Dijkstra s algorithm terminates with dv 55 v for all 1 E V 4mm minimum 11241557quotth 2 Correctness Theorem i For all 1 E S dv 55 v ii For all 1 e S dv weight of shortest path from s to 1 that uses only besides v itself vertices in S Proof By induction I Base Before the While loop dv0 and dvoo for all vzs so i and ii are true I Step Assume i and ii are true before an itemtion now We need to show they remain true a er another iteration Let u be the vertex added to S so du S dv for all other v a S 4mm minimum qulgrmhmr 24 5E Correctness Theorem i For all 1 E S dv 55 1 ii For all 1 e S dv weight of shortest path from s to 1 that uses only besides v itself vertices in S I i Need to show that du 55 u Assume the contrary gt There is apathp from to uWith wp lt du Because of ii that path uses venices e S in addition to u gt Lety be rst vertex onp such thaty S S just before 4mm minimum amwm 2s Correctness Theorem i For all 1 E S dv 5s 1 ii For all 1 e S dv weight of shortest path from s to 1 that uses only besides v itself vertices in S ontmdiction to the choice of u P minimum 11234197 th 25 COI I ectness Theorem i For all 1 E S dv 55 v ii For all 1 e S dv weight of shortest path from s to 1 that uses only besides v itself vertices in S I ii Let v e S Letp be a shortest path from to v that uses only besides v itself venices in S I p does not contain u ii true by inductive hypothesis I p contains u p consists ofvenices in St u and ends With an edge from u to v gt wpduwuv Which is the value of dv a er adding u So ii is true 4mm minimum amwm 27 Unwelghted graphs Suppose wu v l for all u v E E Can the code for Dijkstra be improved I Use a simple FIFO queue instead of a priority ueue I Breadth rst search 39 e Q Q do u e DEQUEUEQ for each v e Adju do if dv 00 then dv e du 1 ENQUEUEQ v Analysis Time OlVl l 4mm a may 11234197 th 22 Example of breadth rst n searc 4mm mmmm qulgamhm 29 Example of breadth rst searc 4mm wasme 11234197 th 30 Example of breadth rst 4mm mmmm qulgamhm 1 Example of breadth rst 39m search 4mm wasme 11234197 th 2 Example of breadth rst searc d Example of breadth rst 39N searc Example of breadth rst 4 search Example of breadth rst quot search Example of breadth rst Example of breadth rst 39 search 39N searc Example of breadth rst Example of breadth rst 1 search 39N search 4mm mmmm qulgamhm 9 Mm minimum 11234197 th A A Correctness of BFS while Q Q do u e DEQUEUEQ for each v e Adju do if dv 00 then dv e du 1 ENQUEUEQ v Key idea The FIFO Q in breadth rst search mimics the priority queue Q in Dijkstra Invariant 1 comes a er u in Q implies that dv du or dv du 1 4mm minimums mtg th How to nd the actual shortest aths Store a predecessor tree dv e 0 for eachv e V7 i do dv e co n Q e V while Q Q do u e EXTRACTMmQ e S u u lgt Q is a pIioIity queue maintaining V7 S S for eachv e Adju do if dv gt du wu v then dv e du wu v TE V E u 4mm magnumA197 th Example of Dijkstra s algorithm Graph with nonnegative edge weights while Q 25 do u e EXTRACTVMIIMQ S e SU u for each v e Ariu do ifdv gt du wu v than dv e dm wu v 4mm mmmhmmmm awe u 4 39 Example of Dijkstra s algorithm Initialize SI u do NM gt am wu v um d wu v v e am 4mm Cs AmtqufAlmmhm awe u Example of Dijkstra s algorithm A EXTRACTMINQ210 SA 0 nA B CD E Q 7B 7C 7D 7E 0 no no no no ah EAW er am gt am am e am 4mm somehowhe th awe u a flu wu v than wu v 45 Example of Dijkstra s algorithm 10 oo Relax all edges 2 leavingA S 39 A 1 A B C D Q B C D E 0 no no no no 10 3 7 7 whileQi3rln h e ExTRAcTeMme Se So on the each v e Adh an ifdv du wuvd12n am e am wu v 4mm CUuiAmtymgAtmmm 1tv e u 46 quot Example of Dijkstra s algorithm Relax all edges leavmgA 10 oo 2 hr each v e Ariu dn ifdv gt a up wu v then up wu v 47 am e d 4mm summon thth awe u 39 Example of Dijkstra s algorithm C EXTRACTMINQ 10 s A C 1 A B e A Q39 0 S the each v Adh an NM gt du wuvd12n am e am wu v 4mm CS AmlymaAlmmhm awe u Example of Dij kstra s Example of Dijkstra s algorlthm algorlthm 7 1 1 Relax all edges Relax all edges leaving C leaving C SAC S AC 0 1 A B C D n A B C D E A A A A Q B D Q B D E 0 no no no 0 no no no no hi1 Q Ed w e n 10 3 10 3 h eExTRAcTeMme 7 7 11 5 SESU on far ach e Adh an fur each v e Adh an ifdvgtduwuvthen imp duwuvd12n dv em wh v dv edhwuv 4mm mummwm mm Me u 49 4mm Cx AmlqufAlmmhm 7tvltu s quot Example of Dij kstra s Example of Dijkstra s cm 39 algorlthm 7 11 algorlthm 7 E EXTRACTMINQ Relax all edges 10 leaving E s ACE SACE o nABCDE nABCDB C A C C r C A C C Q B D Q 0 no no no no hi 3 5 0 no no no 10 3 h e ExTRAcTeMme 10 3 7 11 e u 7 11 fur each v e Adh an 7 11 fur each v e Adh an ifdv gt du wu v than ifdv gt du wuvd12n dv edhwh v dv edhwuv 4mm CS AmlquAlwmhm 1tve u 51 4mm mmAmtymAtmmm 7ME u CS 3343 7 Fall 2007 Antoni mm u Matrix Multiplication Carola Wonk Slides counesy ofCharles Leiserson with small anges by CarolaWenk m ammmwm 339 Powering a number Problem Compute a where n e N Naive algorithm n Divideandrc onquer algorithm recursive squaer ifn is even a awn own a in is odd TM Tot2 91 2 T01 logn ymm snowman1 3 Matrix multiplication Input AaJBbJ l 1 2 Output CCJ AvB quotJ 39 39 39quot an a A an an an A an bu An A m 2 22 A can 7 an 22 A 3912 b2 A2 A An 7 M 0 an an A an at A An A A AM n 5 EatC 39ka kl ymm tsawauon 447mm Standard algorithm forielton do lorjelton do CUlt0 forkelton do 5 ecvamvbw Running time nz ymm snowman1 14 Divideandconquer algorithm IDEA nxn matrix 2x2 matrix of mmmz submatriees iiiHi iSJEiil BMAIWM 447mm Analysis of DampC algorithm AA submatrices Work adding submatrix size submamcm quoth7g6quot W793 11 gt CASE 1 gt Tn 013 Va mm man the ordinary algmwint ymm snowman1 cs 3343 Spring 2009 ALGDRiTHMS Graphs Carola Wenk Slides courtesy of Charles Leiserson with changes and additions by Carola Wenk mm c diAmlym 17 ng g Graphs review Definition A directed graph digraph G V E is an ordered pair consisting of a set Vof vertices singular vertex asetE g Vx Vofedges In an undirected graph G V E the edge setE consists of unordered pairs of vertices In either case we have E O 2 Moreover ifGis connected then E 2 V 7 1 Review CLRS Appendix B4 and B5 mm Cx demlym ifAlgamhm 2 Adj acencymatrix representation The adjacency matrix of a graph G V E where V 1 2nisthematriXA1n1n 1 ifij E E 0 ifij e E V 2 storage gt dense representation 2 3 1 1 0 0 1 0 0 0 0 0 1 mm c diAmlym 17 ng 3 Adjacencylist representation An adjacency list ofa vertex v E Vis the 1istAdjv of vertices adjacent to v Adj127 3 Adj2 3 Adj3 U Adj4 3 For undirected graphs Adjv degreev For digraphs Adjv outdegreev mm Cx demlym ifAlgamhm a 1 Adj acencylist representation Handshaking Lemma Every edge 1 taunted thce For undirected graphs zveydegreem 2 IEI For digra hs Zvey indegreev Zvey 0utdegreev 2 E gt adjacency lists use lV lEl storage tion 5 a sparse representa gt We usually use this representation unless stated otherw1 9 c mm se Amlym mtg th s 32509 Graph Traversal Let GVE be a directed or undirected graph given in adjacency list representation lVl n lEl m A graph traversal visits every vertex Breadth rst search BFS Depth rst search DFS mmmtm 11234197 th BreadthFirst Search BFS BFSGVE ark M all Venice in G as unvisited lime0 V t v iiin e BFUH G 331222 while Q is nonempty do 7 v Qdeque e o ach w adjacent to v do it w 15 unvisited Visit w timet Add edge vw to T Qenqueuew mm Cx AmlqufAlgamhm 7 32509 Example of breadth rst search mmmtm 11234197 th z Example of breadth rst n searc mm assummtym mtg th Example of breadth rst searc 32509 Q bd minimum 11234197 th Example of breadth rst 1 search Example of breadth rst search mm assummtym mtg th 32509 minimum 11234197 th Example of breadth rst searc 0 mm Example of breadth rst 39N searc Example of breadth rst 4 mm search Example of breadth rst 39m search Example of breadth rst searc mmmtm mtg th mm search 32509 summary 11234197 th Example of breadth rst Example of breadth rst mmmtm mtg th mm BFSGVE Mark all venices in G as unvisited ime0 32509 BFSiiter G o 7 Oil Initialize empty queue for each venex v a Van in is unvisited n isit v muF BFS mm Witth Qenqueuev BFSJLE summary 11234197 th c BFS runtime H r Each venex is marked at most once enqueued at most once and therefore dequeued at most once The time to process avenex is proportional to the size of its adjacency list its degree since the graph is given in adjacency 1ist representation 2 0m tirne Totai nintirne is 0mm 0jvj jEj mm CX fA llysu 112141527 th 2i 32509 DepthFirst Search DFS DFSGVE Mark all venices in G as unvisited tin1e0 DstrecGv DFSirecG v visit v dvgtt lime for each w adjacent to v do if w is unvisited Add edge W to tree T DFSirecGw 39f v397 iLime CX fAmlys ring th 22 1 Store edges in ma b c d e f g hi predecessoralmy a mm CX fA llysu 112141527 th 2 32509 a b c d e f g h i predecessorarray a b Example of depth rst search Store edges in CX fAmlys ring th 24 46 Example of depth rst search ms S ore edgesin ma b c d e f g hi predecessormy a b mm mmmtm afAlgamhm 2s Example of depth rst search Store e gesin n a b c d e f g h i predecessorarray a b b 32509 mmmtm 11234197 th 25 Store edges in ma b c d e f g hi predecessormy ab b e mm mmmtm afAlgamhm 27 Store edges in niab cdefghi predecessorarray ab b e g 32509 mmmtm 11234197 th 22 6 Example of depth rst search Example of depth rst search 6 23 Store edges in 39 Store edges in n a b c d e f g hi predecessoralmy n a b c d e f g h i predecessorarray ab belg ab belg mm mummumgmm 29 32509 mmmmqmgm 30 Store edges in niab c de fghi predecessorarray ab bgelg mm mmmtm mtg th 1 32509 cummtm 11234197 th 2 31 Example of depth rst search in Example of depth rst search 23 Store edges in 39 Store edges 39 n a b c d e f g hi predecessorarmy n a b c d e f g h i predecessorarray abfbge1g abfbge1g mm Cs AmlymafAlgamhm 3 32509 mummyme 4 Store edges in Store edges in h i predecessor army 1 a b c d e f g h i predecessor array 1 g a b f b g e 1 g mm mmmtm mtg th as 32509 cummtm 11234197 th 35 mm s Example of depth rst search mummtm mtg th dgesin mab c de fghi predecessoralmy abfbge1g 32509 mab c de fghi predecessorarray abfbge1g mummtm mayth mm Example of depth rst search mummtm mtg th Store edges in a c d g h i predecessor army f e 1 g 0a 01 001230 withuut recursve call ng g DepthFirst Search DFS DFSGVE for each vertex v a Van if v is unvisited DFSirecGv Mark all Venice in G as unvisited time0 DFSirecG v visit v dvgt m for each w adjacent to v do if w is unvisited Add edge vw to tree T DFS recGw fvHlime 2 With Handshaking Lemma all recursive calls are om for atotal of 00 m mmime Amlym mayth Vii DFS runtime Each vertex is visited at most once 2 0a time The body ofthe ior1oops except the recursive call take constant time per graph edge A11 ior 1oops take 0m time Total runtime is OVLWL 01V1 1151 mm CS Amlym 11441517 th 4i if DFS edge classi cation glf 1013 32509 mammalian ringworm 42 Paths Cycles Connectivity Let GVE be a directed or undirected graph A path from v to vkin Gis a sequence ofvertices v1 v2vk such that vvvhmkE or vvvw EEifG is undirected for a11rs11e1 this simp1e if an vertices in the path are distinct A pa v v2vk orms a cyclei vak andk23 A graph with no cyc1es is acyclic a a have a root vertex speci ed A directed acyc1ic graph is a DAG A DAG can have undirected cyc1es ifthe direction ofthe edges is not considered Pail by a path A directed graph is strong1y connected iffor every pair we Vthere is a path from u to v and there is a path from v to u classes of vertices under this reachability relation mm CS Amlym 11441517 th j i i DAG Theorem Theorem A directed graph Gis acyc1ic cgt a depthiirst search ofGyields no back edges Proof 2 Suppose there is a back edge u v Then by de nition ofa back edge there would be a cyc1e C Suppose G contains a cle c Let V be the rst vertex to be discoveredin c and1et u be the preceding vertex in c v is an ancestor ofu in the depthiirst forest hence uv is a back edge 32509 mammalian ringworm 44 A A Topological Sort Tnpnlugically sort the venices of a directed acyclic mph DAG IDeterrninef Vgt 1 2 3fultfv Vi such that u v e E mummy mtg th n Topological Sort Algorithm I Store venices With indegree 0 in a queue Q I While Q is not ern ty I Dequeue vertex v and give it the next number I Decrease indegree of all adjacent venices by 1 I Enqueue all venices With indegree 0 Q abcedfgih 32509 minimum 11234197 th 46 Topological Sort Runtime Runtime I OVE because every edge is touched once and every vertex is enqueued and dequeued exactly once mm assummtym mtg th 47 15quot DepthFirst Search Revisited DFSGVE Mark all vertices in G as unvisited time0 for each Vertex v a Van ifv is unvisited DFSirecGv DFSirecG v visit v dvgtrtime for each w adjacent to v do if w is unvisited Add edge vw to tree T DFSirecGw f v i Hlmc 32509 minimum 11234197 th 4a 155 39m Algorithm I Call DFS on the directed acyclic graph gt Finish time for Way venex Reverse the nish Limes highest nish becomes the lowest nish Lime functiorlf Vgt 1 2 VD suchthat uveEgtf ultf v RurlLl39me OVE mm summons afAlgomhml DFS Based Topological Sort CHIE Lime 32509 CX Amlysu 11234197 th so 0 17 o e ge i i a depthfirst tree It holds to 14ltd v cross edge ifit is any other edge d14gtdv and ngt v orer i mm milAlso in 139 quot 1 DFS edge classi cation d f p 1013 tree edge ifit is part ofthe depthfirst forest 39 an ancestorv in a it holds DFS Based Top Sort Correctness 2m Needto show that for any 14 v s E holds fv lt f14 since we consider reversed finish times Consider exploring edge 14 v in DFS v cannot be visited and unfinished and hence an ancestor in the depth first tree since then itv would be aback edge which by the DAG lemma cannot hap en lfv has not been visited yet it becomes a descendant ofu and hence vlt 14 tree edge lfv has been finished v has been set and 14 is still being explored hence hgt v forvmrd edge cross edge 32509 CX Amlysu 11234197 th 52 cs 3343 Spring 2009 Aicniiinixis Sorting Carola Wenk Slides courtesy of Charles Leiserson with small changes by Carola Wenk 2mm mummies afAlgamhmr i How fast can we sort 7 All the sorting algorithms we have seen so far are comparison sorbquot only use comparisons to determine the relative order of elements I Eg insertion sort merge sort quicksort heapsort The best worstcase running time that we ve seen for comparison sorting is Onlogn Is 0n logn the best we can do Decision trees can help us answer this question 2mg CX Amlysu qulgrmhmr 2 i L m a a M M Fi quot Dec1s10ntree model 5 i lt A decision tree models the execution ofany comparison sorting algorithm I One tree per input size n I The tree contains all possible comparisons if bmnches that could be executed for any input of size n I The tree contains all comparisons along all possible instruction traces control ows for all inputs of size n I For one input only one path to a leaf is executed I Running time length of the path taken I Worstcase running time height of tree 2mm mummies afAlgamhmr 3 PM Decisiontree for insertion sort Sort lta1 a2 a3gt J 2 a J ms ert a3 Each internal node is labeled 1111 forz e 1 2 n The le subtree shows subsequent comparisons ira lt a The right subtree shows subsequent comparisons ira 2 a mu Cs Amlysiqulgzmhm Decisiontree for insertion sort Sort lta1 a2 a3gt lt946gt J i J J Each intemal node is labeled 1111 forz s 1 2 n The left subtree shows subsequent comparisons ira lt a The right subtree shows subsequent comparisons ira 2 a 2mm crrormommgmm 5 ii Decisiontree for insertion sort Sort lta1 a2 a3gt lt946gt inserts J i ins ert a3 Each intemal node is labeled 111 forz s 1 2 n The le subtree shows subsequent comparisons ira lt The right subtree shows subsequent comparisons ira 2 a 9 Cx AmlqufAlymhm l iii Decisiontree for insertion sort Sort a1 a2 a3gt lt946gt l l Each intemal node is labeled 1111 forz s 1 2 n The left subtree shows subsequent comparisons ifa lt a The right subtree shows subsequent comparisons ira 2 a 2mm crrormommgmm 3 Decisiontree for insertion sort Sort lta1 a2 a3gt lt946gt inserts J 2 i i ins ert a3 Each intemal node is labeled 1111 forz s 1 2 n The le subtree shows subsequent comparisons ira lt a The right subtree shows subsequent comparisons ira 2 a mu cmuiAmtymaAlgmhm I Decisiontree for insertion sort Sort lta1 a2 a3gt lt946gt i J ins ert a3 lt i J lt Eaeh internal node is labeled 1111 forz s 1 2 n The left subtree shows subsequent comparisons ira lt a The right subtree shows subsequent comparisons ira 2 a 2mm seamiomnmm 3 st Decisiontree for insertion sort Sort lta1 a2 a3gt lt946gt i J ins ert a3 Eaeh leafcontains apermutation W1 um 7EYLgt to indicate that the ordering am am am has been estahli ed 2mg CX Amlysu 11234197 th IE M 13 Dec1s10ntree model 4 s A decision tree models the execution ofany comparison sorting algorithm I One tree per inth size n I The tree contains all possible comparisons if bmnches that could be executed for any input of size n I The tree contains all comparisons along all possible instruction traces control ows for all 39 puts of size n I For one input only one path to a leaf is executed I Running time length of the path taken I Worstcase running time height of tree Lower bound for comparison sorting Theorem Any decision tree that can sort n elements must have height Qnlogn Proof The tree must contain 2 11 leaves since there are n possible permutations A heighth binary tree has S 2h leaves Thus n S 2h h 2 logn log is mono increasing 2 log Oi2 quot2 log quot2 gt h E Qn log 14 2mg CX Amlysu 11234197 th 2mm CS Amlym mtg th Lower bound for comparison sorting Corollary Heapsort and merge sort are asymptotically optimal comparison sorting algorithms D 2mm assummtym mtg th I Sorting in linear time Counting sort No comparisons between elements InputAl n whereAUEl 2 k Output Bl n sorted Auxiliury storage Cl k 2mg minimum 11234197 th i K Counting sort 1for i lt l to k do Ci lt 0 2forj lt l to n d0 CAj e CAj 1 Igt Ci key iH 3for i lt 2 to k do Ci lt Ci Ci71 lgt Ci key S i 4forj lt n downto l doBCAU e Am cA U E own1 1 2mm assummtym mtg th V Countingsort example 2mg minimum 11234197 th 1forilt1tok do Cilt0 2mm mmmtm mtg th 2 3 4 5 1 2 3 A C Loop 2 2 3 4 5 1 2 3 4 r L C III 2forj lt 1 to n d0 CAj E CAj 1 gt CU key 1N am mmmtm 11234197 th 12 2forj lt 1 to n d0 CAj e CAj 1 Igt Ci key iH 2mm mmmtm mtg th 19 2forj lt 1 to n d0 CAj e CAj 1 Igt Ci key M 2m mmmtm 11234197 th 20 2 3 4 5 A I 2forj e 1 do CAj e CAj 1 2mm ton mmmtm afAlgamhm 1 2 3 4 C II gtCikeyi 21 2forj lt 1 to n do CAj lt CAj 1 lgt Ci key iH 2mm mmmtm 11234197 th 22 3 3forilt2 0 do C 2mm mmmtm afAlgamhm t k i 9 cm Ci71 lgt cm key s 1H 2 3for i lt 2 to k do Ci lt Ci Ci71 lgt Ci key S i 2mm mmmtm 11234197 th 24 2 1 3 4 c sforiezmk 4forjltndowntol 39 do BCAU lt Aj do C1 lt Cz C171 Igt C1 7 ke S 1 y cum e cam 71 2mm cmuiAmtymaAlgmmm 25 71mg mmmwwmgm 25 4forj lt n downto 1 4forj lt n downto 1 doBCAU EAU d0 BCAU EAU CAU E CAU 1 CAU E CAj 1 2mg mmmtm 11234197 th 22 2 3 4 1 cunnn 4forj lt n downto 1 4forj lt n downto 1 doBCAU EAU d0 BCAU EAU CAU E CAU 1 CAU E CAj 1 4forj lt n downto 1 4forj lt n downto 1 doBCAU EAU d0 BCAU EAU CAU E CAU 1 CAU E CAj 1 2mg mmmtm 11234197 th 2 4forj lt n downto 1 doBCAU 9 AU CAU e CAU 1 2mm mmmtm mtg th a 2 4forj lt n downto 1 d0 BCAU 9 AU CAU e CAj 1 2mg mmmtm 11234197 th 4 4forj lt n downto 1 doBCAU 9 AU CAU e CAU 1 2mm mmmtm mtg th as m Analysis 1for i e 1 to k k do Ci e 0 2for j e 1 to n 90 do CAj e CA39 1 3for i e 2 to k k do Ci e Ci Ci71 4furj e n downto 1 90 0 0 BCAj e AU CAj e CAj 1 n k 2mg mmmtm 11234197 th 35 iquot Running time Ifk 0a then counting sort takes n time But sorting takes Qnlog n time Where s the fallacy Answer Comparison sorting takes Qn log n time Counting sort is not a comparison sort In fact not a single comparison between elements occurs 2mm mmmm mtg th 7 1 Stable sorting Counting sort is astable sort it preserves the input order among equal elements Exercise What other sorts have this property 2mg minimum 714197 th i K Radix sort Origin Herman Hollerith s cardsorting machine for the 1890 US Census See Appendix Digitbydigit sort Hollerith s original bad idea sort on mostsigni cant digit rst Good idea Sort on leastsigni cant digit rst with an auxiliary stable sorting algorithm like counting sort 2mm mmmm mtg th 9 Operation of radix sort 329 720 720 329 457 355 329 355 657 436 436 436 839 457 839 457 436 657 355 657 20 329 457 720 355 839 657 839 mm minimum 714197 th quot aquot Correctness of radix sort 3 7 Correctness of radix sort Induction on digitposition Induction on digitposition A thtth b 720 329 A thtth b 720 329 ssume a e num ers ssume a e num ers are sorted by their loworder 3 2 9 3 5 5 are sorted by their loworder 3 2 3 5 5 tildigits 36 436 tildigits 436 436 8 3 9 4 5 7 8 3 9 4 5 7 Sort on digit t Sort on digit t 3 5 5 6 5 7 I Two numbers that differin 3 5 5 6 5 7 4 5 7 7 2 0 digit t are correctly sorted 4 5 7 7 2 0 6 5 7 8 3 9 6 5 7 8 3 9 mm Cs AmlymafAlgamhm 41 71mg magnumA197 th 42 M Correctness of radix sort Analysis of radix sort Induction on digitposition Sort n computer words ofb bits each Assume that the numbers 7 2 0 3 2 9 View each word as having br base239 digits are sorted by their loworder 3 2 9 3 5 5 Example 32bit word b32 t7 1 digits 4 3 6 i 4 3 6 r l 32 base2 digits 1 W 8 3 9 4 5 7 39 39 39 Sort on dlglt t 3 5 5 6 5 7 gt br 32 passes of counting sort on base 2d1g1ts 39 TWP Wham mat differi 4 5 7 7 2 0 r 8 328 base28 digits 2 W 29 anquot dign are comm1y soned gt br 4 passes of counting sort on base28 digits I TWo numbers equal in digit 1 6 5 7 8 3 9 W are Put inthe same order as U r 16 3216 baSe216 digits m 21 the kiwi 3 COITBCI order gt br 2 passes ofcounting sort on base216 digits 2mm mummy me 4 mm Cs AmlqufAlgmhm 44 iquot Analysis of radix sort Sort n computer words of b bits each View each word as having br base239 digits Assume counting sort is the auxiliary stable sort Make br passes ofcounting sort on base239 digits How many passes should we make 2mm assummtym mtg th 45 1 Analysis continued Recall Counting sort takes n k time to sort n numbers in the range from 0 to k7 l If each bbit word is broken into rbit pieces each pass of counting sort takes n 239 time Since there are br passes we have Tnb n 27 r Choose r to minimize Tnb Increasing r means fewer passes but as r gtgt log n the time grows exponentially 2mg minimum 11234197 th 46 5 Choosing r Tnb 1 n M r Minimize T nb by differentiating and setting to 0 Or just observe that we don t want 239 gtgt n and there s no harm asymptotically in choosing r as large as possible subject to this constraint Choosing r logn implies Tnb bnlog n 2mm assummtym mtg th 47 Radix Sort with optimized r Assume counting sort is the auxiliary stable sort Sort n computer words of b bits each The rimtime ofradix sort is Tnb bnlogn Example For numbers in the range from 0 to nd 7 l we have b d log n gt radix sort rims in dn time Notice that countng sort rims in Onk time where all numbers are in the range 1 through k 2mg minimum 11234197 th Conclusions In practice radix sort is fast for large inputs as well as simple to code and maintain Example 32bit numbers At most 3 passes when sorting 2 2000 numbers Merge sort and quicksort do at least flog 2000i 11 passes Downside Unlike quicksort radix sort displays little locality of reference and thus a welltuned quicksort fares better on modern processors which feature steep memory hierarchies 2mm cum may ofAlgomhm 49 Appendix Punchedcard 1 technology Herman Hollerith 18601929 Punched cards Hollerith s tabulating system Operation of the sorter Origin of radix sort Modern IBM card i 2mm cum Analyas ofAlgomhm 5n quot Herman Hollerith 1 8601929 The 1880 US Census took almost 10 years to process While a lecturer at MIT Hollerith prototyped punchedcard technology His machines including a card sorter allowed the 1890 census total to be reported in 6 weeks He founded the Tabulating Machine Company in 191 l which merged with other companies in 1924 to form International Business Machines 2mm cum may ofAlgomhm 51 Punched cards Punched card data record Hole value Algorithm machine hum an operator Replica ofpunch card from the 1900 US census Howells 2000 2mm cum Analyas ofAlgomhm 52 cs 3343 Spring 2006 ALGOHlTHMS Matrix Multiplication Carola Wenk Slides comtesy of Charles LeiseIson with small changes by Carola Wenk 21qu diAmlym warm l a Powering a numb a bit easierthan the recursive mystery question on the homework Problem Compute aquot where n E N Naive algorithm n Divideandconquer algorithm recursive squaring n vimam ifnis even a a HyZ ultquot 1 a ifn is odd Tn Tn2 1 5 Tn log n yrsus c liAmlym army th w Matrix multiplication Input A a B17 l y y 7 Output C cgAB quotJ 1 2quot quot39 Mr 512 ml Mn 512 ai U711 1712 17m 521 522 52m Uzi 22 5n1 n2 5m n1 n2 m 17m an 17 2n 1721 1722 17m n Cl Zaxk 39bky k1 21qu c diAmlym warm Standard algorithm forilt1ton do forjelton do cyeo forkelton do cyecya kbkj Running time n3 yrsus c liAmlym army th r Divideandconquer algorithm IDEA nxn matrix 2x2 matrix of n2xn2 submatrices alu b CA39B NHV H noun 21505 assummtym wamm Strassen s idea Multiply 2x2 matrices with onl P1alfih r P5P4PZP6 P2ablh s P1PZ P3cde t P3P4 P4dlge u 135131 71337137 P5adleh P6 b 7 d39g h 7Nrriult1s18 aiddssubs P7aic39ef oe ore anceon commutativity of mult 21505 assummtym wamm 1 Analysis of DampC algorithm TM submatrices Work adding submatrices submatrix size 141 n 28 n3 5 CASE 1 5 T04 043 N0 better than the ordinary algorithm 21505 minimum 11234197 th Strassen s idea Multiply 2x2 matrices with only 7 recursive mults Pl afih sP1P P2abh afihabh P3 cde afiathathbh P4dg7e afbh P5adeh Psbd39gh P7aicef 21505 minimum 11234197 th cs 3343 Fall 207 ALGORITHMS Single Source Shortest Paths Carola Wenk Slides courtesy of Charles Leiserson with small changes by Carola Wenk 111307 CS 3343 Analysis ofAlgorithms Paths in graphs Consider a digraph G V E with edgeweight function w E gt R The weight of path p v1 gt v2 gt gt vk is de ned to be k l W00 2 WV12Vi1 11 Example 111307 CS 3343 Analysis ofAlgorilhms far Shortest paths Vr as A shortest path from u to v is a path of minimum weight from u to v The shortest path weight from u to v is de ned as 8u v minwp p is a path from u to v Note 8u v 00 if no path from u to v exists 111307 CS 3343 Analysis ofAlgorilhms 1 Goiii xHMs Optimal substructure Theorem A subpath of a shortest path is a shortest path Proof Cut and paste 111307 CS 3343 Analysis ofAlgorilhms A1 email HMS jar Triangle inequality V V Theorem For all u v x e V we have 5u v S 5u x 5x v Proof 0 8uv minimizes over all paths from u to v Concatenating two shortest paths from u to x and from x to v yields one speci c path from u to v 111307 CS 3343 Analysis ofAlgorilhms 5 Welldefinedness of shortest If a graph G contains a negativeweight cycle then some shortest paths may not exist Example 111307 CS 3343 Analysis ofAlgorilhms r quot Singlesource shortest paths Problem From a given source vertex s e V nd the shortestpath weights 8s v for all v e V If all edge weights wu v are nonnegative all shortestpath weights must exist IDEA Greedy 1 Maintain a set S of vertices whose shortest path weights from s are known 2 At each step add to S the vertex v e V S whose distance estimate from s is minimal 3 Update the distance estimates of vertices adjacent to v 111307 CS 3343 Analysis ofAlgorilhms 7 Dij kstra s algorithm ds lt O for each v e V s d0 dv 00 S lt Q lt V lgt Q is a priority queue maintaining V S while Q do u EXTRACTMINQ SeSuW for each v e Ad39u d0 if r relaxatlon step Implicit DECREASEKEY 111307 CS 3343 Analysis ofAlgorilhms A1 GO Rl THMS Q lt V PRIM s algorithm DlJ kStl a keyv lt 00 for all v e V 39 keys lt 0 for some arbitrary s e V dS 0 while Q 7 Q for each v e V s do u lt EXTRACTMINQ d0 dv 00 for each v e Adju S Q do ifv e Q and wu v lt keyv Q V D Q is then keyv lt wu v while Q 10 M r quot u EXTRACTMINQ It suf ces to only check v e Q S S U but it doesn t hurt to check all v for each v e j u 0 o i relaxatlon step Implicit DECREASEKEY 111307 CS 3343 Analysis ofAlgorilhms 9 A1 00Mquot HMS Example of Dijkstra s algorithm Graph with nonnegative edge weights while Q do u lt EXTRACTMINQ S lt S U u for each v e Adju do if dv gt du wu v then dv du wu v 111307 CS 3343 Analysis ofAlgorilhms 10 A1 GO Rl THMS Example of Dijkstra s algorlthm Initialize S while Q do u lt EXTRACTMINQ S lt S U u for each v e Adju do if dv gt du wu v then dv du wu v 111307 CS 3343 Analysis ofAlgorilhms 11 Example of Dijkstra s algorlthm A EXTRACTMINQ10 while Q do u lt EXTRACTMINQ S lt S U u for each v e Adju do if dv gt du wu v then dv du wu v 111307 CS 3343 Analysis ofAlgorilhms 12 A1 00Mquot HMS N Example of Dijkstra s algorlthm 10 oo Relax all edges leavingA S A Q B C 0 oo oo 10 3 whileQ d0 u lt EXTRACTMINQ S lt S U u for each v e Adju do if dv gt du wu v then dv du wu v 111307 CS 3343 Analysis ofAlgorilhms 13 Example of Dijkstra s algorlthm C EXTRACTMINQ10 while Q do u lt EXTRACTMINQ S lt S U u for each v e Adju do if dv gt du wu v then dv du wu v 111307 CS 3343 Analysis ofAlgorilhms 14 algorlthm Relax all edges leaving C S A C 0 oo oo 10 3 7 11 111307 Example of Dijkstra s while Q do u lt EXTRACTMINQ S lt S U u for each v e Adju do if dv gt du wu v then dv du wu v 15 CS 3343 Analysis ofAlgorilhms A1 GORi39I HMS Example of Dijkstra s 6 algorithm E EXTRACTMINQ10 SACE 0 Q 10 3 while Q do u lt EXTRACTMINQ 7 1 1 5 S lt S U u for each v e Adju do if dv gt du wu v then dv du wu v 111307 CS 3343 Analysis ofAlgorilhms 16 A1 GORl39I HMS Example of Dijkstra s algorithm Relax all edges leaving E SACE Q B while Q d0 0 oo oo 10 3 00 00 u lt EXTRACTMINQ 7 1 1 5 S lt S U u 7 11 for each v e Adju do if dv gt du wu v then dv du wu v 17 CS 3343 Analysis ofAlgorilhms 111307 A1 0mm HMS Example of Dijkstra s 7 2 1 algorithm B EXTRACTMINQ 10 SACEB o o 8 8 8 8 while Q d0 10 3 00 00 u lt EXTRACTMINQ 7 1 1 5 S lt S U u 7 11 for each v e Adju do if dv gt du wu v then dv du wu v 111307 CS 3343 Analysis ofAlgorilhms 18 A1 0mm HMS u Exanlple 0f Dijkstra s algorlthm N V Relax all edges leaving B SACEB o o 8 8 8 while Q d0 10 3 00 00 u lt EXTRACTMINQ 7 1 1 5 S lt S U u 7 11 for each v e Adju do if dv gt du wu v then dv du wu v 111307 CS 3343 Analysis ofAlgorilhms 19 A1 0mm HMS Example of Dijkstra s algorithm D EXTRACTMINQ 10 0 oo oo oo 00 I Q Q d 5 w 1 e 0 10 3 00 00 u lt EXTRACTMINQ 7 1 1 5 S lt S U u 7 11 for each v e Adju d0 9 if dv gt du wu v then dv du wu v 111307 CS 3343 Analysis ofAlgorilhms 20 Analysis Of Dijkstra while Q do u lt EXTRACTMINQ IVI S lt S U times JL for each v e Adju do degreeu if dv gt du wu v then t1mes dv du wu v Handshaking Lemma gt lE D implicit DECREASEKEY S Time l Vi TEXTRACTMIN IED TDECREASEKEY Note Same formula as in the analysis of Prim s minimum spanning tree algorithm 111307 CS 3343 Analysis ofAlgorilhms 21 7 7 Analysis of Dijkstra continued Time l TEXTRACTM1N IED TDECREASEKEY Q TEXTRACTMIN TDECREASEKEY TOtal array 0M 01 oqmz b11223 010glVD 010glVD 0IEHOgIVD Fibonacci 0logl 01 0Emlogl heap amortized amortized worst case 111307 CS 3343 Analysis ofAlgorilhms 22 N Correctness Vr 33939 Theorem i For all v e S dv 5s v ii For all v 93 S dv weight of shortest path from s to v that uses only besides v itself vertices in S Corollary Dijkstra s algorithm terminates with dv 5s v for all v e V 111307 CS 3343 Analysis ofAlgorilhms Q Correctness V Theorem i For all v e S dv 5s v ii For all v 93 S dv weight of shortest path from s to v that uses only besides v itself vertices in S Proof By induction Base Before the while loop ds0 and dvoo for all ViS so i and ii are true Step Assume i and ii are true before an iteration now we need to show they remain true after another iteration Let u be the vertex added to S so du S dv for all other v S 111307 CS 3343 Analysis ofAlgorilhms 24 Correctness 33 Theorem i For all v e S dv 8s v ii For all v 93 S dv weight of shortest path from s to v that uses only besides v itself vertices in S i Need to show that du 6s u Assume the contrary gt There is a path 9 from s to u with wp lt du Because of ii that path uses vertices S in addition to u gt Let y be first vertex on 9 such that y S S just before p path p from adding u 111307 CS 3343 Analysis ofAlgorilhms 25 in Correctness Theorem i For all v e S dv 8s v ii For all v 93 S dv weight of shortest path from s to v that uses only besides v itself vertices in S S just before Path 9 from s to u adding u gt dy S wp lt du Contradiction to the choice of u weights are assumption nonnegative about path 111307 CS 3343 Analysis ofAlgorilhms Correctness 33 i Theorem i For all v e S dv 5s v ii For all v 93 S dv weight of shortest path from s to v that uses only besides v itself vertices in S 0 ii Let v S Let p be a shortest path from s to v that uses only besides v itself vertices in S 9 does not contain M ii true by inductive hypothesis 9 contains u 9 consists of vertices in Su and ends with an edge from u to v gt wpduwuv which is the value of dv after adding M So ii is true 111307 CS 3343 Analysis ofAlgorilhms Unweighted graphs Suppose wu v l for all u v e E Can the code for Dijkstra be improved Use a simple FIFO queue instead of a priority queue Breadthfirst search While Q do u DEQUEUEQ for each v e Aa u do if dv 00 then dv du l ENQUEUEQ v Analysis Time O Vi El 111307 CS 3343 Analysis ofAlgorilhms 28 lco lii rH Ms 111307 Example of breadth rst search CS 3343 Analysis ofAlgorilhms lco lii rH Ms 111307 Example of breadth rst search CS 3343 Analysis ofAlgorilhms 111307 Example of breadth rst Search 11 Q bd CS 3343 Analysis ofAlgorilhms Search 111307 CS 3343 Analysis ofAlgorilhms Example of breadth rst search aquot quot N V 22 Q 66 111307 CS 3343 Analysis ofAlgorilhms Search 111307 CS 3343 Analysis ofAlgorilhms 111307 Example of breadth rst seaI Ch 33 Q gl39 CS 3343 Analysis ofAlgorilhms Example of breadth rst 111307 CS 3343 Analysis ofAlgorilhms A Example of breadthfirst 51 search Example of breadth rst 51 search Example of breadth rst 51 search 7 Example of breadth rst search Correctness of BFS While Q do u DEQUEUEQ for each v e Aa u do if dv 00 then dv du 1 ENQUEUEQ v Key idea The FIFO Q in breadth rst search mimics the priority queue Q in Dijkstra Invariant v comes after u in Q implies that dv du 0r dv du 1 111307 CS 3343 Analysis ofAlgorilhms 41 HOW to nd the actual shortest paths Store a predecessor tree ds lt O for each v e V s d0 dv 00 S lt Q lt V lgt Q is a priority queue maintaining V S While Q do u lt EXTRACTMINQ S lt S U u for each v e Aa u do if dv gt du wu v then dv du wu v 7v u 111307 CS 3343 Analysis ofAlgorilhms 42 A1 GORlquot HMS Example of Dijkstra s algorithm Graph with nonnegative edge weights while Q do u lt EXTRACTMINQ S lt S U u for each v e Adju do if dv gt du wu v then dv du wu v 111307 cs 3343Analysis ofAl omth TEV u 43 A1 GO Ri THMS Exaniple 0f Dijkstra s algorlthm Initialize S while Q do u lt EXTRACTMINQ S lt S U u for each v e Adju do if dv gt du wu v then dv du wu v 111307 cs 3343Analysis ofAl omth TEV u 44 A1 GO Ri THMS Example of DleStl a s algorlthm A EXTRACTMINQ10 SA n A B C D E Q B C D E 000000000 while Q do u lt EXTRACTMINQ S lt S U u for each v e Adju do if dv gt du wu v then dv du wu v 111307 cs 3343Analysz39s ofAl omth TEV u 45 A1 GORl T HMS Exanlple 0f Dijkstra s algorlthm Relax all edges leaving A SA o n A B C D E Q 58 C D E 3 while Q do u lt EXTRACTMINQ S lt S U u for each v e Adju do if dv gt du wu v then dv du wu v 111307 cs 3343Analysz39s ofAl omth TEV u 46 A1 GORlquot HMS Example of Dijkstra s algorithm Relax all edges leaving A while Q do u lt EXTRACTMINQ S lt S U u for each v e Adju do if dv gt du wu v then dv du wu v 111307 cs 3343 Analysis ofAl omth TEV u 47 A1 GORiquot HMS Example of DleStl a s algorlthm C EXTRACTMINQ10 while Q do u lt EXTRACTMINQ S lt S U u for each v e Adju do if dv gt du wu v then dv du wu v 111307 cs 3343Analysz39s ofAl omth TEV u 48 A1 GORl39I HMS Exanlple 0f Dijkstra s algorlthm Relax all edges leaving C 3 While Q Q do u lt EXTRACTMINQ 7 1 1 5 S lt S U u for each v e Adju do if dv gt du wu v then dv du wu v 111307 cs 3343 Analysis ofAl omth TEV u 49 A1 GORl T HMS O O 9 Exanlple 0f DleStl a s algorlthm Relax all edges leaving C 10 3 while Q do u lt EXTRACTMINQ 7 1 1 5 S lt S U u for each v e Adju do if dv gt du wu v then dv du wu v 111307 cs 3343 Analysis ofAl omth TEV u 50 A1 GORi39I HMS Example of Dijkstra s algorithm E EXTRACTMINQ10 V V a2 S A C E 0 at A B C D E 139 C A C C j m 3 5 10 3 WhileQ d0 u lt EXTRACTMINQ 7 1 1 5 S lt S U u for each v e Adju do if dv gt du wu v then dv du wu v CS 3343Analysz39s ofAl arithms TV u 51 111307 A1 GORl39I HMS Example of Dijkstra s 61 algorithm 7 1 Relax all edges 1quot leaving E S A C E 0 at A B C D E c A C C Q B D 0 oo 00 00 11 Q d 10 3 oo 00 W 1 e QETRAgTMINQ 7 l 5 S lt S U u 7 11 for each v e Adju do if dv gt du wu v then dv du wu v 111307 cs 3343 Analysis ofAl omth TEV u 52 A1 GORi39I HMS Example of Dijkstra s algorithm 7 V V a2 B EXTRACTMINQ 10 S A C E B 0 at A B C D E C A C C Q D 0 00 oo oo 00 I g Q d 5 W 1 e 0 10 00 00 u lt EXTRACTMINQ 7 1 1 5 S lt S U u 7 11 for each v e Adju do if dv gt du wu v then dv du wu v CS 3343Analysz39s ofAl arithms TV u 53 111307 A1 001m HMS Example of Dijkstra s 1 algorithm Relax all edges leaving B S A CEB o n A B C D E C A B C V o 8 8 8 while Q do u lt EXTRACTMINQ S lt S U u for each v e Adju do if dv gt du wu v then dv du wu v 111307 cs 3343Analysis ofAl arithms TEV u l 1 1 a U18 54 L G o 11 FriMs CS 33433 Fall 2007 ALGORITHMS Topological Sort Carola Wenk 11107 CS 3343 Analysis ofAlgorithms AlGORl39lHMS 33 Paths Cycles Connect1v1ty Let GVE be a directed or undirected graph A path from v1 to vk in G is a sequence of vertices v1 v2 vk such that vivi1 GE or vivi1 GE ifG is undirected for all ie1k1 A path is simple if all vertices in the path are distinct A path v1 v2 vk forms a cycle if v1vk and 122 A graph with no cycles is acyclic 0 An undirected acyclic graph is called a tree Trees do not have to have a root vertex speci ed 0 A directed acyclic graph is a DAG A DAG can have undirected cycles if the direction of the edges is not considered An undirected graph is connected if every pair of vertices is connected by a path A directed graph is strongly connected if for every pair uve Vthere is a path from u to v and there is a path from v to u 0 The strongly connected components of a graph are the equivalence classes of vertices under this reachability relation 11107 CS 3343 Analysis ofAlgorilhms 2 lco lii rH Ms Topological Sort Topologically sort the vertices of a directed acyclic graph DAG Determinef V gt 1 2 gtfu ltfV VI such that u v e E 11107 CS 3343 Analysis ofAlgorilhms A1 GORi39I HMS Topologlcal Sort Algorlthm Store vertices in a priority minqueue with the indegree 0f the vertex as the key While queue is not empty 0 Extract minimum vertex v and give it next number Decrease keys of all adjacent vertices by 1 11107 CS 3343 Analysis ofAlgorilhms A1 ooui x HMS Topological Sort Algorithm Store vertices in a priority minqueue with the indegree of the vertex as the key While queue is not empty 0 Extract minimum vertex v and give it next number Decrease keys of all adjacent vertices by 1 39 39 N V CS 3343 Analysis ofAlgorilhms 11107 Topological Sort Runtime Runtime OV to build heap OE DECREASEKEY ops gt OV E log V with a binary heap gt OV E with a Fibonacci heap 11107 CS 3343 Analysis ofAlgorilhms AlGOR139lHMS quot DepthFlrst Search rev1s1ted DFSGKE Mark all vertices in G as unVisited time0 for each vertex v e Vdo if v is unVisited DFSrecGv DFSrecG v Visit v dVtime discover time for each w adjacent to v do if w is unVisited Add edge vw to tree T DFSrecGw fVtime nish time 11107 CS 3343 Analysis ofAlgorilhms AlGOR139lHMS 33 V DFS Edge Classi cation 0 Edge uv in depthfirst forest Tree edge v was discovered by by exploring edge uv 0 Edge uv not in depthfirst forest Back edge v is ancestor of u in depthfirst forest Forward edge v is descendant of u in depthfirst forest Cross edge Any other edge 11107 CS 3343 Analysis ofAlgorilhms DFS Based Topological Sort Algorithm Call DFS on the directed acyclic graph G VE gt Finish time for every vertex Reverse the finish times highest finish time becomes the lowest finish time gt Valid functionf V gt 1 2 V such that uv e Egtfultfv Runtime OWE lll07 CS 3343 Analysis ofAlgorilhms ALGO Iii rHMs 11107 CS 3343 Analysis ofAlgorilhms A LG 0R i r H39M39s CS 3343 Fall 2007 Lquot p ALGORITHMS Graphs Carola Wenk Slides courtesy of Charles Leiserson with changes and additions by Carola Wenk 103007 CS 3343 Analysis ofAlgorithms Graphs De nition A directed graph digraph G V E is an ordered pair consisting of 21 set Vof vertices singular vertex 21 setE g Vgtlt Vofedges In an undirected graph G V E the edge set E consists of unordered pairs of vertices In either case we have E 0 Vi 2 Review CLRS Appendix 34 and B5 103007 CS 3343 Analysis ofAlgor ilhms Adjacencymatrix representation The adjacency matrix of a graph G V E Where V 1 2 n is the matriXA1n1n givenby 1ifz39jeE AM 10 ifme 1 2 1 O 1 1 O l V1 2 storage 2 O O 1 0 gt dense 3 0 0 0 0 representation 4 0 0 1 0 103007 CS 3343 Analysis ofAlgorilhms Adjacencylist representation An adjacency list of a vertex v e V is the list Aa jv of vertices adjacent to v Adj 2 3 Adj2 3 Adj3 Adj4 3 For undirected graphs Aayv degreev For digraphs Adjv 0ut degreev 103007 CS 3343 Analysis ofAlgorilhms 4 quotN Adjacencylist representation Vr ear Handshaking Lemma Every edge is counted twice For undirected graphs 2V6 Vdegreev 2 E For digraphs ZveV indegreev ZveVoutdegredv 2 E gt adjacency lists use l V E storage gt a sparse representation 103007 CS 3343 Analysis ofAlgorilhms 103007 Graph Traversal Let G VE be a directed or undirected graph given in adjacency list representation M n lEl m A graph traversal visits every vertex Breadth rst search BFS Depth rst search DFS CS 3343 Analysis ofAlgorilhms AlGORl39lHMS DepthFirst Search DFS DFSGVE C71 Mark all vertices in G as unvisited time0 O for each vertex v e Vdo 00 if v is unvisited W1th0ut DFSirec DF SreCGaV DFSrecG v 01 visit v time for each w adjacent to v do 0degv if w is unvisited Without edge VJV to tree T DFSrecGw recursive call 3 With Handshaking Lemma all recursive calls are Om for a total of On m runtime 103007 CS 3343 Analysis ofAlgorilhms AlGORi39IHMs DFS runtime Each vertex is Visited at most once gt On time The body of the for loops except the recursive call take constant time per graph edge 0 A11 for loops take Om time Total runtime is Onm OV E 103007 CS 3343 Analysis ofAlgorilhms 8 AlGORl39lHMS Q BreadthFirst Search BFS BFSGVE n Mark all vertices in G as unVisited time0 01 Initialize empty queue Q for each vertex v e Vdo if v is unVisited V 001 Visit v time without QenqueueV BFSJTI BFSiterG BFSiterG while Q is nonempty do v Qdequeue for each w adjacent to v do if w is unVisited 0degv Visit w time Add edge vw to T Qenqueuew 0m 103007 CS 3343 Analysis ofAlgorilhms 9 Chapter 7 Space and Time Tradeoffs The biggest difference between time and space is that you can39t reuse time Merrick Furst Introduction Distribution Counting Sorting Integers by Counting Them Distribution Counting Algorithm Distribution Counting Example Input Enhancement in String Matching String Matching Speedup Idea Horspool s Algorithm Examples of Horspool s Algorithm Shift Table for Horspool s Algorithm Horspool s Algorithm Comments on Horspool s Algorithm Hashing Introduction to Hashing Hash Functions Collision Resolution by Chaining Collision Resolution by Probing Comments on Hashing B Trees Introduction to BTrees Example of BTree 2 17 18 Introduction Often we can solve a problem faster by using additional space E El El cs 3343 Analysis ofAlgorithrns Input enhancement is based on preprocessing the instance to obtain additional information that can be used to solve the instance in less time Prestructuring is based on using extra space to facilitate faster andor more flexible access to the data Dynamic programming Chapter 8 is based on recording solutions to smaller instances so that each smaller instance is solved only once Chapter 7 Slid272 Distribution Counting Sorting Integers by Counting Them III II cs 3343 Analysis ofAlgorithrns The idea to count how many times each integer appears in an array This information can be used to sort the array For example if we knew there were three 05 and 0 is the minimum then the sorted array will have 05 in positions 0 1 and 2 This requires an additional array to store the counts This only works well if the range of integers is 0n order n or less Chapter 7 snag a 3 Distribution Counting Algorithm algorithm DistributionCountz n AlOn 7 1 m Sort by distribution counting Input An array A of integers Z 0 and lt m Output Sorted array 5 forjlt0tom71doDjlt0 for i e 0 to n7 1 do lt 1 forje1tom71doDjltDj71Dj orienildowntoodo lt 71 SlDlAliHl e Ali return 5 CS 3343 Analysts ofAlgorlthms Chapter 7 Sltde e 4 Input Enhancement in String Matching String Matching Speedup Idea We can speed up string matching by matching from the right side of the string D Consider a search for analysis in some text D A possible match is from positions 0 to 7 of the text D If we compare 5 to position 7 and D this letter is not 5 or any letter in analysis D then the next possible match for analysis is positions 8 to 15 D so we next compare 5 to position 15 D Other misses shift the next possible match different amounts D The shift amounts can be stored in a table CS 3343 Analysts ofAlgorlthms Chapter 7 Sltde e 5 Distribution Counting Example D SupposeA302322 E Second loop D 10 3 2 D Third loopD1146 D Fourth loop 39 1717376 5 7 739727397 i D1126 5 22 139 D1125 S 223 i D1115 S2223 i1 D0015 S02223 10 D0014 S022233 CS 3343 Analysts ofAlgorlthms Chapter 7 Sltde e 5 Horspool s Algorithm D Horspool s algorithm performs a shift based on the text character 6 compared to the last character in the pattern D If c does not appear in the rest of the pattern shift the length of the pattern D If 6 appears in the rest of the pattern shift the number of characters between the last 6 in the rest of the pattern to the end of the pattern CS 3343 Analysts ofAlgorlthms Chapter 7 Sltde e 7 Examples of Horspool s Algorithm T S P BARBER shift BARBER T B P BARBER shift BARBER T TER P LEADER shift LEADER T TER P ERASER shift ERASER CS 3343 Analysis ofAIgorIthms Chapter 7 Shae 7 s Shift Table for Horspool s Algorithm algorithm HorspoolTableP0m 7 1 Input Pattern P Output Shift table for Horspool s Algorithm for k lt7 0 to character set size 7 1 do lt7 m forjlt70tom72do 51PM 7 m717j return 5 CS 3343 Analysis ofAIgorIthms Chapter 7 Shae 7 g Horspool s Algorithm algorithm HorspoolP0m 7 1T0n7 1 Implements HorspooI s Algorithm Input Pattern P and text T Output Index of match in text or 71 S lt7 HOTsp00lTableP ilt70 iis index intoT while i g n 7 m o klt7m71 kisindexintoP while 10 2 0 and Pk Ti 10 do k lt7 k 7 1 if k lt 0 then return 139 else i lt7 iSTi m7 1 return 71 CS 3343 Analysis ofAIgorIthms Chapter 7 Shae 7 10 Comments on Horspool s Algorithm El HorspooI s Algorithm uses m additional space the space for the shift table HorspooI s Algorithm can run anywhere from 9m nm best case to 0mn worst case The 0n BoyerMoore Algorithm is based on the all the characters that are compared rather than just the one compared to the last character of the pattern El El CS 3343 Analysis ofAIgorIthms Chapter 7 Shae 7 11 Hashing 12 Introduction to Hashing D D D D D D CS 3343 Analysis of Algorithms Hashing is an approach to implement a dictionary to insert search and delete elements of a set records in a file Typically records have several fields one of which is the key which identifies the record Hashing distributes the keys in cells of a hash table an array A hash function h computes the hash address from a key A collision is when two different keys have the same hash address ie MIG Chaining and probing are two approaches for collision resolution Chapter 7 Slide 12 Collision Resolution by Chaining In chaining each cell is a linked list that contains all the keys hashed to that cell keys A FOOL AND HIS MONEY ARE SOON PARTED hashaddresses 1 9 6 10 7 11 11 12 O 1 2 3 4 5 6 7 8 9 1O 11 12 l A l l l l l 1 AND MONEY FOOL HIS ARE PARTED l SOON FIGURE 75 Example of a hash table construction with separate chaining The load factor is 04 nm number of keys number of cells The average number of celllist accesses is d CS 3343 Analysis of Algorithms Chapter 7 Slide 14 Hash Functions D CS 3343 Analysis of Algorithms A hash function should distribute keys evenlyrandomly in the hash table and should be easy to compute Cryptographic hash functions should also be hard to reverse ie for an arbitrary a hard to find a key such that a A simple hash function is K mod m m is the hash table size m should be prime For a character string TlOl 1 where C is the size of the character set use CLlt O forz39HOtol Ido a9agtiltCTimodm Chapter 7 Slide 13 Collision Resolution by Probing In linear probing a key is inserted in the first empty cell starting with the hash address keys A FOOL AND HIS MONEY ARE SOON PARTED hashaddresses 1 9 6 1O 7 11 11 12 O 1 2 3 4 5 6 7 8 9 1O 11 12 A A FOOL A AND FOOL A AND FOOL HIS A AND MONEY FOOL HIS A AND MONEY FOOL HIS ARE A AND MONEY FOOL HIS ARE SOON PARTED A AND MONEY FOOL HIS ARE SOON FIGURE 76 Example of a hash table construction with linear probing On average this is 11 04 for successful search and 11 002 for unsuccessful search CS 3343 Analysis of Algorithms Chapter 7 Slide 15 Comments on Hashing D D D CS 3343 Analysis of Algorithms The efficiency of hashing depends on well distributed keys and low load factors Chaining can tolerate load factors gt 1 but for probing the load factor must be lt1 and should be lt 075 If a hash table becomes full or nearly full a common solution is rehashing moving all keys to a larger hash table Double hashing is a more efficient alternative to linear probing Chapter 7 Slide 16 Chapter 9 Greedy Algorithms From the first day to this sheer greed was the driving spirit of civilization Friedrich Engels Introduction 2 Example of Making Change 3 Prim s Algorithm 4 Minimum Spanning Trees 4 Prim s Algorithm 5 Example of Prim s Algorithm 6 Example of Prim s Algorithm Continued 7 Comments on Prim s Algorit m 8 Kruskal s Algorithm 9 Kruskal s Algorithm 9 Example of Kruskal s Algorithm 10 Example of Kruskal s Algorithm Continued 11 Comments on Kruskal s Algorithm 12 Dijkstra s Algorithm 13 SingleSource Shortest Paths 13 Dijkstra s Algorithm 14 Example of Dijkstra s Algorithm 15 Example of Dijkstra s Algorithm Continued 16 Comments on Dijkstra s Algorithm 17 Huffman Trees 18 Encodings 18 Optimal Prefix Codes 19 Huffman s Algorithm 20 Example of Huffman s Algorithm 21 Example of Huffman s Algorithm Continued 22 Introduction Prim s Algorithm Greedy algorithms is a technique for solving problems with the following properties Minimum Spanning Trees D The problem is an optimization problem to find the solution that minimizes or maximizes some value costprofit D The solution can be constructed in a sequence of stepschoices D For each choice point D A spanning tree of a connected graph is a tree containing all the vertices D A minimum spanning tree of a weighted graph is a spanning tree with the smallest weight D The e39 ht of a s ann39n tree 395 the s m of the ed e e39 hts The choice must be feasible W 1g p 1 g 1 11 g W 1g The choice looks as good or better than alternatives 9 1 0 6 1 0 9 1 9 9 1 0 The ch0ice cannot be revoked 5 2 5 5 2 CS 3343 Analysis ofAlgorithms Chapter 9 Slide 2 a 3 a a 3 a a 3 a a a Wqul6 l graph w T2 9 w T3 8 FIGURE 91 Graph and its spanning trees T1 is the minimum spanning tree CS 3343 Analysis of Algorithms Chapter 9 Slide 4 D Suppose we want to give change of a certain amount say 24 cents D We would like to use fewer coins rather than more Prquotquot 5 Algorlthm D We can make a solution by repeatedly choosing a coin g to the current amount resulting in a new amount algorithm PrzmG D The greedy solution is to always choose the largest com value pOSSIble for 24 Returns the MST by Prims Algorithm cents 10 10 1 1 1 139 lnput A weighted connected graph G V E D If there were an 8 cent com the greedy algorithm would not be optimal but Output Set of edges comprising a MST not bad VT 9 any vertex in G CS 3343 Analysis of Algorithms Chapter 9 Slide 3 ET 9 w forieltolVl ldo e minimum weight edge vu WlthUElT and uEV VT VT VT U ET 9 ET U 6 return ET CS 3343 Analysis of Algorithms Chapter 9 Slide 5 Example of Prim s Algorithm 9 Tree vertices Remaining vertices Illustration a a ba9 C 00 da 00 1 ca 6 Ha 5 3 ave a 6 8 9 ba 3 cb 1 d 00 ea 6 1 m3 4 3 v 3 6 8 9 CS 3343 Analysis of Algorithms Chapter 9 Slide 6 Comments on Prim s Algorithm D This algorithm repeatedly chooses the smallest weight edge from the tree so far to the other vertices D If a spanning tree has a weightier edge between VT and V VT it can be improved by replacing it with e D We can put VT edges into a priority queue then dequeue edges until one goes between VT and V VT D Prim s Algorithm using a binary heap to implement a priority queue is OElog E OElog V CS 3343 Analysis of Algorithms Chapter 9 Slide 8 Example of Prim s Algorithm Continued cb 1 fb 4 ef 2 df 5 dc 6 ca 6 fb 4 0 1 0 3 v 3 6 8 e df5 ef 2 a l a 3 v 3 6 8 e df5 0 l a 3 v 3 6 8 e FIGURE 92 Application of Prim39s algorithm The parentheslzed labels of a vertex in the middle column indicate the nearest tree vertex and edge weight selected vertices and edges are shown in bold CS 3343 Analysis of Algorithms Chapter 9 Slide 7 Kruskal s Algorithm Kruskal s Algorithm algorithm KruskaKG Returns the MST by Kruskal s Algorithm Input A weighted connected graph G V E Output Set of edges comprising a MST sort the edges E by their weights ET lt 0 while lETl l 1 lt lVl do 6 H next edge in E if E U 6 does not have a cycle then ET H ET U 6 return ET CS 3343 Analysis of Algorithms Chapter 9 Slide 9 Example of Kruskal s Algorithm 3 6 6 8 G Tree edges Sorted list of edges Illustration bc ef ab bf cf af df ae Cd de 1 1234455668 9 a 36 e be be ef ab bf ef af df ae ed de 1 55 6 6 1 12344 8 0 0 36 G CS 3343 Analysis of Algorithms Chapter 9 Slide 10 Dijkstra s Algorithm SingleSource Shortest Paths D The singlesource shortest paths probem finds the shortest paths from a given vertex the source vertex to all the other vertices D Dijkstra s algorithm can be used if there are no negative edges The Bellman Ford algorithm is used if there are negative edges D Floyd s algorithm is used for all pairs shortest paths if there are no negative weights D CS 3343 Analysis of Algorithms Chapter 9 Slide 13 Example of Kruskal s Algorithm Continued ef be ef ab bf cf af df ae ed de 1 1 6 6 2 234455 8 ova 3 6 9 ab be ef ab bf of at df ae ed de 1 1 2 3 445 5 6 6 8 3 0 0 3 v e 6 8 9 bf bfbbfffdf dd 4 1C3334Ela55a6ec68 010 3 6 6 8 9 df 5 FIGURE 94 Application of Kruskal39s algorithm Selected edges are shown in bold CS 3343 Analysis of Algorithms Chapter 9 Slide 11 Comments on Kruskal s Algorithm D This algorithm repeatedly chooses the smallest weight edge that does not form a cycle D Kruskal s Algorithm is OElog V using efficient cycle detection D Disjoint Set Implementation for Detecting Cycles Put each vertex into a singleton set 6 is chosen if its vertices are in different sets When 6 is chosen the two sets are unioned CS 3343 Analysis of Algorithms Chapter 9 Slide 12 Dijkstra s Algorithm algorithm DijkstraG s Solves SSSP by Dijkstra s Algorithm Input A weighted connected graph G V E with no negative weights and source vertex v Output The length and path from s to every 22 for v E V do dv H 00 pl 9 null unmark 2 d8 H 0 while u H unmarked vertex with smallest du mark u for each 22 adjacent from u do if v is unmarked and du wuv lt d1 then dv H duwuv p1 H u CS 3343 Analysis of Algorithms Chapter 9 Slide 14 II I Example of Dijkstra 5 Algorithm HUffman Trees 0 4 a 3 6 Encodmgs a 7 Ko J 4 e Treevemces Remainingvemces Illustration D We can represent an n character set by assigning a codeword a bit string to alt 0gt blta3gtclt oodlta7gtelt aoogt 3 a 4 o 6 each character a 7239s 54 e D Fixedlength encoding eg ASCII assngns m blt strings to each character ba3 cb34db32 e oo 3 0 4 o 6 m 10g2 77quot I a 239 5 e D Variablelen th encodm e Morse code assn ns different en ths 7 U 4 I 105 Cb7ed54 4 a D To avord ambiguity use prefx codes Ie no codeword IS a prefix of another a3 6 codeword 7 U 4 6 CS 3343 Analysis of Algorithms Chapter 92 Slide 15 CS 3343 Analysis of Algorithms Chapter 9 Slide 18 II I I I I Example of Dijkstra 5 Algorithm Continued Optimal Prefix Codes cm ea 9 4 a D Problem If the probabilities of the characters are known what is the best a 72 54 9 binary prefix code 19 D Best means the expected length of a codeword sum of probabilities times The shortest paths identi ed by following nonnumeric labels d e I e n gt h backward from a dest1nat1or1 vertex 1n the left column to the I I I 1 1 I Z giilfgfethmengms g venbynumemlabels theme B Any binary tree wrth edges labeled With 0 s and l s and characters assrgned to f t b b H m its leaves yields a prefix code roma O I a 0 eng I I I 33333 3531 333333 E The two smallest probabilities must have the same length G mat quotb d e flength9 D If made siblings the size of the problem decreases by one Fl URE 910 Application of Dijkstra s algorithm The next Closest vertex is shown in bold CS 3343 Analysis of Algorithms Chapter 9 Slide 16 CS 3343 Analys39s Of Algorithms Chapter 9 Slide 19 Comments on Dijkstra s Algorithm D This algorithm repeatedly processes the closest unmarked vertex u B When u is marked the SP to u is known Basis First value of u is 3 whose SP is known Induction Assume SPs to previously marked vertices are known SPs to unmarked vertices must start with some marked vertices u is closest unmarked vertex D Dijkstra s Algorithm using a binary heap to implement a priority queue is OElog V CS 3343 Analysis of Algorithms Chapter 9 Slide 17 cs 3343 Fall 2007 l ALGORITHMS Minimum Spanning Trees Carola Wenk Slides courtesy of Charles Leiserson with changes and additions by Carola Wenk 11607 CS 3343 Analysis ofAlgorithms Minimum spanning trees Vr 12 Input A connected undirected graph G V E with weight function w E gt R For simplicity assume that all edge weights are distinct Output A spanning tree T a tree that connects all vertices of minimum weight wT Zwuv uveT 11607 CS 3343 Analysis ofAlgorilhms ALGOR E T HMS 11607 CS 3343 Analysis ofAlgorilhms Hallmark for greedy algorithms 11607 Greedychoice property A locally optimal choice is globally optimal Theorem Let T be the MST of G V E and letA g V Suppose that u v e E is the leastweight edge connecting A to V A Then it v E T CS 3343 Analysis ofAlgorilhms Z Proof of theorem Vr a2 Proof Suppose u v 93 T Cut and paste T p 9quot Q E 1 A u v leastweight edge Q 6 connecting A to V A 11607 CS 3343 Analysis ofAlgorilhms i svr Proof of theorem Vr 33939 Proof Suppose u v 93 T Cut and paste T p 9quot 2 1 u v leastweight edge connecting A to V A Consider the unique simple path from u to v in T 11607 CS 3343 Analysis ofAlgorilhms V V 12 Proof of theorem Proof Suppose u v 93 T Cut and paste T Qquot 2 I A u v leastweight edge connecting A to V A Consider the unique simple path from u to v in T Swap u v with the rst edge on this path that connects a vertex in A to a vertex in V A 11607 CS 3343 Analysis ofAlgorilhms 37 quot Vr 33939 Proof of theorem Proof Suppose u v 93 T Cut and paste T39 QEA Q E V A u v leastweight edge connecting A to V A Consider the unique simple path from u to v in T Swap u v with the rst edge on this path that connects a vertex in A to a vertex in V A A lighterweight spanning tree than T results 11607 CS 3343 Analysis ofAlgorilhms 8 xv Prim s algorithm IDEA Maintain V A as a priority queue Q Key each vertex in Q with the weight of the least Weight edge connecting it to a vertex in A Q lt V keyv lt 00 for all v e V keys lt 0 for some arbitrary s e V while Q 7 Q do u lt EXTRACTMINQ for each v e Adju do ifv e Q and wu v lt keyv then keyv lt wu v lgt DECREASEKEY TEV lt u At the end 12 TEV forms the MST 11607 CS 3343 Analysis ofAlgorilhms A1 GORi39I HMS u lt EXTRACTMINQ for each v e Adj u do ifv e Q and wu v lt keyv then keyv lt wu vlgt DECREASEKEY 11607 711v u CS 3343 Analysis ofAlgorilhms 10 A1 GORi39I HMS u lt EXTRACTMINQ for each v e Adj u do ifv e Q and wu v lt keyv then keyv lt wu vlgt DECREASEKEY 11607 711v u CS 3343 Analysis ofAlgorilhms 11 A1 GORi39I HMS u lt EXTRACTMINQ for each v e Adj u do ifv e Q and wu v lt keyv then keyv lt wu vlgt DECREASEKEY 11607 711v u CS 3343 Analysis ofAlgorilhms 12 A1 GORi39I HMS u lt EXTRACTMINQ for each v e Adj u do ifv e Q and wu v lt keyv then keyv lt wu vlgt DECREASEKEY 11607 711v u CS 3343 Analysis ofAlgorilhms 13 u lt EXTRACTMINQ for each v e Adju d0 ifv e Q and wu v lt keyv then keyv lt wu vlgt DECREASEKEY TV u 11607 CS 3343 Analysis ofAlgorilhms 14 u lt EXTRACTMINQ for each v e Adj u do ifv e Q and wu v lt keyv then keyv lt wu vlgt DECREASEKEY TV u 11607 CS 3343 Analysis ofAlgorilhms 15 u lt EXTRACTMINQ for each v e Adju 39 d0 ifv e Q and wu v lt keyv then keyv lt wu vlgt DECREASEKEY TV u 11607 CS 3343 Analysis ofAlgorilhms 16 u lt EXTRACTMINQ for each v e Adju 39 quot d0 ifv e Q and wu v lt keyv then keyv lt wu vlgt DECREASEKEY 11607 711v u CS 3343 Analysis ofAlgorilhms 17 A1 0mm HMS Example of Prim s algorithm 614 QEVA u lt EXTRACTMINQ for each v e Adj u do ifv e Q and wu v lt keyv then keyv lt wu vlgt DECREASEKEY TV u 11607 CS 3343 Analysis ofAlgorilhms 18 A1 GORi39I HMS u lt EXTRACTMINQ for each v e Adj u do ifv e Q and wu v lt keyv then keyv lt wu vlgt DECREASEKEY TV u 11607 CS 3343 Analysis ofAlgorilhms 19 A1 0mm HMS u lt EXTRACTMINQ for each v e Adj u do ifv e Q and wu v lt keyv then keyv lt wu vlgt DECREASEKEY TV u 11607 CS 3343 Analysis ofAlgorilhms 20 A1 GORi39I HMS u lt EXTRACTMINQ for each v e Adj u do ifv e Q and wu v lt keyv then keyv lt wu vlgt DECREASEKEY TV u 11607 CS 3343 Analysis ofAlgorilhms 21 A1 GO Ri THMS u lt EXTRACTMINQ for each v e Adju d0 ifv e Q and wu v lt keyv then keyv lt wu vlgt DECREASEKEY TV u 11607 CS 3343 Analysis ofAlgorilhms 22 Analysis ofPrim Q lt V 90 VD keyv 00 for all v e V tota keys 0 for some arbitrary S e V While Q 2 do u EXTRACTMINQ IVI for each v e Aa u times degredu do if v e Q and wu v lt keyv mes then keyv wu v 7v u Handshaking Lemma gt E implicit DECREASEKEY S Time l myTEXTRACTMIN IED TDECREASEKEY 11607 CS 3343 Analysis ofAlgorilhms 23 s Analysis of Prim continued Time l myTEXTRACTMIN IED TDECREASEKEY Q TEXTRACTMIN TDECREASEKEY TOtal array 00m 01 00W binary heap Fibonacci 0logl 01 0EVlogV heap amortized amortized worst case 000 VD 000 VD 0IE 10 VD 11607 CS 3343 Analysis ofAlgorilhms 24 Kruskal s algorithm IDEA again greedy Repeatedly pick edge with smallest weight as long as it does not form a cycle 0 The algorithm creates a set of trees a forest 0 During the algorithm the added edges merge the trees together such that in the end only one tree remains The correctness of this greedy strategy is not obvious and needs to be proven Proof skipped here 11607 CS 3343 Analysis ofAlgorilhms 25 Example of Kruskal s algorithm S21h9 12 fgh MST edges 1 set repr Every node is a single tree 11607 CS 3343 Analysis ofAlgorilhms 26 Example of Kruskal s algorithm S21h9df 12 g h MST edges 1 set repr a Vt Edge 3 merged two singleton trees 11607 CS 3343 Analysis ofAlgorilhms 27 5 quot NVr 39 39I Example of Kruskal s algorithm 39 s21gg 12 911 gen MST edges 1 set repr 11607 CS 3343 Analysis ofAlgorilhms 28 5 quot NVr 39 39I Example of Kruskal s algorithm 39 sgg 12 911 men MST edges 1 set repr 11607 CS 3343 Analysis ofAlgorilhms 29 in NVr 39 39I Example of Kruskal s algorithm sgg 12 ghe1bcf MST edges 1 set repr 11607 CS 3343 Analysis ofAlgorilhms 30 Example of Kruskal s algorithm I r S 1 g u Ehmhg MST edges 1 set repr Vt Edge 8 merged the two bigger trees 11607 CS 3343 Analysis ofAlgorilhms 31 39 Example of Kruskal s algorithm S g Q9 ha a9 by Ca f9 MST edges 1 set repr 11607 CS 3343 Analysis ofAlgorilhms 32 Example of Kruskal s algorithm I l z Sg 12 9habcfd MST edges 1 set repr Skip edge 10 as it would cause a cycle 11607 CS 3343 Analysis ofAlgorilhms 33 Example of Kruskal s algorithm S g MST edges 1 set repr Skip edge 12 as it would cause a cycle 11607 CS 3343 Analysis ofAlgorilhms 34 Example of Kruskal s algorithm S g 12 g h a b c f d MST edges 1 set repr Skip edge 14 as it would cause a cycle 11607 CS 3343 Analysis ofAlgorilhms 35 Example of Kruskal s algorithm S h ab cf 13 MST edges 1 set repr Disjoint set data structure UnlonFlnd Maintains a dynamic collection of pairwisedisjoint sets 8 51 52 Sr Each set Si has one element distinguished as the representative element Supports operations 01 MAKESETx adds new set x to S 006n UNIONx y replaces sets Sx Sy with Sx U Sy 006n FINDSETx returns the representative of the set Sx containing element x 39 1 lt 0604 lt10gn lt10g10gn lt10gn 11607 V r CS 3343 Analysis ofAlgorilhms 37 IDEA Repeatedly pick edge with smallest weight as long as it does not form a cycle Kruskal s algorithm S lt lgt Swill contain all MST edges 0Vl for each v EV do MAKESETV 0E10glEl Sort edges of E in nondecreasing order according to w 0E For each uv e E taken in this order do if FINDSETu 2 FINDSETv 1gt uv in different trees 0aV A lt A u uv UNIONuv gt Edge uv connects the two trees Runtime OVElogEEoc Vl OE log E 11607 CS 3343 Analysis ofAlgorilhms 38 Chapter 8 Dynamic Programming Those who do not remember the past are con demned to repeat it George Santayana Introduction 2 Example Computing Fibonacci Numbers 3 Computing Binomial Coefficients 4 Definition of Binomial Coefficients 4 Table for Computing Binomials 5 Binomial Algorithm 6 Comments on Binomial Algorithm 7 Warshall s Algorithm 8 Transitive Closure 8 Bad Algorithm for Transitive Closure 9 ldea Behind Warshall s Algorithm 10 Warshall s Algorithm 11 Example of Warshall s Algorithm 12 Example Continued 13 Other Dynamic Programming Problems 14 Optimal Binary Search Tree 14 The Knapsack Problem 15 Example for the Knapsack Problem 16 Introduction Dynamic programming is a technique for solving problems with the following properties D An instance is solved using the solutions for smaller instances D The solution for a smaller instance might be needed multiple times D The solutions to smaller instances are stored in a table so that each smaller instance is solved only once E Additional space is used to save time cs 3343 Analysis ofAlgorithrns Chapter 8 Slide7 2 Example Computing Fibonacci Numbers Compare recursive solution exponential algorithm ifn 0 or n 1 then return n else return Fn 7 1 Fn 7 2 To dynamic programming solution linear algorithm AlO lt7 0A1lt71 for i lt7 2 to n do lt7 Ali 7 1 Ali 7 2 return Aln cs 3343 Analysis ofAlgorithrns Chapter 8 5m 7 3 Computing Binomial Coefficients 4 Binomiai Algorithm Definition of Binomial Coefficients algorithm BmomzaKn k D The binomial coefficient denoted Cn k or is the number of subsets of k Computes Cn k using dynamic programming elements from an n element set Input Integers n 2 k 2 O D The binomial formula is Output The value of Cn k ab Cn0a Cnka kbkCnnb for Z T O to n do forj H O to minz k do B One prOperty of binomial coefficients is ifj O orj 239 then CnkOn 1k 1Cn 1k Abdel t Cn0 Cnn 1 Else AliaJ 9 All 1 1AZ 17 return An k D A dynamic programming approach stores the values of Cn k as they are com PUted CS 3343 Analysis of Algorithms Chapter 8 Slide 6 CS 3343 Analysis of Algorithms Chapter 8 Slide 4 Comments on Binomial Algorithm Table for computmg Bmom39als D The algorithm computes each value Cz39j once wherej g 239 j g k and O 1 l 2 k l lt 2 S 1 1 1 D 2 12kk1k1 1 terms n k 1 terms k1 1 ogjgzltk ogjgkgzgn E D n1 1 Cn 1lt 1 Cn 1lt k k 1 n 1 W k1n k1k1n1 k2enk FIGURE 81 Table for computing the binomial coefficient Cn k by the dynamic B More WE are in exerCises programming algorithm CS 3343 Analysis of Algorithms Chapter 8 Slide 5 CS 3343 AhabSis 0f Algorithms Chapter 81 Slide 7 Warshall s Algorithm 8 Idea Behind Warshall s Algorithm Transitive Closure D The idea is to process each vertex as an intermediate vertex D Suppose a path dacbe D The transitive closure of a directed graph is the set of pairs ij where there D Consider a Edges d a and a 2 imply d c in the transitive closure is a path from vertex 239 to vertexj D Consider b Edges 21 and 196 imply c e in the transitive closure D If ij is an edge it is in the transitive closure D Consider c Edges d c and c e in the transitive closure imply d e in it D If 33 and j k are in the transitive closure then so is 239 too a a a g 19 g g a i 19 f 1d cs 3343 Analysis ofAlgorithms Chapter 8 Slide 10 0 0 2h 3 3 sj j a 2 lj a d 1 0w 0 d 1 1g 1 Warshall s Algorithm FIGURE 82 a Dlgraph b Its adjacency matrix C ltS transitive closure cs 3343 Analysis of Algorithms Chapter 8 Slide 8 algorithm WarshallA1n Computes transitive closure matrix Bad Algorlthm for TranSItlve Closure Input Adjacency matrix A Output Transitive closure matrix R R H A algorithm BadTransitiveClosureA1n Doesn t compute transitive closure lnput Adjacency matrix A for Z T 1 to n do Output Transitive closure matrix R fork 9110 71 d0 R 9 A If Rlzj and El k then Rlz k 9 true forje1tondo forz39e1tondo forj H 1 to 73 do rewm R for k H 1 to 73 do This algorithm is 033 if Rli and RU k then cs 3343 Analysis of Algorithms Chapter 8 Slide 11 Rlz k 9 true return R Example of Warshall s Algorithm Need to repeat triple loop until no changes so 00 CS 3343 Analysis of Algorithms Chapter 8 Slide 9 Ones reflect the existence of paths with no intermediate vertices Hi0 is just the adjacency matrix boxed row and column are used for getting Rm Hlo QOOQ Ones reflect the existence of paths with intermediate vertices numbered not higher than 1 ie just vertex 8 note a new path from dto b boxed row and column are used for getting 82 RH QOU Q 0 4COO 40000 Ones reflect the existence of paths with intermediate vertices numbered Rm not higher than 2 ie a and b note two new paths boxed row and column are used for getting 33 AOAAQQOAOQOOAOQ II II II I AOOCDQ AOOOQJ AOOOQJ 4004 posa QOO Q CS 3343 Analysis of Algorithms Chapter 8 Slide 12 Chapter 4 Divide and Conquer Divide each difficulty into as many parts as is feasible and necessary to resolve it Rene Descartes Introduction 2 Illustration 3 General DivideandConquer Recurrence 4 The Master Theorem 5 Mergesort 6 Mergesort Algorithm 6 Merge Algorithm 7 Illustration 8 Comments on Mergesort 9 Analysis of Mergesort 10 Quicksort 11 Quicksort Algorithm 11 Partition Algorithm 12 Illustration 13 Comments on Quicksort 14 Binary Search 15 Binary Search Algorithm 15 Illustration Comments on Binary Search 17 Closest Pair 18 Idea for Closest Pair 18 Closest Pair Algorithm 19 Comments on Closest Pair 20 Convex Hull 21 First Idea for Convex Hull 21 Second Idea for Convex Hull 22 Quickhull Algorithm 23 Quickhull Algorithm Continued 24 Comments on Quickhull 25 Introduction The Master Theorem Divideand conquer is an approach to solving a problem by For the recurrence Tn aTnb if fn E nd then D Elrlde En lnstzlillnce into smaller instances of the problem nd if a lt bd D c0 veb39l etshma elr tlllStanc39lce fl ll 39 t 39 t I t39 f th I Tlquot E quotd log n if a 2 bd D I om me e so u Ions o e sma er lns ances in o a so u ion or e arger nlogba if a gt bd lnstance cs 3343 Analysis of Algorithms Chapter2 Slide 2 Note Tn Z Also Tn Z alogbn 7110ng because recurrence tree has at least alogb nodes Examples Mergesort Tn 2Tn2 n n log n Binary Search Tn Tn2 1 log n Strassen s Tn 7Tn2 732 n10g27 CS 3343 Analysis of Algorithms Chapter 2 Slide 5 Illustration Mergesort solution to solution to subproblem 1 subproblem 2 Mergesort Algorithm solution to the original problem FIGURE 41 Divide and conquer technique typical case CS 3343 Analysis of Algorithms Chapter 2 Slide 3 Sorts a given array mergesort Input An array A of orderable elements General DivideandConquer Recurrence Output Array AlOoon 1l in ascending order if n lt 1 then The general case is to divide an instance of size 73 into a instances of size 7319 CO py Am 1 to BK 1 taking fn time to divide and combine copy 1 to ClOlnZl 1 MergesortB T01 a Tnb l MergesortC time for number of time for time for jwmngeltB7 C A size n subinstances size 7319 divide 84 combine cs 3343 Analysis of Algorithms Chapter 2 Slide 6 Some examples are Mergesort T Binary Search Tn Tn2 1 Strassen s Tn 7Tn2 nZ CS 3343 Analysis of Algorithms Chapter 2 Slide 4 2Tn2 l n Merge Algorithm Comments on Mergesort D Note that n in Mergesort algorithm MergeBOp 1COq 1 D Note that 0 g 239 g p 0 g j 3 q and 7Lj k in Merge algorithm AOp q 1 Comparison only happens if both 339 lt p and j lt q Merges two sorted arrays into one array D 2 recursive calls to Mergesort on instances of size 732 Copy and merge is Input Sorted arrays B and C Output Sorted array A D Constant factor can be improved by more efficient use of arrays i F O F 0 cs 3343 Analysis of Algorithms Chapter 2 Slide 9 forkeOtOerq 1do ifiltpand jqor 30M then AW 9 BW Z 9 51 AnalySIs of Mergesort else D The number of comparisons C73 is AUG 9 017 J mj1 C73 g 20732 n 1 CS 3343 Analysis ofAIgorithms Chapter 2 Slide 7 lj Base cases for n a power Of 2 O 1 lt 5 lt D Induction assuming CnZ S 1032712 Illustration C72 S 20022 n 1 83297154 S g nlog2n2 n 1 g nloan nlogZZJrn 1 g nloan n l n 1 g n log2 73 CS 3343 Analysis of Algorithms Chapter 2 Slide 10 12 3 4 5 7 8 9 CS 3343 Analysis of Algorithms Chapter 2 Slide 8 Quicksort Quicksort Algorithm algorithm QuicksoitAl1m Sorts a subarray by quicksort Input An subarray of A Output Array Al1139r in ascending order ifl lt r then p lt7 PmtitionAltxr p is index of pivot Quicksor A up 7 1 Quicksor Ab 11139r CS 3343 Anzlysls ofAlgorlthms Chapter 2 Slld27 11 Partition Algorithm algorithm PartitionAl1m Partitions a subarray using Al as pivot Input Subarray ofA Output Final position of pivot pivot lt7 AU i lt7 l j lt7 39r 1 repeat repeat i lt7 i 1 until 2 pivot repeat j lt7 j 7 1 until Aj g pivot ifi lt j then swap and Aj until i 2 j swap Al and Aj return j CS 3343 Anzlysls ofAlgorlthms Chapter 2 Slld27 12 Illustration 53198274 CS 3343 Anzlysls ofAlgorlthms Chapter 2 Sllde e 13 Comments on Quicksort D Partition ensures that ifp is the final position of the pivot then i lt p implies g Ap and i gt p implies Z Ap Best Case If Partition always splits subarray in half then Tn 2Tn2 n E nlog Worst Case If pivot is always picks min or max then Tn Tn 71 n E nZ Average Case Randomly chosen pivot is nlog D In medianof three partitioning pivot is median of leftmost rightmost and middle element D Finding median is n with a modification El El El CS 3343 Anzlysls ofAlgorlthms Chapter 2 Sllde e 14 Binary Search 15 Closest Pair 18 Binary Search Algorithm algorithm BinarySearchA0n 17 K Searches a sorted array using binary search Input An sorted array A and a key K Output The index of K or 1 l 9 O 7 9 n 1 while l g r do m 9 10 7 21 if K Am then return m else ifK lt Am then r 9 m 1 else I 9 m 1 return 1 CS 3343 Analysis of Algorithms Chapter 2 Slide 15 Idea for Closest Pair XC K d K V CS 3343 Analysis of Algorithms Chapter 2 Slide 18 Illustration K 31 values in A 3 l142731394255707481l859398 indicesofA O 1 2 3 4 5 6 7 8 9101112 iteration 1 l m r iteration 2 l m r iteration 3 l m r iteration 4 lmr CS 3343 Analysis of Algorithms Chapter 2 Slide 16 Comments on Binary Search U BinarySearch ensures that AU 1 lt K or Z 0 and K lt Ar 1 or rzn l D The number of possible indices is r l 1 which reduces by half or more each iteration D The number of times 71 can divided by 2 until it becomes lt 1 is about log2n exact 1 log2 CS 3343 Analysis of Algorithms Chapter 2 Slide 17 Closest Pair Algorithm algorithm ClosestPairP Finds closest pair of points Input A set of n points sorted by coordinates Output Distance between closest pair if n lt 2 then return 00 else if n 2 then return distance between pair else 2 9 median value for x coordinate d1 9 ClosestPairpoints with x lt C d2 9 ClosestPairpoints with x gt C d H H1111ltdl7 d2 d3 9 process points with c d lt x lt c d return mind7 d3 CS 3343 Analysis of Algorithms Chapter 2 Slide 19 10 Comments on Closest Pair D Preprocessing can sort the points by their 1 and y coordinates use two lists Recursive calls can create sorted lists for subsets of points D The calculation of d3 is Select points with c d lt 1 lt c d Examine points in order of y values For any point 1y there can only be a few points within 1 i dy i d D Preprocessing is nlog and recurrence is Tn 2Tn2 n E nlogn CS 3343 Analysis of Algorithms Chapter 2 Slide 2O Convex Hull 21 Quickhull Algorithm algorithm QuickhulKP Finds convex hull Input A set of n points Output A list of points all of convex hull P1 9 point in P with lowest 1 value P2 9 point in P with highest 1 value A 9 points in P above m B 9 points in P below m return P1 P2 14 P2 and P1 CS 3343 Analysis of Algorithms Chapter 2 Slide 23 First Idea for Convex Hull P1 FIGURE 48 Upper and lower hulls of a set of points CS 3343 Analysis of Algorithms Chapter 2 Slide 21 Second Idea for Convex Hull FIGURE 49 The idea of quickhull CS 3343 Analysis of Algorithms Quickhull Algorithm Continued algorithm QHWalkP1 P2 P Finds convex hull clockwise from P1 to P2 Input Two points and a set of n points Output A list of points part of convex hull if n g 1 then return P else P3 9 point in P farthest from m A 9 points in P left 016m B 9 points in P left of return P3 A P3 and P1 CS 3343 Analysis of Algorithms Chapter 2 Slide 24 Chapter 2 Slide 22 11 12 Chapter 3 Brute Force Adequacy is sufficient Adam Osborne Introduction 2 Bubble Sort and Selection Sort 3 Bubble Sort 3 Correctness of Bubble Sort 4 Selection Sort 5 Efficiency of Selection Sort 6 Brute Force String Matching 7 BruteForce String Matching 7 Analysis of BruteForce String Matching 8 Closest Pair and Convex Hull 9 Closest Pair Problem 9 ClosestPair BruteForce Algorithm 10 The Convex HuII Problem 11 Examples of Convex Sets 12 Example of Convex HuII 13 Idea for Solving Convex HuII 14 Development of Idea for Convex HuII 15 Exhaustive Search 16 Exhaustive Search 16 TSP Example 17 TSP Solution 18 Knapsack Problem Example 19 Knapsack Problem Solution 20 Introduction efficiency Example an 0n algorithm for aquot algorithm Powera n Input A real number a and an integer n 2 0 Output aquot result lt7 1 for i lt7 1 to n do result lt7 result as a return result C5 3343 Analysts ofAlgorlthms Brute force is a straightforward approach to solving a problem without regard for Chapter 3 Sllde e 2 Correctness of Bubble Sort D If A is not sorted sorted is set to false and loop continues D Once a pair of elements are swapped the won t be swapped again D n elements have nn 712 different pairs so at most nn 712 swaps so loop must eventually exit D The number of comparisons is 9n2 See book C5 3343 Analysts ofAlgorlthms Chapter 3 Sllde e A Bubble Sort and Selection Sort Bubble Sort My bubble sort varies from the book algorithm BubbleSorKA0n7 1 Sorts a given array by bubble sort Input An array A of orderable elements Output Array A0n7 1 in ascending order sorted lt7 false while sorted do sorted lt7 true forjlt70ton72do if Aj gt Aj 1 then swap AU and Aj 1 sorted lt7 false C5 3343 Analysts ofAlgorlthms Chapter 3 Sllde e 3 Selection Sort algorithm SelectionSordA0n 7 1 Sorts a given array by selection sort Input An array A of orderable elements Output Array A0n7 1 in ascending order forilt70ton72do min lt7 i forjlt7i1ton71do if Aj lt Amz39n then min lt7i swap and Amz39n C5 3343 Analysts ofAlgorlthms Chapter 3 Sllde e 5 Efficiency of Selection Sort Correct because is minimum of A in7 The i 0 pass outer loop iteration performs n 7 1 comparisons The i 1 pass performs n 7 2 comparisons The lasti n 7 2 pass performs 1 comparison The number of comparisons Cn is 9n2 IIIIIIII H72 H71 7 7 7n71nNn Cn7n71717k7 2 k1 i0 C5 3343 Analysts ofAlgorlthms Chapter 3 Sllde e 5 Brute Force String Matching Closest Pair and ConvexHull Brute Force String Matching algorithm BmteForceSm39ngMatch Implements bruteforce string matching Input Text array T and pattern array P Output The index where P is found or 71 forilt70ton7mdo j lt7 0 whilej lt m and PM TIi j do J H ifj m then return i return 71 CS 3343 AnzIysis ofAIgorithms TI0ttn71P0um71 Chapter 3 Shde e 7 Analysis of Brute Force String Matching Correct because every possible index i is checked 139 n 7 m is the highest possible index There are n 7 m 1 values for 139 CS 3343 AnzIysis ofAIgorithms D D D At worst m comparisons are made for a given value of i D D The number of comparisons is g mn 7 m 1 g mn E 0mn Chapter 3 Shde e s Closest Pair Problem D A point 2D case is an ordered pair of values at y D The Euclidean distance between two points B am y and 967 is dpi7pj 96 957392 M WV D The closestpair problem is finding the two closest points in a set of n points D The brute force algorithm checks every pair of points which will make it nZ D We can avoid computing square roots by using squared distance CS 3343 AnzIysis ofAIgorithms Chapter 3 Shde e g Closest Pair Brute Force Algorithm algorithm BruteFo rceClosestPai39rfP Finds two closest points by brute force Input A list P ofn Z 2 points Output The indices of the closest pair 11min lt7 oo forilt71ton71do forjlt7i1tondo d 9 96 95792 M i W2 if d lt 11min then 11min lt7 d imm lt7 139 min lt7 j return 2min jmz39n CS 3343 AnzIysis ofAIgorithms Chapter 3 Shde e 10 The Convex Hull Problem D A region set of points in the plane is convex if every line segment between two points in the region is also in the region B The convex hull of a finite set of points P is the smallest convex region containing P D Theorem The convex hull of a finite set of points P is a convex polygon whose vertices is a subset of P D The convex hull problem is finding the convex hull given P CS 3343 Analysis of Algorithms Chapter 3 Slide 11 Examples of Convex Sets O a b FIGURE 34 a Convex sets b Sets that are not convex CS 3343 Analysis of Algorithms Chapter 3 Slide 12 Idea for Solving Convex Hull D Consider the straight line that goes through two points B and D Suppose there are points in P on both sides of this line This implies that the line segment between B and is not on the boundary of the convex hull D Suppose all the points in P are on one side of the line or on the line This implies that the line segment between B and Pj is on the boundary of the convex hull CS 3343 Analysis of Algorithms Chapter 3 Slide 14 Development of Idea for Convex Hull D The straight line through R and Pj mjyj can be defined by a nonzero solution for CUEZ byz c axj byj c B One solution is a yj yi b 32 xj and c xiyj yixj D The line segment from B to is on the convex hull if either ax by Z c or am by g c is true for all the points D Brute force algorithm is 023 See book CS 3343 Analysis of Algorithms Chapter 3 Slide 15 Example of Convex Hull CS 3343 Analysis of Algorithms Chapter 3 Slide 13 cs 3343 Spring 2009 con rms More on Shortest Paths Carola Wenk Slides comtesy of Charles LeiseIson with small anges by Carola Wenk mst summonamt m Negativeweight cycles Recall If a graph G V E contains a negative weight cycle then some shOItest paths may not exist Example BellmanFord algorithm Finds all shortestpath weights from a source s E Vto all 1 E Vor detennines that a negativeweight cycle exists ansm c liAmlym army th 2 U BellmanFord algorithm dv e 0 for eachv E V7 s initialization do v e co forieltolVlildo for each edge u v e E do if div gt dill WW7 V 18quot relaxation diquot F dill Wuv V step v e u for each edge u v e E do if dv gt du wu v then repon that a negativeWeight cycle exists At the end dv 5s 1 Time OUVHED Mst c fidemzlyJu gmgmm Example of BellmanFord Order of edges BE DB ED AB AC DC BC ED A B C D E 0 oo oo oo oo ansm c lfAmlym 17mg th t 535413 Example of BellmanFord Example of BellmanFord Brder ofedges 53 DB ED AB AC Dc BC ED Erder ofedges BE DB ED AB AC D C BC ED 1 A B C D E 71 A B C D E 0 oo oo oo oo 0 00 00 00 00 00 0 1 0 0 00 0 71 oo oo oo 0 fl 4 oo 00 41509 CS AmlquAlgamhm 5 mm mmmwwmwm 5 g Example of BellmanFord 1 Example of BellmanFord Order ofedges 53 DB ED AB AC Dc BC ED Order ofedges BE DB ED AB AC D C BC ED B C D E A B C D E m m 1 0 00 00 0 71 oo oo oo 1 4 0 00 0 fl 4 so so 1 2 00 co 0 71 2 00 00 41509 minimums mtg th 7 mm murmur mayth

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.