Midterm 2 answers

TRUE [ TRUE/FALSE ] When finding the value of the optimal solution in a dynamic programming algorithm one must find values of optimal solutions for all of its sub-problems. 2) 15 pts Given a sequence of n real numbers A 1 …A n , give an efficient algorithm to find a subsequence (not necessarily contiguous) of maximum length, such that the values in the subsequence form a strictly increasing sequence. Let A[i] represent the i-th element in the sequence. initialize OPT[i] = 1 for all i. best = 1 for(i = 2..n) { for(j = 1..i-1) { if(A[j] < A[i]) { OPT[i] = max( OPT[i], OPT[j] + 1 ) } best = max( best, OPT[i] ) } } return best The runtime of the above algorithm is O(n^2)

5) 20 pts Given the graph below with demands/supplies as indicated below and edge capacities and possible lower bounds on flow marked up on each edge, find a feasible circulation. Show all your work -10 35 -5 20 -30 -10 C= 20 C=20 L= 10 C= 20 C= 20 C= 10 C= 20 L= 10 C= 30 C= 5 C= 30 C= 20 C= 10 L = 5

-20 35 -10 -10 0 -5 10 C=10 C=20 C=5 C=10 C=30 C=20 C=20 C=5 C=10 C=30 C=20 T S C=35 C=10 C=10 C=20 C=5 C=10 f1 -20 35 -10 -10 0 -5 10 0 20 5 0 0 15 10 5 0 30 20 Circulation = f0+f1

CS570 Analysis of Algorithms Fall 2010 Exam II Name: _____________________ Student ID: _________________ ____Monday ____Friday ____DEN Maximum Received Problem 1 20 Problem 2 20 Problem 3 20 Problem 4 20 Problem 5 20 Total 100 2 hr exam Close book and notes If a description to an algorithm is required please limit your description to within 150 words, anything beyond 150 words will not be considered.

3) 20 pts King Arthur’s court had n knights. He ruled over m counties. Each knight i had a quota q i of the number of counties he could oversee. Each county j , in turn, produced a set S j of the knights that it would be willing to be overseen by. The King sets up Merlin the task of computing an assignment of counties to the knights so that no knight would exceed his quota, while every county j is overseen by a knight from its set S j . . Show how Merlin can employ the Max-Flow algorithm to compute the assignments. Provide proof of correctness and describe the running time of your algorithm. (You may express your running time using function F(v, e) , where F(v, e) denotes the running time of the Max-Flow algorithm on a network with v vertices and e edges.) We make a graph with n+m+2 vertices, n vertices k 1 ,…,k n corresponding to the knights, m vertices c 1 ,…,c m corresponding to the counties, and two special vertices s and t . We put an edge from s to k i with capacity q i . We put an edge from k i to c j with capacity 1 if county j is willing to be ruled by knight i . We put an edge of capacity 1 from c j to t . We now find a maximum flow in this graph. If the flow has value m , then there is a way to assign knight to all counties. Since this flow is integral, it will pick one incoming edge for each county c j to have flow of 1 . If this edge comes from knight k i , then county j is ruled by knight i . The running time of this algorithm is F(n+m+2, +n+m ).

CS570 Analysis of Algorithms Fall 2014 Exam II Name: _____________________ Student ID: _________________ Email:______________________ Thursday Evening Section Maximum Received Problem 1 20 Problem 2 16 Problem 3 16 Problem 4 16 Problem 5 16 Problem 6 16 Total 100 Instructions: 1. This is a 2-hr exam. Closed book and notes 2. If a description to an algorithm or a proof is required please limit your description or proof to within 150 words, preferably not exceeding the space allotted for that question. 3. No space other than the pages in the exam booklet will be scanned for grading.

3) 16 pts There are a series of part-time jobs lined up one after the other , 𝐽 1 , 𝐽 2 , … , 𝐽 𝑛 . For any ? 𝑡ℎ part-time job, you are getting paid ? 𝑖 amount of money. Also for the ? 𝑡ℎ part-time job, you are also given ? 𝑖 , which is the number of immediately following part-time jobs that you cannot take if you perform that ? 𝑡ℎ job. Give an efficient dynamic programming solution to maximize the amount of money one can make. Also state the runtime of your algorithm. For 1 <= ? <= ? , let ? 𝑖 denote a solution for the set of jobs { 𝐽 𝑖 , .... , 𝐽 𝑛 }, ? 𝑖 maximizes the amount of money, and let opt (?) denote its amount of money. If ? 𝑖 chooses to take job 𝐽 𝑖 , then it has to exclude 𝐽 𝑖+1 through 𝐽 𝑖+𝑁 𝑖 . In this case, its money is ? 𝑖 plus the money it earns for the set { 𝐽 𝑖+𝑁 𝑖 +1 ,..., 𝐽 𝑛 }. Since ? 𝑖 is optimal for the set { 𝐽 𝑖 ,.., 𝐽 𝑛 }, ? 𝑖 restricted to the subset { 𝐽 𝑖+𝑁 𝑖 +1 ,..., 𝐽 𝑛 } has to be optimal. Thus in this case, opt (?) = ? 𝑖 + opt (? + ? 𝑖 + 1) . If ? 𝑖 chooses not to take job 𝐽 𝑖 , then the amount of money one can earn is the money from the set of jobs { 𝐽 𝑖+1 ,..., 𝐽 𝑛 }. Since ? 𝑖 is optimal for the set { 𝐽 𝑖 ,.., 𝐽 𝑛 }, ? 𝑖 restricted to the subset { 𝐽 𝑖+1 ..., 𝐽 𝑛 } has to be optimal. Thus in this case, opt (?) = opt (? + 1) . We thus have a recurrence for all ? , opt (?) = max(opt (? + 1) , opt (? + ? 𝑖 + 1) + ? 𝑖 ). (We understand that opt(index > n) = 0). The boundary condition is that opt (?) = ? 𝑛 and we start solving recurrence starting with opt(n), opt(n-1) and so on until opt(1). Complexity of this solution is O(n).

4) 16 pts Consider the below flow-network, for which an s-t flow has been computed. The numbers in the boxes give the capacity of each edge, the label next to an edge gives the flow sent on that edge. If no flow is sent on that edge then no label appears in the graph. a. What is the current value of flow? (2 pts) b. Show the residual graph for the corresponding flow-network. (2 pts) c. Calculate the maximum flow in the graph using the Ford-Fulkerson algorithm. You need to show the augmenting path at each step, show the final max flow and a min cut. (12 pts) Note: extra space provided for this problem on next page/ a) Current value of the flow is 7. b) Residual graph is shown below 7 16 8 9 11 5 12 7 10 16 7 7 s c a b d t t 9 8 2 11 5 12 0 10 16 s c a b 7 7 7 0 0 0 0 0 0 d t

Additional Space for Problem 4 c) Augmenting paths for one of the maximum flow are a. S->a->d->t, increment in flow along these edges is 9. b. S->b->d->t, increment in flow along these edges is 3. Final network-flow graph is shown below. Maximum flow is 19. Edges in the minimum cut are (c,t) and (d,t). 7 9 12 3 3 16 16 8 9 11 5 12 7 10 16 7 s c a b d t Min-cut

