DESIGN AND ANALYSIS OF ALGORITHMS
DESIGN AND ANALYSIS OF ALGORITHMS COMP 482
Popular in Course
Popular in ComputerScienence
This 50 page Class Notes was uploaded by Cleora Stiedemann on Monday October 19, 2015. The Class Notes belongs to COMP 482 at Rice University taught by Staff in Fall. Since its upload, it has received 33 views. For similar materials see /class/224965/comp-482-rice-university in ComputerScienence at Rice University.
Reviews for DESIGN AND ANALYSIS OF ALGORITHMS
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/19/15
CMP 482 l ELEC 420 Maximum Network Flow Skim CLRS 2225 Graphs minimum spanning trees shortest paths Covered in previous courses but a refresher is always good See how Dijsktra s shortest path alg can use Fibonacci heaps Read CLRS 26 What if weights in a graph are maximum capacities of some flow of material Pipe network to transport fluidgas eg water oil natural gas 002 Edges pipes Vertices junctions of pipes Data communication network Edges network connections of different capacity Vertices routers do not produce or consume data just move it Also used in resource planning economics ecosystem network analysis Formalization Flow network Directed graph GVE One source and one sink We ll generalize later Each edge has Each vertex is on some capacity cuv 2 0 path from s to t Formalization Flow How much is currently flowing f V x V a R fVuZfvu veV fuVZfuv veV Must satisfy 3 properties Capacity constraint Vuv e V fuv s cuv SkeW Symmetwi Total value of flow f Flow conservation Vu e V st fuV fVu 0 What goes in must go out Example flows Valid or invalid Why Maximum flow problem Find fto maximize f Maximum flow Algorithm idea If we have some flow and can find an augmenting path p from 5 tot can add a constant amount of flow along path El agt0 V uve p fuv a s cuv Then just do it to get a better flow Find an augmenting path in the example FordFulkerson method FordFulkersonGst l initialize flow f to O everywhere 2 while there is an augmenting path p do 3 augment flow f along p 4 return f How do we findchoose an augmenting path How much additional flow can we send through that path Does the algorithm always find the maximum flow http algoviz cs vt eduAlgovizWikiNetworkFlow Augmenting Augmenting path any path in the residual network Residual network GfVEf Ef uv e V gtltV cfuv gt 0 Residual capacities cfuv cuv fuv Residual capacity of path p cfp mi cfuv uv p 1319 v 7 23 Residual capacity of path scdt Observe Edges in Ef are either edges in E or their reversals Ef s 2E 1o FordFulkerson method with details FordFulkersonGst l for each edge uvEGE do 2 fuv fvu O 3 while G from s to t j112residual network Gf do 4 cf mincfuv uvep 5 for each edge uv p do 6 fuv fuv Cf 7 fVu fuv 8 return f Algorithms based on this method differ in how they choose p Does it always find a maximum flow First some definitions Cut a partition of V into ST such that se 8 teT T fST Zfuv ueSVeT 219 9 15 23 cST Zcuv ueSVeT Minimum cut a cut with the smallest capacity of all cuts Does it always find a maximum flow Maxflow mincut theorem The following are equivalent statements 1 fis a maximum flow in G 2 The residual network Gf contains no augmenting paths 3 f cST for some out ST of G 1 We prove three parts 1 7 34 2 From this we have 2e1 which means that the Ford Fulkerson method always correctly finds a maximum flow What is the worstcase running time Augmentation OE How many augmentations Let s assume integer flows Each increases the value of the flow by some integer Of where f is the maxflow Total worstcase OEgtltf Example How an augmenting path is chosen is very important EdmondsKarp algorithm Use shortest augmenting path in edges Run algorithm on our example EdmondsKarp algorithm analysis 1 Augmentation OE Breadthfirst search Will prove augmentations OVE Let dv be distance from s to v in residual network Will prove Every E iterations dt increases by 21 dt can increase at most M times a OVE iterations Total OVEZ EdmondsKarp algorithm analysis 2 Will prove Every E iterations dt increases by 21 Consider the residual network in levels according to dv As long as dt doesn39t change the paths found will only use forward edqes Each iteration saturates amp removes at least 1 forward edge and adds only backward edges so no distance ever drops After removing E dt 1 forward edges twill be disconnected from 5 80 within E iterations either t is disconnected amp algorithm terminates or A nonforward edge used amp dt increased Other MaxFlow Algorithms More complex but asymptotically faster Problem important thus wellstudied Pushrelabel Goldberg amp Tarjan 1986 OVE log V2E 2 Described in CLRS In practice mostused approach King Rao amp Tarjan 1994 OVE IOgEVlog V V Goldberg amp Rao 1998 OminV23E12 E ogV2E2 log maxwGE cuv Variation Multiple sources or sinks What if we have more sources or sinks Augment the graph to make it with one source and one sink Variation Node capacities What if nodes have maximum flows oioi Convert into a edge capacity 20 Variations Any combination of Multiple sources amp sinks Node capacities amp possibly no edge capacities Minimum edgenode flows Sources amp sinks also conserve flow circulation Multiple distinct flow commodities Flows have costs which are to be minimized Integral flows Some can be restated as maxflow some can be solved by extensions of same algs some NP complete 21 Application Maximum Bipartite Matching Matching in a graph is a subset M of edges such that each vertex has at most one edge of M incident on it It puts vertices in pairs q Bipartite V LR E g LxR A maximum Eg dating agency 22 Application Maximum Bipartite Matching up VLR EQLXR How can we reformulate as a maxflow problem What is the running time using EdmondsKarp 23 CMP 482 l ELEC 420 Skip Lists Skim CLRS 10 12 13 background amp related Read Skip Lists A Probablistic Alternative to Balanced Trees by Pugh 1990 Review Should be familiar with many kinds amp uses of trees eg Binary search trees Balanced trees Heaps Syntax trees Spanning trees This course More search trees More heaps Tnes Balanced Trees Overview Many variations but common implementation themes Most interested in dictionaries Create insert delete search Thus frequently are variations on binary search trees Want Olog n per operation Implementation often uses rotations Maintains the searchtree ordering A lt x lt B lt y lt C Can change tree depth based on depths on A B C Background Some Balanced Search Tree Variations Randomlybuilt BST Reasonably balanced in expected case Only feasible if all inserts happen first amp can randomize their relative order AVL tree 1962 BST Guarantees depths of all leaves differ by at most 1 Balancing requires Olog n rotations RedBlack tree 1972 BST Guarantees depth of all leaves within a factor of 2 Balancing requires at most 2 rotations AAtree 1996 Easiertocode variant of RedBlack tree Background Some Balanced Search Tree Variations 23 tree 1970 Search tree where nodes have either 2 or 3 children and 1 or 2 keys respectively Guarantees depth of all leaves within a constant factor lsomorphic to AAtree 234 tree Generalization of 23 trees Guarantees depth of all leaves equal Lower constant costs than 23 trees because only makes one pass on tree instead of two on each operation lsomorphic to RedBlack tree Btree 1972 23n tree Bushy a increase spatial locality Shallow a minimize the number of node accesses Most suitable for huge data sets as in databases Background Some Search Tree Variations Treap 19801989 BST also maintaining heap property Conceptually simple Low constant costs but logarithmic bounds only expected Skip list 1990 Singlylinked sorted list with extra pointers to later in list Conceptually fairly simple High space overhead for lots of pointers and logarithmic bounds only expected Splay tree 1983 Selfadjusting ie changes tree even on noninsertdelete operations so as to improve later accesses Logarithmic bounds only when amortized Trie 1960 Specialized to strings Lineartime in length of input Many variations Some Applets http www site uottawa castancsi2514app1etsav1BThtml http www ececs uc edufrancoC321htm1RedBlackredblack html http wwwcsunmedur1pm499ttfthtm1 http babbage clarku eduachouc5160fal103examp1esbstanimation TreapExample html http peop1e ksp skkukobak m 4 http www cis ksu eduhowe11viewerviewer html Skip Lists Overview Intuitive idea but trickier details Logarithmic bounds only expected Analysis is a useful example Linear in worstcase Worstcase search Start with singlylinked sorted list n Add ptrs between every 2ncl element nZ Add ptrs between every 4th element n4 Add ptrs between every 2i39th element Vi Ig n Behaves just like 3 BST Level 3 V r r r r r r r r Problem Rigid location of pointers difficult to maintain when insertingdeleting r r r V 11 Level ANOO Solution Only keep the right proportions of pointers Each node is at a particular level 100 level 1 50 level 2 25 level 3 12i level i1 Level 4N0 7 1 Using top level links search 2 For each next level search bounded by previous Level ANOO Informal ExpectedCase Analysis of nextlowerlevel nodes skipped per link of levels Expected lg n Expected 2 Search Search of top level 81 Bounded search of each next level 81 per level Total log n r L L L y L L L r y y r 7 Level ANOO Informal ExpectedCase Analysis Used probability p12 of adding link to next level What if we generalize of nextlowerlevel nodes skipped per link of levels Expected log1Io n Expected 1p Search Search of top level 81 Bounded search of each next level 81 per level Total log n Soon More formal more precise amp pick optimal p Insert 1 Search for where n belongs Remember last link at each level Exit if value found M 15 ANOO Insert 1 Search for where n belongs Remember last link at each level Exit if value found 2 Create node Choose its level k probabilistically 3 For i1 replace last links Increase head node s level if necessary Level ANOO 1 Search forcing search to go on each level Remember last link on each level Exit if value not found Level ANOOh 1 Search forcing search to go on each level Remember last link on each level Exit if value not found 2 Replace last links Decrease start node s level if necessary 3 Delete node Level Formal ExpectedCase Analysis of Search We ll analyze a search backwards From the item upwards amp leftwards Ck expected length of search path when climbing k levels Equivalent to count either 1 or gt r r L L L L L L y y r y y 7 Level ANOO Formal ExpectedCase Analysis of Search Ck expected length of search path when climbing k levels Base case CO O Level ANOO gt r r L L L L L L y y r y y r Formal ExpectedCase Analysis of Search Ck expected length of search path when climbing k levels Inductive case Ck prob gtlt cost prob gtlt cost I I I I I I 22 Level ANOO Formal ExpectedCase Analysis of Search Ck expected length of search path when climbing k levels Inductive case Ck 1pgtlt1Ck pgtlt1Ck1 I I I I I I 23 Level ANOO Formal ExpectedCase Analysis of Search Ck expected length of search path when climbing k levels Inductive case Ck 1D gtlt 1Ck p X 1Ck1 1 Ck p pCk p pCk1 0 1 pCk pCk1 Ck 1p Ck1 kp Level ANOO gt r r L L L L L L y y r r y r Formal ExpectedCase Analysis of Search How many levels Intuition log1Io n But could unluckily have a very tall node How likely Prnode x is at or above level i pi1 Prnode x is at or above level 12log1Io n p239091p 1m2 PrEI node at or above level 12log1Io n n x 1n2 1m Pr E node at or above level 12log1Io n 1 1n Level ANOO Formal ExpectedCase Analysis of Search Expected length of search path 1 2log1pn 0 with high probability Minimized by p1e With probability 1 1n for some constant c 26 Numerous implementation choices eg how to represent nodes Time Pretty good fairly low constants Space OK More pointers amp larger nodes than many comparable balanced trees 27
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'