Notes: 1. MINIMUM SPANNING TREES a) PRIM’S ALGORITHM PRIM(G, w, r ) // r b el o n g s t o V, O( ElgV ) runnin g time u si n g Min−Heap data s t r u c t u r e 01 f o r each u i n V 02 key [ u ] = i n f i n i t y // wei gh t o f edge c o n n e c ti n g u t o a v e r t e x i n S , where S i s the cu t ( d yn amic all y ch an gin g ) 03 pi [ u ] = NIL // p a ren t 04 c o l o r [ u ] = WHITE 05 key [ r ] = 0 06 Q = V // o r d e r e d by key [ u ] , Q = V−S . i n i t i a l l y i s a l l the v e r t i c e s i n V 07 w hil e Q i s not empty 08 u = EXTRACT−MIN(Q) , c o l o r [ u ] = BLACK // add u t o S 09 f o r each v e r t e x v i n Adj [ u ] 10 i f c o l o r [ v ] == WHITE && w( u , v ) < key [ u ] 11 pi [ v ] = u 12 key [ v ] = w( u , v ) 13 key [ ∗ ] , pi [ ∗ ] b) KRUSKAL’S ALGORITHM KRUSKAL (G, w) //O( ElgV ) r u n ni n t time 01 X = EMPTY LIST //MAINTAIN EDGES IN MST BUILDING 02 f o r each v e r t e x u i n V 03 MAKESET( u ) 04 S o r t (E) // i n a s c e n di n g o r d e r o f wei gh t 05 f o r each edge ( u , v ) i n E 06 i f FIND( u ) <> FIND( v ) 07 X = X U {( u , v )} 08 UNIOIN( u , v ) 09 r e t u r n X MAKESET( x ) // e ve r y v e r t e x has rank , h ei g h t o f s u b t r e e hanging from t h a t ve r te x , RUNNING TIME:O( 1 ) 01 pi ( x ) = x 02 rank ( x ) = 0 FIND( x ) // f o l l o w s p a ren t p o i n t e r s t o r o o t o f t r e e , RUNNING TIME: PROPORTIONAL TO TREE HEIGHT 01 w hil e x <> pi ( x ) 02 x = pi ( x ) 03 r e t u r n x 1 UNION( x , y ) 01 LINK(FIND( x ) , FIND( y ) ) LINK( x , y ) 01 i f rank ( x ) > rank ( y ) 02 pi ( y ) = x 03 e l s e pi ( x ) = y 04 i f rank ( x ) = rank ( y ) 05 rank ( y ) = rank ( y ) + 1 2. a) fordFulkersonWithBFS The BFS procedure should return true if there exists a path from s to t and false otherwise. It should also fill in the P[], parent, list to store the path defined at 6. Algorithm 2 is a modification of BFS for this purpose. b) BFSAugmented 2 3.DIJKSTRA ALGORITHM (USE MIN-HEAP DATA STRUCTURE) DIJKSTRA(G, w, s ) //G = (V, E) i n a d j a c e n c y l i s t format , w = weight , s = s o u r c e v e r t e x 01 f o r each v e r t e x v i n V 02 d [ v ] = i n f i n i t y // di s t a n c e 03 pi [ v ] = n i l // p a ren t 04 d [ s ] = 0 05 Q = empty // c r e a t e a min−heap Q 06 f o r each v e r t e x v i n V 07 I n s e r t −Heap (Q, v , d [ v ] ) //v i s index , d [ v ] i s v al u e put i n t o node 08 w hil e Q != empty 09 u = Ex trac t−Min (Q) 10 f o r each v e r t e x v i n Adj [ u ] 11 i f d [ v ] > d [ u ] + w( u , v ) 12 d [ v ] = d [ u ] + w( u , v ) 13 Dec rease−Key (Q, v , d [ v ] ) 14 pi [ v ] = u MIN−HEAP OPERATIONS: MIN−HEAP−INSERT(A, key ) heap−s i z e [A] <− heap−s i z e [A] + 1 A[ heap−s i z e [A ] ] <− +i n f HEAP−DECREASE−KEY(A, heap−s i z e [A] , key ) HEAP−DECREASE−KEY(A, i , key ) i f key > A[ i ] then e r r o r ”new key i s l a r g e r than c u r r e n t key ” A[ i ] <− key w hil e i> 1 and A[ p a ren t ( i ) ] > A[ i ] do exchange A[ i ] <−> A[ p a ren t [ i ] ] i <− p a ren t ( i ) HEAP−EXTRACT−MIN(A) 3 i f heap−s i z e [A] < 1 then e r r o r ” heap unde r fl ow ” min <− A[ 1 ] A[ 1 ] <− A[ heap−s i z e [A ] ] 1 Forest Finding Let G = (V, E, w) be a weighted, undirected graph. A decycler is a set of edges D ⊂ E such that for any cycle C ⊆ E, C ∩ D = ∅. Our goal is to find a decycler of minimum weight. • (6 points) Write pseudocode for an algorithm which takes G = (V, E, w) as input, runs in O(E log V ) time, and returns a minimum-weight decycler. 2 Tree Codes A common task is to find an efficient representation of some data. In this problem, we will consider how to represent a sequence of colors as efficiently as possible using binary strings (bitstrings). For example, suppose we have the following data: [Blue, Gold, Red, Magenta, Red, Red, Gold, Silver] Consider the following two mappings from colors to bitstrings: Color Mapping A Mapping B Blue 00 110 Gold 10 00 Red 111 01 Magenta 01 111 Silver 110 10 If we replace our sequence of colors with the corresponding bitstrings and concatenate, mapping A yields 00101110111111110110, which has a total length of 20 bits. However, mapping B gives us 110000111101010010, which uses only 18 bits, so it is a more efficient representation for our data. In general, given a sequence of (not necessarily distinct) colors, we to design an algorithm which finds an assignment of binary strings to each color which uses the fewest bits possible. However, to make our output easier to read, we will also require that no color has a bitstring which begins with another color’s bitstring (e.g., we cannot assign ”0” to Gold and ”01” to Blue). A good way to do this is to build a rooted binary tree (NOT a BST) where the leaves represent our colors and the path from the root to a leaf determines its bitstring (a 0 represents going left once, while a 1 represents going right once). Another key idea is to construct the tree from the bottom upwards, starting with the least frequent colors - it is more efficient to assign longer bitstrings to these colors and shorter bitstrings to more frequent colors. You can use a heap to store colors (or combinations of colors) prioritized by frequency. • (5 points) Write pseudocode for an algorithm which takes as input a sequence of colors C[1, . . . , n] and outputs the binary tree described above. Your algorithm should run in O(n lg n) time. • (1 point) Give a worked example on a sequence of at least 11 colors, of which 5 or more are distinct. • (1 point) Argue why this process ensures that no color has a bitstring which begins with another color’s bitstring. • (2 points) Now, reverse this process. Write pseudocode for an algorithm which takes as input a bitstring S[1, . . . , n] and a binary tree T built using the algorithm above, and outputs the sequence of colors C[1, . . . , n] which maps to this string using the mapping given by T. 4 3 Spymaster We have a set of n spies each of whom needs to meet exactly one messenger from a set of n messengers. The set of possible locations [m] = {1, · · · , m} where they can meet. For each spy i, there is a subset Si ⊆ [m] of the possible locations where spy i can go. Similarly, there is a subset Mi ⊆ [m] of the possible locations where messenger i can go. Moreover, each location j can handle at most cj pairs of spy-messenger meetings. The task is to decide if there is a possible way to match up spies and messengers such that every pair meets at one of their common locations. Formally, does there exist a permutation σ on n vertices (mapping spies to messengers) and a function ` : [n] → [m] mapping spies to locations such that 1. ∀i ∈ [n], `(i) ∈ Si ∩ Mσ(i) (every spy-messenger pair meets at a location which they can both visit) 2. ∀j ∈ [m], |{i | `(i) = j}| ≤ cj (the capacity of each location is not exceeded) • (3 points) Write the pseudocode which given n, m, {Mi}, {Si} decides if such a pairing is possible. • (2 points) Give a proof of the correctness of your algorithm. 4 Saturation We are given a flow network G = (V, E, s, t, c) and some valid flow f. Recall that an edge is saturated under f if f(e) = c(e). In this problem, we will examine whether the saturated edges can tell us something about the max flow and min cut in G. a) (1 points) We say that f is a blocking flow if for every directed path from s to t, there is a saturated edge some￾where along the path. Does this imply that f must be a maximum s t flow? Prove or give a counterexample. b) (1 points) If f is a maximum s t flow, consider the set S of saturated edges. Let c(S) = Pe∈S c(e) be the total capacity of S. Is c(S) equal to the minimum total capacity of any s t cut? Prove or give a counterexample. 5 Min-cut with the fewest edges Given a flow network G = (V, E, s, t, c) with integer capacities, you would like to find the min-cut which contains the fewest number of edges among all min-cuts in G. • (4 points) Write pseudocode for an algorithm which solves this problem in O(E2V ) time. • (3 points) Prove that your algorithm returns a min cut with the fewest edges. In other words, if your algorithm returns a min cut with k edges, show that any other min cut must have at least k edges. 6 Edmonds-Karp We will develop a slightly modified implementation of the Ford-Fulkerson method using a greedy idea to choose augmenting paths. Consider a flow network G = (V, E, s, t, c) where c(e) ≥ 1 for all e ∈ E. We define the widest path as the augmenting path with the most capacity. a) (2 points) Modify Dijkstra’s algorithm to compute the widest path. b) Let’s say that we select the choose the widest path during each iteration of Ford-Fulkerson. Let’s try to prove a bound on its complexity. • (2 points) Show that the maximum flow in G is at most c|E| where c is the flow through the widest path. • (1 point) Let f0 = f ∗ and let fn denote the remaining flow after n iterations. Prove a recurrence between fn and fn+1 using the previous observation. • (1 point) Use your recurrence to conclude that we terminate O(|E| log |f ∗|) iterations. Hint - You can use that for 0 < x < 1, log(1 x) ≤ −x 5 7 Programming Please complete the HW7 programming assignment in Problem6 folder. Read the README file for instructions. Fill in hw7.py for this problem. Code should pass tests in tests folder and all other cases not covered by tests provided.