5) 16 pts You are given an n-by-n grid, where each square (i, j) contains c(i, j) gold coins. Assume that c(i, j)>=0 for all squares. You must start in the upper-left corner and end in the lower-right corner, and at each step you can only travel in one the following three ways: 1- one square down which costs you 1 gold coin, or 2- one square to the right which costs you 2 gold coins, or 3- one square diagonally down and to the right which costs you 0 gold coins When you visit any square, including your starting or ending square, you may collect all of the coins on that square. Give an algorithm to end up with the maximum number of coins and show how you can find the optimal path. Solution: let opt[i, j] be the maximum number of coins that it is possible to collect while ending at (i, j). We have the following recurrence for 0<= i<=n-1, 0<= j<=n-1. opt[i, j]= c(i, j)+ max(opt[i-1,j]-2, opt[i, j-1]-1, opt[i-1, j-1]) If we assume that borrowing, i.e., negative number of golds are fine the initial conditions are opt(i,-1)=opt(j,-1)=-inf , opt(0,0)=c(0,0) if the assumption is that borrowing is not allowed the initial conditions are opt(i,-1)=opt(j,-1)=-inf , opt(0,0)=c(0,0) ??𝑡(1,0) = { −??𝑓, 𝑐(0,0) − 2 < 0 𝑐(0,0) + 𝑐(1,0) − 2, 𝑐(0,0) − 2 ≥ 0 ??𝑡(0,1) = { −??𝑓, 𝑐(0,0) − 1 < 0 𝑐(0,0) + 𝑐(0,1) − 1, 𝑐(0,0) − 1 ≥ 0 There are n 2 subproblems, and each takes O(1) time to solve. Thus, the running time is O(n 2 ). To find the optimal path one can trace back through the recursive formula for different i,j values.

6) 16 pts You need to transport iron-ore from the mine to the factory. We would like to determine how long it takes to transport. For this problem, you are given a graph representing the road network of cities, with a list of k of its vertices (t 1 , t 2 ,…, t k ) which are designated as factories, and one vertex S (the iron-ore mine) where all the ore is present. We are also given the following: - Road Capacities (amount of iron that can be transported per minute) for each road (edges) between the cities (vertices). - Factory Capacities (amount of iron that can be received per minute) for each factory ( at t 1 , t 2 ,…, t k ) Give a polynomial-time algorithm to determine the minimum amount of time necessary to transport and receive all the iron-ore at factories, say C amount. Here we want to define a network-flow graph with a source, sink, and capacities on the edges. In the given graph we already have a source S (the iron-ore mine) vertex. Add a new sink vertex T to the graph, and add an edge between each of the factory to T. On each of this newly added edge, set the factory capacity given for that factory. On the remaining edges set the capacities given by the road capacities. We then run any polynomial-time max flow algorithm on the resulting graph; because it is polynomial in size (has only one additional vertex and at most n additional edges), the resulting runtime to compute max-flow (F) is polynomial. Now we have the maximum rate at which we can transport the iron-ore. So it takes minimum of 𝐶 𝐹 time to transport and receive all the iron-ore at factories.

Additional Space

CS570 Analysis of Algorithms Fall 2014 Exam II Name: _____________________ Student ID: _________________ Email:______________________ Wednesday Evening Section Maximum Received Problem 1 20 Problem 2 16 Problem 3 16 Problem 4 20 Problem 5 16 Problem 6 12 Total 100 Instructions: 1. This is a 2-hr exam. Closed book and notes 2. If a description to an algorithm or a proof is required please limit your description or proof to within 150 words, preferably not exceeding the space allotted for that question. 3. No space other than the pages in the exam booklet will be scanned for grading.

1) 20 pts Mark the following statements as TRUE or FALSE . No need to provide any justification. [/FALSE ] If an iteration of the Ford-Fulkerson algorithm on a network places flow 1 through an edge (u, v), then in every later iteration, the flow through (u, v) is at least 1. [ TRUE/] For the recursion T(n) = 4T(n/3) + n, the size of each subproblem at depth k of the recursion tree is 𝑛/3 ?−1 . [/FALSE ] For any flow network G and any maximum flow on G , there is always an edge e such that increasing the capacity of e increases the maximum flow of the network. [/FALSE ] The asymptotic bound for the recurrence T(n) = 3T(n/9) + n is given by Θ(n 1/2 log n). [/FALSE ] Any Dynamic Programming algorithm with n subproblems will run in O(n) time. [/FALSE ] A pseudo-polynomial time algorithm is always slower than a polynomial time algorithm. [ TRUE/] The sequence alignment algorithm can be used to find the longest common subsequence between two given sequences. [/FALSE ] If a dynamic programming solution is set up correctly, i.e. the recurrence equation is correct and each unique sub-problem is solved only once (memoization), then the resulting algorithm will always find the optimal solution in polynomial time. [ TRUE/] For a divide and conquer algorithm, it is possible that the divide step takes longer to do than the combine step. [ TRUE/] Maximum value of an ? − ? flow could be less than the capacity of a given ? − ? cut in a flow network.

2) 16 pts Recall the Bellman-Ford algorithm described in class where we computed the shortest distance from all points in the graph to t. And recall that we were able to find all shortest distance to t with only O(n) memory. How would you extend the algorithm to compute both the shortest distance and to find the actual shortest paths from all points to t with only O(n) memory? We need an array of size n to hold a pointer to the neighbor that gives us the shortest distance to t. Initially all pointers are set to Null. Whenever a node’s distance to t is reduced, we update the pointer for that node and point it to the node that is giving us a lower distance to t. Once all shortest distances are computed, to find a path from any node v to t, one can simply follow these pointers to reach t on the shortest path.

3) 16 pts During their studies, 7 friends (Alice, Bob, Carl, Dan, Emily, Frank, and Geoffrey) live together in a house. They agree that each of them has to cook dinner on exactly one day of the week. However, assigning the days turns out to be a bit tricky because each of the 7 students is unavailable on some of the days. Specifically, they are unavailable on the following days (1 = Monday, 2 = Tuesday, …, 7 = Sunday):  Alice: 2, 3, 4, 5  Bob: 1, 2, 4, 7  Carl: 3, 4, 6, 7  Dan: 1, 2, 3, 5, 6  Emily: 1, 3, 4, 5, 7  Frank: 1, 2, 3, 5, 6  Geoffrey: 1, 2, 5, 6 Transform the above problem into a maximum flow problem and draw the resulting flow network. If a solution exists, the flow network should indicate who will cook on each day; otherwise it must show that a feasible solution does not exist Solution: I will use the initials of each person’s name to refer to them in this solution. Construct a graph G = (V, E). V consists of 1 node for each person (let us denote this set by P = {A, B, C, D, E, F, G}), 1 node for each day of the week (let’s call this set D = {1, 2, 3, 4, 5, 6, 7}), a source node s, and a sink node t. Connect s to each node p in P by a directed ( s, p ) edge of unit capacity. Similarly, connect each node d in D to t by a directed ( d, t ) edge of unit capacity. Connect each node p in P by a directed edge of unit capacity to those nodes in D when p is available to cook. This completes our construction of the flow network. I am omitting the actual drawing of G here. Finding a max-flow of value 7 in G translates to finding a feasible solution to the allocation of cooking days problem. Since there can be at most unit flow coming into any node p in P, a maximum of unit flow can leave it. Similarly, at most a flow of value 1 can flow into any node d in D because a maximum of unit flow can leave it. Thus, a max- flow of value 7 means that there exists a flow-carrying s - p-d-t path for each p and d. Any ( p, d ) edge with unit flow indicates that person p will cook on day d . The following lists one possible max-flow of value 7 in G: Send unit flow on each ( s, p ) edge and each ( d, t ) edge. Also send unit flow on the following ( p, d ) edges: (A, 6), (B, 5), (C, 1), (D, 4), (E, 2), (F, 7), (G, 3)

