### Create a StudySoup account

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

Already have a StudySoup account? Login here

# ADVANCED ALGORITHMS COT 5405

FSU

GPA 3.58

### View Full Document

## 98

## 0

## Popular in Course

## Popular in OTHER

This 10 page Class Notes was uploaded by Miller Gibson on Thursday September 17, 2015. The Class Notes belongs to COT 5405 at Florida State University taught by Staff in Fall. Since its upload, it has received 98 views. For similar materials see /class/205397/cot-5405-florida-state-university in OTHER at Florida State University.

## Popular in OTHER

## Reviews for ADVANCED 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: 09/17/15

COT 5405 Fall 2006 Lecture 26 Maximum Flow Problem Flow Networks De nition A ow network G V E is a directed graph where each edge a v E E has a non negative capacity c a v 2 0 o If a v then we take ca v 0 0 Two special vertices s t E V s t are denoted as the sink and soarce respectively For every v EV there is a path from s to tthrough v 0 So lEzVl I 0 De nition A ow is f V X V gt 9 that satisfies the following constraints 0 Capacity constraint Va v EVfa v s ca v o Skew symmetry Va v EVfa v fv a 0 Flow conservation Va EV s t Eva u v 0 De nition The value of a owfis defined as lf 2 EV EVfs v Maximum ow problem Given a ow network find a ow of maximum value 0 Multiple sourcesmultiple sinks maximum ow problem can be solved by creating a supersink and a supersource with edges to and from the sinks and sources having infinite capacities Implicit summation notationfX Y 2 6X2 EY x y when X YQV Lemma 261 1 VXQVfXX 0 2 VX YQVfX Y fY X 3 VX Y ZQV with X Y a XUY Z fX Z fY Z and Z XUY fZ X fZ Y Proof for 1 the rest are review questions Label the vertices in X as x1 x2 xk X X 2 EXZy ex x Y Zkid get Zkid Zgti xi xj 39 Zkid Z i xj x1 yi12gtifxi xj 39 Z131 Zigtj xf x1 yi12gti xi xj quotyi12gtifxi x39 2212 x39 39 xp 0 1 x xj Zkid Zgti xi xj Zkid Zlti x39 t 29 COT 5405 Fall 2006 Lecture 27 FordFulkerson Method Residual Networks Given a ow the residual network consists of edges that can admit more ow De nition The residual capacity of edge u v is given by cfu v cu v fu v De nition A residual network is defined by G V E where E u v E V X V cu v gt 0 Lemma If f is the ow for G V E and G V E is the induced residual network with owf thenff defined by ffu v fu v fu v is a ow in G with value lffl If lfl Proof We will prove that ff has all the properties of a ow and then determine that value of this ow Capacity constraints ffu v fu v fu v s fu v cu v fu v cu v fu v cu v Skew symmetry ffu v fu v fu v fv u fv u fv u fv u ffv u Flow conservation Let u E V s t EV EV ffu v 2 EV EV fu v fu v ZvEVfu V ZvEVqu V 0 0 0 Flow value lffl 2 Eva ffs v 2 Eva fs v fs v Evev s v Evaf0 V lfl lfl Augmenting Path De nition Given G V E and ow f an augmenting path p is a simple path from s to tin G f De nition The residual capacity of an augmenting path p is given by cp mincfu v u v Ep Lemma Definefp V X V gt Wbyfpm v i cfp if u v Ep ii cp if v u Ep and iii 0 otherwise Thefp is a ow in G with value 02 cp gt 0 Corrollary f ffp is a ow in G with value fl If 12 gt lfl COT 5405 Fall 2006 Lecture 26 Maximum Flow Problem Flow Networks De nition A ow network G V E is a directed graph where each edge a v E E has a non negative capacity c a v 2 0 o If a v then we take ca v 0 0 Two special vertices s t E V s t are denoted as the sink and soarce respectively For every v EV there is a path from s to tthrough v 0 So lEzVl I 0 De nition A ow is f V X V gt 9 that satisfies the following constraints 0 Capacity constraint Va v EVfa v s ca v o Skew symmetry Va v EVfa v fv a 0 Flow conservation Va EV s t Eva u v 0 De nition The value of a owfis defined as lf 2 EV EVfs v Maximum ow problem Given a ow network find a ow of maximum value 0 Multiple sourcesmultiple sinks maximum ow problem can be solved by creating a supersink and a supersource with edges to and from the sinks and sources having infinite capacities Implicit summation notationfX Y 2 6X2 EY x y when X YQV Lemma 261 1 VXQVfXX 0 2 VX YQVfX Y fY X 3 VX Y ZQV with X Y a XUY Z fX Z fY Z and Z XUY fZ X fZ Y Proof for 1 the rest are review questions Label the vertices in X as x1 x2 xk X X 2 EXZy ex x Y Zkid get Zkid Zgti xi xj 39 Zkid Z i xj x1 yi12gtifxi xj 39 Z131 Zigtj xf x1 yi12gti xi xj quotyi12gtifxi x39 2212 x39 39 xp 0 1 x xj Zkid Zgti xi xj Zkid Zlti x39 t 29 COT 5405 Fall 2006 Lecture 28 EdmondsKarp Algorithms FordFulkerson Method Ford Fulkerson G s t o For each edge 11 V EE 0 fu V e 0 fV u e 0 0 While there is an augmenting path p from s to t in GE 0 CAP e minCfUz v u v 6p o for each 11 V Ep 39 fU V fU V CfP 39 fV u e fu V An arbitrary search for an augmenting path leads to 0IE lfl algorithm with integer capacities where If I is the maximum flow EdmondsKarp Algorithm Method In the Ford Fulkerson method when finding p perform breadth first search and choose the shortest path from s to tas p Each BFS takes 0 IE I time since IE I 2 lVlI from our definition of a flow network We will show below that the number of augmentations is 0IV IE I and so the total time complexity is 0IV IE F Lemma The shortest path distance from the source in the residual gs V increases monotonically with each augmentation for each v in V 3 t Proof Assume the contrary Then there exists v E V 3 t such that some augmentation causes the shortest path to decrease Let v be the vertex with smallest 53 v for which this happens Let f be the flow when this happens and f be the previous flow 53 v lt 513 v from our assumption Letp s gt u gt v be a shortest path from s to v in G So 53 u 53 v I Also 53 u 2 513 u Note that u v Ef Otherwise we would have 5 v 5 53 u I s 53 u I 53 v contradicting our assumption Since u v E but is in E v u must have been on the augmenting path in G So 513 v 2 513 u I s 53 u I 53 v 2 contradicting our assumption QED De nition Edge u v EE is critical if IF Cu v Theorem 269 The number of augmentations in the Edmonds Karp algorithm is OV IEI Proof We will show that an edge can become critical at most lVl2 times Since each augmentation requires at least one critical edge this will prove that the number of augmentations is 0 IV IE I Let the ow be f the first time some edge u v becomes critical It can become critical again in fact appear in the residual again only after v u appears in an augmenting path Let f be the ow when v u appears on an augmenting path Then 53 u 63 v I a 63 v I 63 u 2 Since 53 u 5 IV u v can become critical at most lVl2 times QED COT 5405 Fall 2006 Lecture 27 FordFulkerson Method Residual Networks Given a ow the residual network consists of edges that can admit more ow De nition The residual capacity of edge u v is given by cfu v cu v fu v De nition A residual network is defined by G V E where E u v E V X V cu v gt 0 Lemma If f is the ow for G V E and G V E is the induced residual network with owf thenff defined by ffu v fu v fu v is a ow in G with value lffl If lfl Proof We will prove that ff has all the properties of a ow and then determine that value of this ow Capacity constraints ffu v fu v fu v s fu v cu v fu v cu v fu v cu v Skew symmetry ffu v fu v fu v fv u fv u fv u fv u ffv u Flow conservation Let u E V s t EV EV ffu v 2 EV EV fu v fu v ZvEVfu V ZvEVqu V 0 0 0 Flow value lffl 2 Eva ffs v 2 Eva fs v fs v Evev s v Evaf0 V lfl lfl Augmenting Path De nition Given G V E and ow f an augmenting path p is a simple path from s to tin G f De nition The residual capacity of an augmenting path p is given by cp mincfu v u v Ep Lemma Definefp V X V gt Wbyfpm v i cfp if u v Ep ii cp if v u Ep and iii 0 otherwise Thefp is a ow in G with value 02 cp gt 0 Corrollary f ffp is a ow in G with value fl If 12 gt lfl Cuts of Flow Networks De nition A cut S T of G V E is a partition of Vinto S and T such that T V S 3 ES and t ET De nition The net ow across the cut S T is defined as f S T De nition The our capacity is c S T De nition A minimum cut is a cut with minimum capacity Lemma Flow across any cut S T is fS T lfl Proof39 S T fS V fS S fS V fs V fSs V fs V lfl Note that f Ss V 0 by flow conservation Corrollary The value of any flow is bounded above by the capacity of any cut MaxFlow MinCut Theorem If f is a flow in a flow network G V E with source s and sink t then the following are equivalent 1 fis a max flow in G 2 G contains no augmenting path 3 lf 2 cS T for some cut S T of G Proof 1 3 2 Assume the contrary The flow sumf fp is a valid flow with If fp gt lfl leading to a contradiction 2 3 Define S v in V El a path from s to Vin G and T V S For each u E S and v E Tfu v Cu v So If fS T cS T 3 3 I If scS T for all cuts So if lf 2 cS T then the flow is the maximum possible COT 5405 Fall 2006 Lecture 22 RabinKarp Algorithm The Idea Interpret strings as numbers by interpreting symbols as digits in 0 I IZII Example 2 61 b c d e f g h i j Interpret this as 0 I 2 3 4 5 6 7 8 9 So the string acdab is interpreted as 02302 Let p be the value of the pattern P This can be computed in 0m time using Horner s rulep Pm 10PmI 10Pm2 t0 the value of TI m can similarly be computed in 0m time Note that IN 10ts 10 quot391Ts1 Tsm1 can be computed in constant time if we pre computelOm 1 in 0m time In order to find all matches we can compare p with If for each s The time complexity is 0mn 0n RabinKarp Algorithm The numbers involved in the application of the above idea may be very large So we work in modulo q 2 IZI Define 39 p pq 39 to is defined in a similar manner Rabin KarpT P 39 Pre processing to compute p39 and t0 39 fors0tor1 m o if p39 5 I if Pl m Tsl sm 39 Print 5 I if s lt n m t5 2t5 h Tsl Tsml q h 2m1 q This takes 9nm1m time in the worst case COT 5405 Fall 2006 Lecture 23 DFA for String matching Finite Automaton Set of states Q Start state q E Q Set of accepting states A Q Q Alphabet Z Transition function 5 Q XE gt Q mewsoe General Construction Scheme Final state junction w is the state after scanning w 39 5 q0 39 wa 5 w a w 62 a GE Suffix nction 0x maxk PI k is a suffix of x 39 0x is the length of the longest prefix ofP that is also a suffix of x 39 P0 a is a suffix of all strings Construction Q 0 I m q0 0 A m 5q a 0an 39 Note C26 m iff P is a suffix of x implying that a match has been found DFAbased Matching FA MatcherT 6 m Iqlto 39foriltor1 o qlt 5qTi oifq I Print i m This takes 9n time and 9m IZI space Correctness of Construction We wish to prove that the state is 0Ti after scanning TI i That is we wish to prove that T 02 Theorem 324 T 0T i 0 11 Proof We prove the theorem by induction on i Base case To 0 0T0 Induction hypothesis Assume T XI We wish to prove that TM 2 0TM TM 2 TiTi1 6 T Ti1 from the definition of ab 0P Ti Ti1 from the definition of 6 0P0m Ti1 from the induction hypothesis 2 0Ti Ti1 from lemma 323 0TM QED Constructing 6 39for q O to m 9mtime o for each a E 2 902 time I k lt ml I Repeat k lt k l 0m time 39 until Pk is a suffix of an 0m time 39 5q a lt k This takes 0m3 IZI time This can be improved to 0m IZI

### 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 made $350 in just two days after posting my first study guide."

#### "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!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

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