4) 20 pts Suppose that there are 𝑛 asteroids that are headed for earth. Asteroid ? will hit the earth in time ? ? and cause damage ? ? unless it is shattered before hitting the earth, by a laser beam of energy ? ? . Engineers at NASA have designed a powerful laser weapon for this purpose. However, the laser weapon needs to charge for a duration ?? before firing a beam of energy ? . Can you design a dynamic programming based pseudo- polynomial time algorithm to decide on a firing schedule for the laser beam to minimize the damage to earth? Assume that the laser is initially uncharged and the quantities ?, ? ? , ? ? , ? ? are all positive integers. Analyze the running time of your algorithm. You should include a brief description/derivation of your recurrence relation. Description of recurrence relation = 8pts, Algorithm = 6pts, Run Time = 6pts Solution 1 (Assuming that the laser retains energy between firing beams): Sort all asteroids by the time ? ? . Label the asteroids from 1 to 𝑛 and without loss of generality assume ? 1 < ? 2 < ⋯ < ? 𝑛 . Also assume that if asteroid ? is destroyed then it is done exactly at time ? ? (if the laser continuously accumulates energy then the destruction order of the asteroids does not change even if ? 𝑡ℎ asteroid is shot down before time ? ? ). Define ??𝑇(?, 𝑇) as the minimum possible damage caused to earth due to asteroids ?, ? + 1, … , 𝑛 if 𝑇 ? energy is left in the laser just before time ? ? . We want the solution corresponding to ??𝑇(1, ? 1 ) . If 𝑇 ≥ ?? ? and the ? 𝑡ℎ asteroid is destroyed then ??𝑇(?, 𝑇) = ??𝑇(? + 1, 𝑇 − ?? ? + ? ?+1 − ? ? ) , otherwise ??𝑇(?, 𝑇) = ? ? + ??𝑇(? + 1, 𝑇 + ? ?+1 − ? ? ) . Hence, ??𝑇(?, 𝑇) = { ? ? + ??𝑇(? + 1, 𝑇 + ? ?+1 − ? ? ), 𝑇 < ?? ? min{? ? + ??𝑇(? + 1, 𝑇 + ? ?+1 − ? ? ), ??𝑇(? + 1, 𝑇 − ?? ? + ? ?+1 − ? ? )} , 𝑇 ≥ ?? ? Boundary condition: ??𝑇(𝑛, 𝑇) = 0 if 𝑇 ≥ ?? 𝑛 and ??𝑇(𝑛, 𝑇) = ? 𝑛 if 𝑇 < ?? 𝑛 , since if there is enough energy left to destroy the last asteroid then it is always beneficial to do so. Furthermore, 𝑇 ≤ ? 𝑛 since a maximum of 𝑡 𝑛 ? energy is accumulated by the laser before the last asteroid hits the earth and 𝑇 ≥ 0 since the left over energy in the laser is always non-negative. Algorithm: i. Initialize ??𝑇(𝑛, 𝑇) according to the boundary condition above for 0 ≤ 𝑇 ≤ ? 𝑛 . ii. For each 𝑛 − 1 ≥ ? ≥ 1 and 0 ≤ 𝑇 ≤ ? 𝑛 populate ??𝑇(?, 𝑇) according to the recurrence defined above. iii. Trace forward through the two dimensional ??𝑇 array starting at (1, ? 1 ) to determine the firing sequence. For 1 ≤ ? ≤ 𝑛 − 1 , destroy the ? 𝑡ℎ asteroid with 𝑇 ? energy left if and only if ??𝑇(?, 𝑇) = ??𝑇(? + 1, 𝑇 − ?? ? + ? ?+1 − ? ? ) . Destroy the 𝑛 𝑡ℎ asteroid only if 𝑇 ≥ ?? 𝑛 . Complexity: Step (i) initializes ? 𝑛 values each taking constant time. Step (ii) computes (𝑛 − 1)? 𝑛 values, each taking one invocation of the recurrence and hence is done in ?(𝑛? 𝑛 ) time. Trace back takes ?(𝑛) time since the decision for each ? takes constant time. Initial sorting takes ?(𝑛 log 𝑛) time. Thus overall complexity is ?(𝑛? 𝑛 + 𝑛 log 𝑛) .

Solution 2 (Assuming that the laser does not retain energy left over after firing and if asteroid 𝒊 if destroyed then it is done exactly at time 𝒕 𝒊 ): Sort all asteroids by the time ? ? . Label the asteroids from 1 to 𝑛 and without loss of generality assume ? 1 < ? 2 < ⋯ < ? 𝑛 . In contrast to Solution 1, the destroying sequence will change if we are free to destroy asteroid ? before time ? ? (this case is not solved here). Define ??𝑇(?) to be the minimum possible damage caused to earth due to the first ? asteroids. We want the solution corresponding to ??𝑇(𝑛) . If the ? 𝑡ℎ asteroid is not destroyed either by choice or because ? ? < ?? ? then ??𝑇(?) = ? ? + ??𝑇(? − 1) . On the other hand, if the ? 𝑡ℎ asteroid is destroyed ( ? ? ≥ ?? ? is necessary) then none of the asteroids arriving between times ? ? − ?? ? and ? ? (both exclusive) can be destroyed. Letting 𝑝[?] denote the largest positive integer such that ? 𝑝[?] ≤ ? ? − ?? ? (and 𝑝[?] = 0 if no such integer exists), we have ??𝑇(?) = ??𝑇(𝑝[?]) + ∑ ? ? ?−1 ?=𝑝[?]+1 if 𝑝[?] ≤ ? − 2 and ??𝑇(?) = ??𝑇(? − 1) if 𝑝[?] = ? − 1 . Hence for ? ≥ 1 , ??𝑇(?) = { ??𝑇(? − 1), ? ? ≥ ?? ? and 𝑝[?] = ? − 1 ? ? + ??𝑇(? − 1), ? ? < ?? ? min {? ? + ??𝑇(? − 1), ??𝑇(𝑝[?]) + ∑ ? ? ?−1 ?=𝑝[?]+1 } , ? ? ≥ ?? ? and 𝑝[?] ≤ ? − 2 Boundary condition: ??𝑇(0) = 0 since no asteroids means no damage. Algorithm: i. Form the array 𝑝 element-wise. This is done as follows. a. Set 𝑝[1] = 0 . b. For 2 ≤ ? ≤ 𝑛 , binary search for ? ? − ?? ? in the sorted array ? 1 < ? 2 < ⋯ < ? 𝑛 . If ? ? − ?? ? < ? 1 then set 𝑝[?] = 0 else record 𝑝[?] as the index such that ? 𝑝[?] ≤ ? ? − ?? ? < ? 𝑝[?]+1 . ii. Form array 𝐷 to store cumulative sum of damages. Set 𝐷[0] = 0 and 𝐷[?] = 𝐷[? − 1] + ? ? for 1 ≤ ? ≤ 𝑛 . iii. Set ??𝑇(0) = 0 and for 1 ≤ ? ≤ 𝑛 populate ??𝑇(?) according to the recurrence defined above, computing ∑ ? ? ?−1 ?=𝑝[?]+1 as 𝐷[? − 1] − 𝐷[𝑝[?]] . iv. Trace back through the one dimensional ??𝑇 array starting at ??𝑇(𝑛) to determine the firing sequence. Destroy the first asteroid if and only if ??𝑇(1) = 0 . For 2 ≤ ? ≤ 𝑛 , destroy the ? 𝑡ℎ asteroid if and only if either ??𝑇(?) = ??𝑇(? − 1) with 𝑝[?] = ? − 1 or ??𝑇(?) = ??𝑇(𝑝[?]) + 𝐷[? − 1] − 𝐷[𝑝[?]] with 𝑝[?] ≤ ? − 2 . Complexity: initial sorting takes ?(𝑛 log 𝑛) . Construction of array 𝑝 takes ?(log 𝑛) time for each index and hence a total of ?(𝑛 log 𝑛) time. Forming array 𝐷 is done in ?(𝑛) time. Using array 𝐷 , ??𝑇(?) can be populated in constant time for each 1 ≤ ? ≤ 𝑛 and hence step (iii) takes ?(𝑛) time. Trace back takes ?(𝑛) time since the decision for each ? takes constant time. Therefore, overall complexity is ?(𝑛 log 𝑛) .

5) 16 pts Consider a two-dimensional array A[1:n,1:n] of integers. In the array each row is sorted in ascending order and each column is also sorted in ascending order. Our goal is to determine if a given value x exists in the array. a. One way to do this is to call binary search on each row (alternately, on each column). What is the running time of this approach? [2 pts] b. Design another divide-and-conquer algorithm to solve this problem, and state the runtime of your algorithm. Your algorithm should take strictly less than O( 𝑛 2 ) time to run, and should make use of the fact that each row and each column is in sorted order (i.e., don't just call binary search on each row or column). State the run-time complexity of your solution. a) O( 𝑛 log 𝑛 ). b) Look at the middle element of the full matrix. Based on this, you can either eliminate A[ 1. . 𝑛 2 , 1. . 𝑛 2 ] or A[ 𝑛 2 . . 𝑛, 𝑛 2 . . 𝑛 ]. If 𝑥 is less than middle element then you can eliminate A[ 𝑛 2 . . 𝑛, 𝑛 2 . . 𝑛 ]. If 𝑥 Is greater middle element then you can eliminate A[ 1. . 𝑛 2 , 1. . 𝑛 2 ]. You can then recursively search in the remaining three 𝑛 2 × 𝑛 2 matrices. The total runtime is T(n) = 3T( 𝑛 2 )+O(1), T(n) = O( 𝑛 log 2 3 ).

6) 12 pts Consider a divide-and-conquer algorithm that splits the problem of size n into 4 sub- problems of size n/2. Assume that the divide step takes O(n^2) to run and the combine step takes O(n^2 log n) to run on problem of size n. Use any method that you know of to come up with an upper bound (as tight as possible) on the cost of this algorithm. Solution: Use the generalized case 2 of Master’s Theore m. For 𝑇(𝑛) = ?𝑇 ( 𝑛 ? ) + Θ(𝑛 log 𝑏 ? log ? 𝑛) with ? ≥ 0, we have 𝑇(𝑛) = Θ(𝑛 log 𝑏 ? log ?+1 𝑛) . The divide and combine steps together take ?(𝑛 2 log 𝑛) time and the worst case is that they actually take Θ(𝑛 2 log 𝑛) time. Hence the recurrence for the given algorithm is 𝑇(𝑛) = 4𝑇 ( 𝑛 2 ) + Θ(𝑛 2 log 𝑛) in the worst case. Comparing with the generalized case, ? = 4, ? = 2, ? = 1 and so 𝑇(𝑛) = Θ(𝑛 2 log 2 𝑛) . Since this expression for 𝑇(𝑛) is the worst case running time, an upper bound on the running time is ?(𝑛 2 log 2 𝑛) .

Additional Space

CS570 Analysis of Algorithms Spring 2007 Exam 2 Name: _____________________ Student ID: _________________ Maximum Received Problem 1 20 Problem 2 10 Problem 3 20 Problem 4 20 Problem 5 20 Problem 6 5 Problem 7 5 Note: The exam is closed book closed notes.

1) 20 pts Mark the following statements as TRUE or FALSE . No need to provide any justification. [ TRUE/FALSE ] True Max flow problems can in general be solved using greedy techniques. [ TRUE/FALSE ] False If all edges have unique capacities, the network has a unique minimum cut. [ TRUE/FALSE ] True Flow f is maximum flow if and only if there are no augmenting paths. [ TRUE/FALSE ] True Suppose a maximum flow allocation is known. Increase the capacity of an edge by 1 unit. Then, updating a max flow can be easily done by finding an augmenting path in the residual flow graph. [ TRUE/FALSE ] False In order to apply divide & conquer algorithm, we must split the original problem into at least half the size. [ TRUE/FALSE ] True If all edge capacities in a graph are integer multiples of 5 then the maximum flow value is a multiple of 5. [ TRUE/FALSE ] False If all directed edges in a network have distinct capacities, then there is a unique maximum flow. [ TRUE/FALSE ] True Given a bipartite graph and a matching pairs, we can determine if the matching is maximum or not in O(V+E) time [ TRUE/FALSE ] False Maximum flow problem can be efficiently solved by dynamic programming [ TRUE/FALSE ] True The difference between dynamic programming and divide and conquer techniques is that in divide and conquer sub-problems are independent

2) 10pts Give tight bound for the following recursion a) T(n)=T(n/2)+T(n/4)+n A simple method is that it is easy to easy that T(n)=4n satisfy the recursive relation. Hence T(n)=O(n) b) T(n) = 2T(n 0.5 )+logn Let n=2 k and k=2 m , we have T(2 k )= 2T(2 k/2 )+k and T(2 k/2 )= 2T(2 k/4 )+k/2 Hence T(2 k )=2(2T(2 k/4 )+k/2)+k=2 2 T(2 k/4 )+2k=2 3 T(2 k/8 )+3k=….=2 m T(1)+mk =2 m T(1)+m2 m . Note that n=2 k and k=2 m , hence m=log log n. We have T(n)=T(1)log n+(log log n)*(log n). Hence T(n)= (log log n)*(log n)

3) 20 pts Let A = (a 0 , a 1 , . . . , a n-1 ) be an array of n positive integers. a- Present a divide-and-conquer algorithm which computes the sum of all the even integers a i in A(1..n-1) where a i > a i-1 . Solutions other than divide and conquer will receive no credit. Algorithm: Compute-Even-Integers(l,r) if r=l+1 if((a r %2=0) and (a r >a l )) return a r else return 0 else let m=       + 2 r l Let S= Compute-Even-Integers(l,m)+ Compute-Even-Integers(m,r) If a m %2=0 and a m >a m-1 S=S+ a m To computes the sum of all the even integers a i in A(1..n-1) where a i > a i-1 , invoke Compute-Even-Integers(0,n-1) b- Show a recurrence which represents the number of additions required by your algorithm. T(n)=2T(n/2)+c

c- Give a tight asymptotic bound for the number of additions required by your algorithm. By master theorem, it is easy to see that T(n)=O(n) d- Discuss how your approach would compare in practice to an iterative solution of the problem. In practice, both methods are O(n) algorithm. Their complexity is the same.

4) 20 pts Families 1…..N go out for dinner together. To increase their social interaction, no two members of the same family use the same table. Family j has a(j) members. There are M tables. Table j can seat b(j) people. Find a valid seating assignment if one exists. We first construct a bipartite graph G whose node are the families f i (i=1,…,N) and the tables t j (j=1,…,M). We add edge e ij =( f i , t j ) in the graph for i=1,…,N and j=1,…,M and set e ij =1. Then we add a course s and sink in G. For each family f i , we add e=(s, f i ) in the graph and set c e =a(i). For each stable t j , we add e=( t j , t) and set c e =b(j) . After building the graph G for the original problem, we find the maximum s-t-flow value v in graph G by Fulkerson algorithm. If v is a(1)+…+a(N), then we make the seating assignment such that no two members of the same family use the same table, otherwise we can not. To prove the correctness of the algorithm, we prove that no two members of the same family use the same table if and only if the value of the maximum value of an s-t flow in G is a(1)+…+a(N): First if no two members of the same family use the same table, it is easy to see that this flow meets all capacity constraints and has value a(1)+…+a(N). For the converse direction, assume that there is and s-t flow of value a(1)+…+a(N). The construction given in the algorithm makes sure that the there is at most one member in family j sitting in the table j as the capacity of the flow goes from f i to c j is 1. So we only need to make sure that all families are seated. Note that {s}, V-{s} is an s-t cut with value a(1)+…+a(N), so the flow must saturate all edges crossing the cut. Therefore, all families must be sitting in some tables. This completes the correctness proof. Running time: The time complexity of construcing the graph is O(MN). The number of edges in the graph is MN+M+N, and v(f)= a(1)+…+a(N). Let T= a(1)+…+a(N), then the running time applying Ford-Fulkerson algorithm is O(MNT).

5) 20 pts Determine if there is a feasible circulation in the below network. If so, determine the circulation, if not show where the bottlenecks are. The numbers in parentheses are ( lowerbound, upperbound ) on flow. (3,1) (5,3) (7,4) (2,0) (1,0) (3,2) (2,0) (4,2) (2,1) d=5 d=-10 d=5

6) 5 pts List all minimum s-t cuts in the flow network pictured below. Capacity of every edge is equal to 10. C1={{S},{V,U,T}} C2={{S,U},{V,T}} C3={{S,U,V},{T}} S T U V 10 10 10 10 10

7) 5 pts Show an example of a graph in which poor choices of augmenting paths can lead to exactly C iterations of the Ford-Fulkerson algorithm before achieving max flow. (C is the sum of all edge capacities going out of the source and must be much greater than the number of edges in the network) Specifically, draw the network, mark up edge capacities, and list the sequence of augmenting paths. Any example satisfying that the condition in this question is fine when you list the sequence of augmenting paths.

CS570 Analysis of Algorithms Spring 2008 Exam II Name: _____________________ Student ID: _________________ Maximum Received Problem 1 20 Problem 2 15 Problem 3 15 Problem 4 15 Problem 5 20 Problem 6 15 Total 100 Note: The exam is closed book closed notes.

1) 20 pts Mark the following statements as TRUE , FALSE . No need to provide any justification. [ TRUE ] If all capacities in a network flow are rational numbers, then the maximum flow will be a rational number, if exist. [ TRUE ] The Ford-Fulkerson algorithm is based on the greedy approach. [ FALSE ] The main difference between divide and conquer and dynamic programming is that divide and conquer solves problems in a top-down manner whereas dynamic- programming does this bottom-up. [ FALSE ] The Ford-Fulkerson algorithm has a polynomial time complexity with respect to the input size. [ TRUE ] Given the Recurrence, T ( n ) = T ( n/ 2 ) + θ (1), the running time would be O (log( n )) [ FALSE ] If all edge capacities of a flow network are increased by k, then the maximum flow will be increased by at least k. [ TRUE ] A divide and conquer algorithm acting on an input size of n can have a lower bound less than Ω (n log n) . [ TRUE ] One can actually prove the correctness of the Master Theorem. [ TRUE ] In the Ford Fulkerson algorithm, choice of augmenting paths can affect the number of iterations. [ FALSE ] In the Ford Fulkerson algorithm, choice of augmenting paths can affect the min cut.

2) 15 pts Present a divide-and-conquer algorithm that determines the minimum difference between any two elements of a sorted array of real numbers. Key feature: The min difference can always been achieved between a pair of neighbors in the array, as the array is sorted. int Min_Diff(first, last) { if (last >= first) return inf; else return min(Min_Diff(first, (first + last)/2), Min_Diff((first + last)/2+1, last), abs(number[(first + last)/2+1] - number[(first + last)/2])); } The complexity is liner to the array size.

3) 15 pts You are given the following directed network with source O and sink T. O A B C D 8 2 8 3 2 1 3 6 7 T a) Find a maximum flow from O to T in the network. Augmenting paths and flow pushing amount: OACT 2 OBDT 3 OABDT 1 OACBDT 3 And the maximum flow here is with weight 9: O A B C D 7 0 7 3 2 1 3 5 6 T b) Find a minimum cut. What is its capacity?

O A B C D 7 6 3 1 2 3 8 2 8 T Capacity of this min cut is 9. 4) 15 pts Solve the following recurrences a) T (n) = 2T (n/2)+ n log n According to the master theorem, . 2 ( ) ( log ) T n n n   Or we can solve it like this: 2 2 ( log ) ( ) 2 ( ) log 2(2 ( ) log log 2) log 2 4 2 2 ( 1) 4 ( ) 2 log log 2 ... 2 ( ) log log 2 4 2 ... (1) ( log ) ( log ) k k k n n n n n T n T n n T n n n n n T n n n T kn n n nT n n n n                      2 k k

b) T (n) = 2T (n/2) + log n Similar to a), the result is ( ) ( ) T n n   . c) T(n) = 2T(n-1) - T(n-2) for n ≥ 2; T(0) = 3; T(1) = 3 It is very easy to find out that for the initial values T(0)=T(1), we always have T(i)=T(0), i >0. Thus T(n) = 3.

5) 20 pts You are given a flow network with integer capacity edges. It consists of a directed graph G = (V, E), a source s and a destination t, both belong to V. You are also given a parameter k. The goal is to delete k edges so as to reduce the maximum flow in G as much as possible. Give a efficient algorithm to find the edges to be deleted. Prove the correctness of your algorithm and show the running time. We here introduce a straightforward algorithm (assuming k<=|E|, otherwise just return failure): Delete_k_edges() { E' = E; for i=1 to k { curr_Max_Flow = inf; for j in E' if Max_Flow(V, E'-j) < curr_Max_Flow { curr_Max_Flow = Max_Flow(V, E'-j); index[i] = j; } E' = E' – index[i]; } } Then the final E' is a required edge set, and indices of all k deleted edges are stored in the array index[]. Running time is , depending on the max_flow algorithm used here, the time complexity varies: if Edmonds_Karp is used here the time would be ; if Dinic or other more advanced algorithm is used here the time complexity can be reduced. ( | | (max_ )) O k E T flow  3 ( | || | ) O k V E Proof hint: By induction. k = 1, the algorithm is correct. Assume k = i the algorithm is correct. Then we prove for k = i+1, it is also correct. Here, it is better to divide this i+1 into the first step and the folloing i steps, not vice versa.

6) 15 pts Six men and six women are at a dance. The goal of the matchmaker is to match each woman with a man in a way that maximizes the number of people who are matched with compatible mates. The table below describes the compatibility of the dancers. Ann Cindy Erin Liz Mary Nancy Bob C C - - - - Dave - - C - - - John - C C C - - Kevin - - C - C - Ron - - - C - C Sam - - - - C - Note : C indicates compatibility. a) Determine the maximum number of compatible pairs by reducing the problem to a max flow problem. Bob Dave John Kevin Ron Sam Ann Cindy Erin Liz Mary Nancy T S All edges are with capacity 1. Run some maximum flow algorithm like Edmonds-Karp, it would guarantee to return a 0-1 solution within polynomial time, with represents the required match. b) Find a minimum cut for the network of part (a). A={S, Dave, Kevin, Sam, Erin, Mary} and A' = V-A constitute a minimum cut, with capacity 5. c) Give the list of pairs in the maximum pairs set. Maximum 5 pairs. One solution: Bob-Ann, Dave-Erin, John-Cindy, Ron-Nancy, Sam-Mary.

CS570 Analysis of Algorithms Spring 2009 Exam II Name: _____________________ Student ID: _________________ ____2:00-5:00 Friday Section ____5:00-8:00 Friday Section Maximum Received Problem 1 20 Problem 2 20 Problem 3 20 Problem 4 20 Problem 5 20 Total 100 2 hr exam Close book and notes 1) 20 pts Mark the following statements as TRUE or FALSE . No need to provide any justification.

[ TRUE/FALSE ] TRUE The problem of deciding whether a given flow f of a given flow network G is maximum flow can be solved in linear time. [ TRUE/FALSE ] TRUE If you are given a maximum s - t flow in a graph then you can find a minimum s - t cut in time O(m). [ TRUE/FALSE ] TRUE An edge that goes straight from s to t is always saturated when maximum s - t flow is reached. [ TRUE/FALSE ] FALSE In any maximum flow there are no cycles that carry positive flow. (A cycle <e 1 , …, e k > carries positive flow iff f(e 1 ) > 0, …, f(e k ) > 0.) [ TRUE/FALSE ] TRUE There always exists a maximum flow without cycles carrying positive flow. [ TRUE/FALSE ] FALSE In a directed graph with at most one edge between each pair of vertices, if we replace each directed edge by an undirected edge, the maximum flow value remains unchanged. [ TRUE/FALSE ] FALSE The Ford-Fulkerson algorithm finds a maximum flow of a unit-capacity flow network (all edges have unit capacity) with n vertices and m edges in O(mn) time. [ TRUE/FALSE ] FALSE Any Dynamic Programming algorithm with n unique subproblems will run in O(n) time. [ TRUE/FALSE ] FALSE The running time of a pseudo polynomial time algorithm depends polynomially on the size of of the input [ TRUE/FALSE ] FALSE In dynamic programming you must calculate the optimal value of a subproblem twice, once during the bottom up pass and once during the top down pass.

2) 20 pts a) Give a maximum s-t flow for the following graph, by writing the flow f e above each edge e. The printed numbers are the capacities. You may write on this exam sheet. Solution: (b) Prove that your given flow is indeed a max-flow. Solution:

The cut ({s: 1, 2, 3, 4}, {5, 6, 7}) has capacity 6. The flow given above has value 6. No flow can have value exceeding the capacity of any cut, so this proves that the flow is a max-flow (and also that the cut is a min-cut). 3) 20 pts On a table lie n coins in a row, where the i th coin from the left has value x i >= 0. You get to pick up any set of coins, so long as you never pick up two adjacent coins. Give

a polynomial-time algorithm that picks a (legal) set of coins of maximum total value. Prove that your algorithm is correct, and runs in polynomial time. We use Dynamic Programming to solve this problem. Let OPT(i) denote the maximum value that can be picked up among coins 1, . . . , i . Base case: OPT(0) = 0, and OPT(1) = x1. Considering coin i , there are two options for the optimal solution: either it includes coin i , or it does not. If coin i is not included, then the optimal solution for coins 1, . . . , i is the same as the one for coins 1, . . . , i -1. If coin i is included in the optimal solution, then coin i -1 cannot be included, but among coins 1, . . . , i − 2, the optimum subset is included, as a non-optimum one could be replaced with a better one in the solution for i. Hence, the recursion is OPT(0) = 0 OPT(1) = x 1 OPT(i) = max(OPT(i-1), x i + OPT(i − 2)) for i > 1. Hence, we get the algorithm Coin Selection below: The correctness of the computation follows because it just implements the recurrence which we proved correct above. The output part just traces back the array for the solution constructed previously, and outputs the coins which have to be picked to make the recurrence work out. The running time is O(n), as for each coin, we only compare two values. 4) 20 pts We assume that there are n tasks, with time requirements r 1 , r 2 , . . . , r n hours. On the project team, there are k people with time availabilities a 1 , a 2 , . . . , a k . For each task i

and person j , you are told if person j has the skills to do task i . You are to decide if the tasks can be split up among the people so that all tasks get done, people only execute tasks they are qualified for, and no one exceeds his time availability. Remember that you can split up one task between multiple qualified people. Now, in addition, there are group constraints. For instance, even if each of you and your two roommates can in principle spend 4 hours on the project, you may have decided that between the three of you, you only want to spend 10 hours. Formally, we assume that there are m sets S j ⊆ {1, . . . , k} of people, with set constraints t j . Then, any valid solution must ensure, in addition to the previous constraints, that the combined work of all people in S j does not exceed t j , for all j . Give an algorithm with running time polynomial in n, m, k for this problem, under the assumption that all the S j are disjoint, and sketch a proof that your algorithm is correct. Solution: We will have one node u h for each task h, one node v i for each person i, and one node w j for each constraint set S j . In addition, there is a source s and a sink t. As before, the source connects to each node u h with capacity r h . Each u h connects to each node v i such that person i is able to do task h, with infinite capacity. If a person i is in no constraint set, node v i connects to the sink t with capacity a i . Otherwise, it connects to the node w j for the constraint set S j with i ∈ S j , with capacity a i . (Notice that because the constraint sets are disjoint, each person only connects to one set.) Finally, each node wj connects to the sink t with capacity t j . We claim that this network has an s-t flow of value at least ∑ h r h if and only if the tasks can be divided between people. For the forward direction, assume that there is such a flow. For each person i, assign him to do as many units of work on task h as the flow from u h to v i . First, because the flow saturates all the edges out of the source (the total capacity out of the source is only ∑ h r h ), and by flow conservation, each job is fully assigned to people. Because the capacity on the (unique) edge out of v i is a i , no person does more than a i units of work. And because the only way to send on the flow into v i is to the node w j for nodes i ∈ S j , by the capacity constraint on the edge (w j , t), the total work done by people in S j is at most t j . Conversely, if we have an assignment that has person i doing x ih units of work on task h, meeting all constraints, then we send x ih units of flow along the path s-u h -v i -t (if person i is in no constraint sets), or along s-u h -v i -w j -t, if person i is in constraint set S j . This clearly satisfies conservation and non-negativity. The flow along each edge (s, u h ) is exactly r h , because that is the total amount of work assigned on job h. The flow along the edge (v i , t) or (v i , s j ) is at most a i , because that is the maximum amount of work assigned to person i. And the total flow along (w j , t) is at most t j , because each constraint was satisfied by the assignment. So we have exhibited an s-t flow of total value at least ∑ h r h . 5) 20 pts There are n trading posts along a river numbered n, n – 1… 3, 2, 1 . At any of the posts you can rent a canoe to be returned at any other post downstream. (It is

impossible to paddle against the river since the water is moving too quickly). For each possible departure point i and each possible arrival point j(< i) , the cost of a rental from i to j is known. It is C[i, j] . However, it can happen that the cost of renting from i to j is higher than the total costs of a series of shorter rentals. In this case you can return the first canoe at some post k between i and j and continue your journey in a second (and, maybe, third, fourth . . . ) canoe. There is no extra charge for changing canoes in this way. Give a dynamic programming algorithm to determine the minimum cost of a trip by canoe from each possible departure point i to each possible arrival point j . Analyze the running time of your algorithm in terms of n . For your dynamic programming solution, focus on computing the minimum cost of a trip from trading post n to trading post 1 , using up to each intermediate trading post. Solution Let OPT(i,j) = The optimal cost of reaching from departure point “i” to departure point “j”. Now, lets look at OPT(i,j). assume that we are at post “i”. If we are not making any intermediate stops, we will directly be at “j”. We can potentially make the first stop, starting at “i” to any post between “i” and “j” (“j” included, “i” not included) This gets us to the following recurrence OPT(i,j) = min(over j<= k < i)(C[i,k] + OPT(k,j) ) The base case is OPT(i,i) = C[i,i] = 0 for all “i“ from 1 to n The iterative program will look as follows Let OPT[i,j] be the array where you will store the optimal costs. Initialize the 2D array with the base cases for (i=1;i<=n;i++) { for (j=1;j<=i-i;j++) { calculate OPT(i,j) with the recurrence } } Now, to output the cost from the last post to the first post, will be given by OPT[n,1] As for the running time, we are trying to fill up all OPT[i,j] for i<j. Thus, there are O(n 2 ) entries to fill (which corresponds to the outer loops for “i” and “j”) In each loop, we could potentially be doing at most k comparisons for the min operation . This is O(n) work. Therefore, the total running time is O(n 3 )

CS570 Analysis of Algorithms Spring 2010 Exam II Name: _____________________ Student ID: _________________ DEN Student YES / NO Maximum Received Problem 1 20 Problem 2 20 Problem 3 20 Problem 4 20 Problem 5 20 Total 100 2 hr exam Close book and notes If a description to an algorithm is required please limit your description to within 200 words, anything beyond 200 words will not be considered.

1) 20 pts Mark the following statements as TRUE or FALSE . No need to provide any justification. In the final residual graph constructed during the execution of the Ford–Fulkerson Algorithm, there’s no path from source to sink. TRUE In a flow network whose edges all have capacity 1, the maximum flow value equals the maximum degree of a vertex in the flow network. FALSE. Memoization is the basis for a top-down alternative to the usual bottom-up approach to dynamic programming solutions. TRUE The time complexity of a dynamic programming solution is always lower than that of an exhaustive search for the same problem. FALSE If we multiply all edge capacities in a graph by 5, then the new maximum flow value is the original one multiplied by 5. TRUE. For any graph 𝐺𝐺 with edge capacities and vertices 𝑠𝑠 and 𝑡𝑡 , there always exists an edge such that increasing the capacity on that edge will increase the maximum flow from 𝑠𝑠 to 𝑡𝑡 . (Assume that there is at least one path in the graph from 𝒔𝒔 to 𝒕𝒕 . ) FALSE. There might be more than one min-cut, by increasing the edge capacity of one min- cut doesn’t have to impact the other one. Let 𝐺𝐺 be a weighted directed graph with exactly one source 𝑠𝑠 and exactly one sink 𝑡𝑡 . Let ( 𝐴𝐴 , 𝐵𝐵 ) be a maximum cut in 𝐺𝐺 , that is, 𝐴𝐴 and 𝐵𝐵 are disjoint sets whose union is 𝑉𝑉 , 𝑠𝑠 ∈ 𝐴𝐴 , 𝑡𝑡 ∈ 𝐵𝐵 , and the sum of the weights of all edges from 𝐴𝐴 to 𝐵𝐵 is the maximum for any two such sets. Now let 𝐻𝐻 be the weighted directed graph obtained by adding 1 to the weight of each edge in 𝐺𝐺 . Then ( 𝐴𝐴 , 𝐵𝐵 ) must still be a maximum cut in 𝐻𝐻 . FALSE There could exist other edge which has many more cross-edges, which was not max- cut previously, to become the new max-cut.

A recursive implementation of a dynamic programming solution is often less efficient in practice than its equivalent iterative implementation. We give points for both TRUE and FALSE answers due to the ambiguity of "often". Ford-Fulkerson algorithm will always terminate as long as the flow network G has edges with strictly positive capacities. FALSE If some edges are irrational numbers, Ford-Fulkerson may never terminate. Any problem that can be solved using dynamic programming has a polynomial time worst case time complexity with respect to its input size. FALSE

2) 20 pts Judge the following statement is true or false. If true, prove it. If false, give a counter- example. Given a directed graph, if deleting edge e reduces the original maximum flow more than deleting any other edge does, then edge e must be part of a minimum s-t cut in the original graph. Solution: False. Counter-example: Apparently deleting the edge with capacity 10 will reduce the flow by the most, while it is not part of minimum s-t cut. Comment: some of you misunderstood the problem in different ways. Some counter-examples have multiple min s-t cuts and the edge "e" is actually in one of them. And some others failed to satisfy the precondition "more than… any other", and have some equal alternatives, which are also incorrect. S T 1 1 2 2 10 3 3 4 4

3) 20 pts a- Show all steps involved in finding maximum flow from S to T in above flow network using the Ford-Fulkerson algorithm. b- What is the value of the maximum flow? c- Identify the minimum cut. a. 1. Augment path: [S, B, C, T], bottleneck is 1, residual graph: A S D B C T E 3 1 5 3 2 4 2 3 S D B C T E 3 1 4 3 4 2 3 A 1 1 1

2. Augment path: [S, A, C, T], bottleneck is 1, residual graph: 3. Augment path: [S, A, C, B, D, E, T], bottleneck is 1, residual graph: 4. No forward path from S to T, terminate. b. The maximum flow is 3. S D B C T E 2 1 4 2 4 2 3 A 1 1 1 2 S D B C T E 1 1 1 1 1 1 A 2 2 2 2 1 3 5

c. The Min-Cut is: [S, A, C] and [B, D, E, T]. A S D B C T E 3 1 5 3 2 4 2 3

4) 20 pts The words `computer' and `commuter' are very similar, and a change of just one letter, p  m will change the first word into the second. The word `sport' can be changed into `sort' by the deletion of the `p', or equivalently, `sort' can be changed into `sport' by the insertion of `p'. The edit distance of two strings, s1 and s2, is defined as the minimum number of point mutations required to change s1 into s2, where a point mutation is one of: 1. change a letter, 2. insert a letter or 3. delete a letter a) Design an algorithm using dynamic programming techniques to calculate the edit distance between two strings of size at most n . The algorithm has to take less than or equal to 𝑂𝑂 ( 𝑛𝑛 2 ) for both time and space complexity. b) Print the edits. The following recurrence relations define the edit distance, 𝑑𝑑 ( 𝑠𝑠 1, 𝑠𝑠 2) , of two strings s1 and s2: 1. 𝑑𝑑 (‘’, ‘’) = 0 (for empty strings) 2. 𝑑𝑑 ( 𝑠𝑠 , ‘’) = 𝑑𝑑 (‘’, 𝑠𝑠 ) = | 𝑠𝑠 | (length of s) 3. 𝑑𝑑 ( 𝑠𝑠 1 + 𝑐𝑐ℎ 1, 𝑠𝑠 2 + 𝑐𝑐ℎ 2) = 𝒎𝒎𝒎𝒎𝒎𝒎 ( 𝑑𝑑 ( 𝑠𝑠 1, 𝑠𝑠 2) + � 0, 𝑖𝑖𝑖𝑖 𝑐𝑐ℎ 1 = 𝑐𝑐ℎ 2 1, 𝑒𝑒𝑒𝑒𝑠𝑠𝑒𝑒 , 𝑑𝑑 ( 𝑠𝑠 1 + 𝑐𝑐ℎ 1, 𝑠𝑠 2) + 1, 𝑑𝑑 ( 𝑠𝑠 1, 𝑠𝑠 2 + 𝑐𝑐ℎ 2) + 1 ) The first two rules above are obviously true, so it is only necessary consider the last one. Here, neither string is the empty string, so each has a last character, 𝑐𝑐ℎ 1 and 𝑐𝑐ℎ 2 respectively. Somehow, 𝑐𝑐ℎ 1 and 𝑐𝑐ℎ 2 have to be explained in an edit of 𝑠𝑠 1 + 𝑐𝑐ℎ 1 into 𝑠𝑠 2 + 𝑐𝑐ℎ 2 . • If 𝑐𝑐ℎ 1 equals 𝑐𝑐ℎ 2 , they can be matched for no penalty, which is 0, and the overall edit distance is 𝑑𝑑 ( 𝑠𝑠 1, 𝑠𝑠 2) . • If 𝑐𝑐ℎ 1 differs from 𝑐𝑐ℎ 2 , then 𝑐𝑐ℎ 1 could be changed into 𝑐𝑐ℎ 2 , costing 1, giving an overall cost 𝑑𝑑 ( 𝑠𝑠 1, 𝑠𝑠 2) + 1 . • Another possibility is to delete 𝑐𝑐ℎ 1 and edit 𝑠𝑠 1 into 𝑠𝑠 2 + 𝑐𝑐ℎ 2 , 𝑑𝑑 ( 𝑠𝑠 1, 𝑠𝑠 2 + 𝑐𝑐ℎ 2) + 1 . • The last possibility is to edit 𝑠𝑠 1 + 𝑐𝑐ℎ 1 into 𝑠𝑠 2 and then insert 𝑐𝑐ℎ 2 , 𝑑𝑑 ( 𝑠𝑠 1 + 𝑐𝑐ℎ 1, 𝑠𝑠 2) + 1 . There are no other alternatives. We take the least expensive, min , of these alternatives. Examination of the relations reveals that 𝑑𝑑 ( 𝑠𝑠 1, 𝑠𝑠 2) depends only on 𝑑𝑑 ( 𝑠𝑠 1 ′ , 𝑠𝑠 2 ′ ) where 𝑠𝑠 1 ′ is shorter than 𝑠𝑠 1 , or 𝑠𝑠 2 ′ is shorter than 𝑠𝑠 2 , or both. This allows the dynamic programming technique to be used.

A two-dimensional matrix, m[0..|s1|,0..|s2|] is used to hold the edit distance values: m[i,j] = d(s1[1..i], s2[1..j]) m[0,0] = 0 m[i,0] = i, i=1..|s1| m[0,j] = j, j=1..|s2| m[i,j] = min(m[i-1,j-1] + if s1[i]=s2[j] then 0 else 1, m[i-1, j] + 1, m[i, j-1] + 1 ), i=1..|s1|, j=1..|s2| 𝑚𝑚 [, ] can be computed row by row . Row 𝑚𝑚 [ 𝑖𝑖 , ] depends only on row 𝑚𝑚 [ 𝑖𝑖 − 1, ] . The time complexity of this algorithm is 𝑂𝑂 (| 𝑠𝑠 1| ∗ | 𝑠𝑠 2|) . If 𝑠𝑠 1 and 𝑠𝑠 2 have a similar length 𝑛𝑛 , this complexity is 𝑂𝑂 ( 𝑛𝑛 2 ) . b) Once the algorithm terminates, we have generated the edit distance matrix 𝑚𝑚 , we can do a trace-back for all the edits, e.g. Figure 1: Figure 1 Edit distance matrix (from Wikipedia) Here we are using a head recursion so that it prints the path from beginning to the end. Print_Edits( 𝑛𝑛 1 , 𝑛𝑛 2 ) if 𝑛𝑛 = 0 then Output nothing else Find ( 𝑖𝑖 , 𝑗𝑗 ) ∈ {( 𝑛𝑛 1 − 1, 𝑛𝑛 2), ( 𝑛𝑛 1, 𝑛𝑛 2 − 1), ( 𝑛𝑛 1 − 1, 𝑛𝑛 2 − 1)} that has the minimum value from 𝑚𝑚 [ 𝑖𝑖 , 𝑗𝑗 ] . Print_Edits ( 𝑖𝑖 , 𝑗𝑗 ) if 𝑚𝑚 [ 𝑖𝑖 , 𝑗𝑗 ] = 𝑚𝑚 ( 𝑛𝑛 1, 𝑛𝑛 2) then

Do nothing else if ( 𝑖𝑖 , 𝑗𝑗 ) = ( 𝑛𝑛 1 − 1, 𝑛𝑛 2 − 1) then Print “ 𝑐𝑐ℎ𝑎𝑎𝑛𝑛𝑎𝑎𝑒𝑒 𝑠𝑠 1’ 𝑠𝑠 𝑛𝑛 1 𝑡𝑡ℎ 𝑒𝑒𝑒𝑒𝑡𝑡𝑡𝑡𝑒𝑒𝑙𝑙 𝑖𝑖𝑛𝑛𝑡𝑡𝑖𝑖 𝑠𝑠 2’ 𝑠𝑠 𝑛𝑛 2 𝑡𝑡ℎ 𝑒𝑒𝑒𝑒𝑡𝑡𝑡𝑡𝑒𝑒𝑙𝑙 ” else if ( 𝑖𝑖 , 𝑗𝑗 ) = ( 𝑛𝑛 1, 𝑛𝑛 2 − 1) then Print “ 𝑖𝑖𝑛𝑛𝑠𝑠𝑒𝑒𝑙𝑙𝑡𝑡 𝑠𝑠 2’ 𝑠𝑠 𝑛𝑛 2 𝑡𝑡ℎ 𝑒𝑒𝑒𝑒𝑡𝑡𝑡𝑡𝑒𝑒𝑙𝑙 𝑎𝑎𝑖𝑖𝑡𝑡𝑒𝑒𝑙𝑙 𝑠𝑠 1’ 𝑠𝑠 𝑛𝑛 1 𝑡𝑡ℎ 𝑝𝑝𝑖𝑖𝑠𝑠𝑖𝑖𝑡𝑡𝑖𝑖𝑖𝑖𝑛𝑛 ” else Print “ 𝑑𝑑𝑒𝑒𝑒𝑒𝑒𝑒𝑡𝑡𝑒𝑒 𝑠𝑠 1’ 𝑠𝑠 𝑛𝑛 1 𝑡𝑡ℎ 𝑒𝑒𝑒𝑒𝑡𝑡𝑡𝑡𝑒𝑒𝑙𝑙 ” The trace-back process has the complexity of 𝑂𝑂 ( 𝑛𝑛 ) .

5) 20 pts Given a 2-dimensional array of size m n × with only “0” or “1” in each position, starting from position [1, 1] (top left corner), every time you can only move either one cell to the right or one cell down (of course you must remain in the array). Give an O(mn) algorithm to calculate the number of different paths without reaching “0” in any step, starting from [1, 1] and ending in [ m, n ]. Solution: We can solve this problem using dynamic programming. We denote a[i][j] as the array, num[i][j] as the number of different paths without reaching "0" in any step starting from [1, 1] and ending in [i, j]. Then the desired solution is num[m][n]. We have 0 i=0 or j=0 or a[i][j]=0 [ ][ ] [1][1] i=1 and j=1 [ 1][ ] [ ][ 1] num i j a num i j num i j other   =   − + −  This is simply because we can reach cell [i, j] by coming from either [i-1, j] or [i, j-1]. When a[i][j]=1, num[i][j] is just the sum of the two num's from the two different directions. By calculating num row by row, we can get num[m][n] at last. This is an O(mn) solution since we use O(1) time to calculate each num[i][j] and the size of array num is O(mn). Comment: this is different from the "number of disjoint paths" problem which can be solved by being reduced to max flow problem. And some used max function instead of plus. Some other used recursion, but without memorization which would course the complexity become exponential. And some other tried to find paths and count, which is also an approach with exponential complexity.

CS570 Analysis of Algorithms Summer 2007 Exam 2 Name: _____________________ Student ID: _________________ Maximum Received Problem 1 10 Problem 2 20 Problem 3 20 Problem 4 10 Problem 5 20 Problem 6 20 Note: The exam is closed book closed notes.

1) 10 pts Mark the following statements as TRUE or FALSE . No need to provide any justification. True [ TRUE/FALSE ] Binary search could be called a divide and conquer technique False [ TRUE/FALSE ] If you have non integer edge capacities, then you cannot have an integer max flow Ture [ TRUE/FALSE ] The Ford Fulkerson algorithm with real valued capacities can run forever Ture [ TRUE/FALSE ] If we have a 0-1 valued s-t flow in a graph of value f, then we have f edge disjoint s- t paths in the graph Ture [ TRUE/FALSE ] Merge sort works because at each level of the algorithm, the merge step assumes that the two lists are sorted

2) 20pts Prove or disprove the following for a given graph G(V,E) with integer edge capacities Ci a. If the capacities on each edge are unique then there is a unique min cut Disprove : b. If we multiply each edge with the same multiple “f”, the max flow also gets multiplied by the same factor Prove: For each cut (A, B) of the graph G, the capacity c(A, B) will be multiplied by “f” if each edge’s capacity is multiplied by “f”, thus the minimal cut will be multiplied by “f” , thus the max flow also gets multiplied by “f”. c. If we add the same amount, say “a” to every edge in the graph, then the min cut stays the same (the edges in the min cut stay the same i.e.) 1 1 1 1 3 3 3 3 3 5 Before add 2 to every edge After add 2 to every edge 1 2 3 4 6

d. If the edge costs are all even, then the max flow(min cut) is also even The capacity of any cut (A, B) is sum of the capacities of all edges out of A, thus the capacity of any cut, including the minimal one, is also even. e. If the edge costs are all odd, then the max flow (min cut) is also odd 1 1 1 1 Max flow: 2

3) 20 pts Suppose you are given k sorted arrays, each with n elements, and you want to combine them into a single sorted array of kn elements. (a) Here's one strategy: merge the first two arrays, then merge in the third, then merge in the fourth, and so on. What is the time complexity of this strategy, in terms of k and n? The merge the first two array takes O(n), … the merge of the last array takes O(kn), totally there are k merge sorts. Thus, it takes O(k 2 n) times. (b) Present a more efficient solution to this problem. Let the final array to be A, initially A is empty. Build up a binary heap with the first element from the k given arrays, thus this binary tree consists of k element. Extract the minimal element from the binary tree and add it to A, delete it from its original array, and insert the next element from that array into the binary heap. Each heap operation is O(logk), and take O(kn) operations, thus, the running time is O(kn*logk)

4) 10 pts Derive a recurrence equation that describes the following code. Then, solve the recurrence equation. COMPOSE (n) 1. for i ← 1 to n 2. do for j ← 1 to sqrt( n) 3. do print (i, j, n) 4. if n > 0 5. then for i ← 1 to 5 6. COMPOSE ( ⎣ n/ 2 ⎦ ) T(n) = 5 T(n/2) + O(n 3/2 ) By the Master theorem, T(n) = n lg5

5) 20 pts Let G=(V,E) be a directed graph, with source s ∈ V, sink t ∈ V, and non-negative edge capacities {C e }. Give a polynomial time algorithm to decide whether G has a unique minimum s-t cut. (i.e. an s-t cut of capacity strictly less than that of all other s- t cuts.) Find a max flow f for this graph G, and then construct the residual graph G’ based on this max flow f. Start from the source s, perform breadth-first or depth-first search to find the set A that s can reach, define B = V – A, the cut (A, B) is a minimum s-t cut. Then, for each node v in B that is connected to A in the original graph G, try the following codes: add v into set A, and then perform breadth-first or depth-first search find a new set A’ that s can reach, if the sink t is included in A’, then try next node v’, otherwise, report a new minimum s-t cut. If all possible nodes v in B have been tried but no more minimum s-t cut can be found, then report the (A, B) is the unique minimum s-t cut.

20 pts Consider you have three courses to study, C1, C2 and C3. For the three courses you need to study a minimum of T1, T2, and T3 hours respectively. You have three days to study for these courses, D1, D2 and D3. On each day you have a maximum of H1, H2, and H3 hours to study respectively. You have only 12 hours total to give to all of these courses, which you could distribute within the three days. On each one of the days, you could potentially study all three courses. Give an algorithm to find the distribution of hours to the three courses on the three days If T1+T2+T3 > 12 or T1+T2+T3 > H1 + H2 + H3, then report no feasible distribution can be found. Else, start C1 with T1 hours, and then C2 with T2 hours, and finally C3 with T3 hours.

CS570 Analysis of Algorithms Summer 2008 Exam II Name: _____________________ Student ID: _________________ ____4:00 - 5:40 Section ____6:00 – 7:40 Section Maximum Received Problem 1 15 Problem 2 15 Problem 3 15 Problem 4 20 Problem 5 20 Problem 6 15 Total 100 2 hr exam Close book and notes

1) 15 pts a) Suppose that we have a divide-and-conquer algorithm for a solving computational problem that on an input of size n, divides the problem into two independent subproblems of input size 2n/5 each, solves the two subproblems recursively, and combines the solutions to the subproblems. Suppose that the time for dividing and combining is O(n). What's the running time of this algorithm? Answer the question by giving a recurrence relation for the running time T(n) of the algorithm on inputs of size n, and giving a solution to the recurrence relation. Solution: The recurrence relation of T(n): T(n) = 2 T(2n/5) + O(n) To solve the recurrence relation, using the substitution method: guess that T(n) ≤ cn ⇒ T(n) ≤ 2 * 2c/5n + an ≤ cn as long as c ≥ 5a Thus, T(n) ≤ cn. ⇒ T(n) = O(n) b) Characterize each of the following recurrence equations using the master method. You may assume that there exist constan ts c > 0 and d ≥ 1 such that for all n < d, T(n) = c. a. T(n) = 2T(n/2) + log n b. T(n) = 16T(n/2) + (n log n) 4 c. T(n) = 9T(n/3) + n 3 log n Solution: a. Since there is ε > 0 such that log n = O( n log 2 2 − ε ) = O( n 1 − ε ), ⇒ case 1 of master method, T(n) = Θ n log 2 2 = Θ (n) b. (n log n) 4 = n 4 log 4 n = Θ n log 2 16 log 4 n , ⇒ case 2 of master method, T(n) = Θ n log 2 16 log (4+1) n = Θ n 4 log 5 n c. n 3 log n = Ω (n log 3 9 + 1 ) and 9 × n 3 3 log n 3 = n 3 3 log n 3 ≤ 1 3 n 3 log n, ⇒ case 3 of master method, T(n) = Θ n 3 log n

2) 15 pts You are given a sorted array A[1..n] of n distinct integers. Provide an algorithm that finds an index i such that A[i] = i, if such exists. Analyze the running time of your algorithm Solution: (This one is exactly the same as 5) of sample exam 1 of exam I) Function(A,n) { i=floor(n/2) if A[i]==i return TRUE if (n==1)&&(A[i]!=i) return FALSE if A[i]<i return Function(A[i+1:n], n-i) if A[i>i] return Function(A[1:i], i) } Proof: The algorithm is based on Divide and Conquer. Every time we break the array into two halves. If the middle element i satisfy A[i]<j, we can see that for all j<i, A[j]<j. This is because A is a sorted array of DISTINCT integers. To see this we note that A[j+1]-A[j]>=1 for all j. Thus in the next round of search we only need to focus on A[i+1:n] Likewise, if A[i]>i we only need to search A[1:i] in the next round. For complexity T(n)=T(n/2)+O(1) Thus T(n)=O(log n)

3) 15 pts Consider a sequence of n distinct integers. Design and analyze a dynamic programming algorithm to find the length of a longest increasing subsequence. For example, consider the sequence: 45 23 9 3 99 108 76 12 77 16 18 4 A longest increasing subsequence is 3 12 16 18, having length 4. Solution: Let X be the sequence of n distinct integers. Denote by X( i ) the i th integer in X, and by D i the length of the longest increasing subsequence of X that ends with X( i ). The recurrence that relates D i to D i ‘ s with j < i is as follows: D ? = max ? < ? , 𝑋 ? < 𝑋 ( ? ) D ? + 1 The algorithm is as follows: for i =1 … n Compute D i end for return the largest number among D 1 to D n . When computing each D i , the recurrence finds the largest D j such that ? < ? , 𝑋 ? < 𝑋 ( ? ) . Thus, each D i is maximized. The length of the longest increasing subsequence is obviously among D 1 to D n . Since computing each D i costs O(n) and the loop runs for n times, the complexity of the algorithm is O( n 2 ).

4) 20 pts In the flow network illustrated below, each directed edge is labeled with its capacity. We are using the Ford-Fulkerson algorithm to find the maximum flow. The first augmenting path is S-A-C-D-T, and the second augmenting path is S-A-B-C-D-T. a) 10 pts Draw the residual network after we have updated the flow using these two augmenting paths(in the order given) Solution: Residual network after S-A-C-D-T: Residual network after S-A-B-C-D-T: 1 1 1 2 1 2 2 2 1 S A C B D T 4 1 4 2 1 1 2 1 3 3 1 1 S A C B D T 4 2 4 1 S A C B D T 2 4 1 3 3 4 3 1 3

b) 6pts List all of the augmenting paths that could be chosen for the third augmentation step. Solution: S-C-B-T S-C-D-T S-C-A-B-T S-C-D-B-T c) 4pts What is the numerical value of the maximum flow? Draw a dotted line through the original graph to represent a minimum cut. Solution: The numerical value of the maximum flow is 5. A minimum cut is shown in the following figure: 1 S A C B D T 2 4 1 3 3 4 3 3

5) 20 pts Decide whether you think the following statements are true or false. If true, give a short explanation. If false, give a counterexample. Let G be an arbitrary flow network, with a source s, a sink t, and a positive integer capacity c e on every edge e. a) If f is a maximum s-t flow in G, then for all edges e out of s, we have f(e) = c e . Solution: False. Clearly, the maximum s-t flow in the above graph is 2. The edge (s, u) does not have f(e) = c e b) Let (A,B) be a minimum s-t cut with respect to the capacities { c e : e Є E}. Now suppose we add 1 to every capacity. Then (A,B) is still a minimum s-t cut with respect to these new capacities {1 + c e : e Є E}. Solution: False. Clearly, one of the minimum cuts is A={s,u} and B={v,t}. After adding 1 to every capacity, the maximum s-t flow becomes 10 and the cut between A and B is 11. s u v t 5 3 2 3 5 s u v t 3 1 1 1 1

6) 15 pts Suppose that in county X, there are only 3 kinds of coins: the first kind are 1-unit coins, the second kind are 4-unit coins, and the third kind are 6-unit coins. You want to determine how to return an amount of K units, where K≥0 is an integer, using as few coins as possible. For example, if K=7, you can use 2 coins (a 1-unit coin and a 6-unit coin), which is better than using three 1-unit coins and a 4-unit coins since in this case, the total number of coins used is 4. For 0 ≤ k ≤ K and 1 ≤ i ≤ 3, let c(i,k) be the smallest number of coins required to return an amount of k using only the first i kinds of coins. So for example, c(2,5) would be the smallest number of coins required to return 5 units if we can only use 1- unit coins and 4-unit coins. In what follows, you can assume that the denomination of the coins is stored in an array d, i.e., d[1]=1,d[2]=4,d[3]=6. Give a dynamic programming algorithm that returns c(i,k) for 0 ≤ k ≤ K and 1 ≤ i ≤ 3 Solution: Let the coin denominations be d 1 , d 2 , . . . , d i . Because of the optimal substructure, if we knew that an optimal solution for the problem of making change for k cents used a coin of denomination d j , we would have c( i , k ) = 1+ c( ? , ? − 𝑑 j ) . As base cases, we have that c( i , k ) = 0 for all ? ≤ 0 . To develop a recursive formulation, we have to check all denominations, giving c( i , k ) = 0, if ? ≤ 0 1 + min 1 ≤? ≤? {c( ? , ? − 𝑑 j )} ⁡ , if ? > 1 The algorithm is as follows: for i = 1 … 3 for k =0 … K Compute c( i, k) end for end for When i = j , to compute each c( j , k ) costs O( j ). Thus, the complexity is O(K+2K+3K) = O(6K)

Q1 : [ TRUE/FALSE ] FALSE Suppose ?(𝑛) = ? ( 𝑛 2 ) +56, then ?(𝑛) = Θ (𝑛) [ TRUE/FALSE ] TRUE Maximum value of an s-t flow could be less than the capacity of a given s-t cut in a flow network. [ TRUE/FALSE ] FALSE For edge any edge e that is part of the minimum cut in G, if we increase the capacity of that edge by any integer k>1, then that edge will no longer be part of the minimum cut. [ TRUE/FALSE ] FALSE Any problem that can be solved using dynamic programming has a polynomial worst case time complexity with respect to its input size. [ TRUE/FALSE ] FALSE In a dynamic programming solution, the space requirement is always at least as big as the number of unique sub problems [ TRUE/FALSE ] FALSE In the divide and conquer algorithm to compute the closest pair among a given set of points on the plane, if the sorted order of the points on both X and Y axis are given as an added input, then the running time of the algorithm improves to O(n). [ TRUE/FALSE ] TRUE If f is a max s-t flow of a flow network G with source s and sink t, then the value of the min s-t cut in the residual graph G f is 0. [ TRUE/FALSE ] TRUE Bellman-Ford algorithm can solve the shortest path problem in graphs with negative cost edges in polynomial time. [ TRUE/FALSE ] TRUE Given a directed graph G=(V,E) and the edge costs, if every edge has a cost of either 1 or -1 then we can determine if it has a negative cost cycle in O(|V|^3) time.. [ TRUE/FALSE ] TRUE The space efficient version of the solution to the sequence alignment problem (discussed in class), was a divide and conquer based solution where the divide step was performed using dynamic programming.