Solutions for Practice Problems for Exam (1)

CS 3510: Design & Analysis of Algorithms 10/17/2023 Practice Problems for Exam 3: Dynamic Programming Sahil Singla • This is the CS 3510 practice exam for exam 3. • Topics include: Bipartite Graph Matching, Max-Flow, Dynamic Programming on graphs, strings, and sequences.

Matchings 1. Explain briefly why or why not the the following claims are true (no need for a formal proof). For the questions G = ( V, E ) is a Bipartite Graph, and let M be a valid matching on that graph. The graph M can be partitioned into L and R to be Bipartite. i. If | M | = | E | , then M is a perfect matching of G . ⃝ True √ False ii. If P = ( u, . . . , v ) is an augmenting path in G with matching M and u ∈ L , then v ∈ L . ⃝ True √ False iii. If G is a fully connected Bipartite Graph (complete), this implies M covers every edge. ⃝ True √ False iv. M is a perfect matching of G if and only if | L | = | R | . ⃝ True √ False v. Assume P = ( u, x, y, . . . , v ) is an augmenting path in G with matching M , since we start at an unmatched vertex u , x is a matched vertex and y is an unmatched vertex. ⃝ True √ False vi. When we use the augmenting path to improve the matching, we can only increase the size of the matching by 1 every time. √ True ⃝ False

3. We are shipping pencils across the world. But, our supply chain is notoriously weak in some places. We know how many pencils we can send on each route, but we want to know where our supply chain is the weakest: i.e the minimum number of edges so that there is no path from our factory to our destination. We ship from our factory to only one final destination. (a) Describe the graph. Solution: This problem is the same as the edge disjoint path problem. We are trying to count the number of edges in the min cut. We can do this by setting all of the edge capacities to 1. (b) Describe the algorithm to find the number of edges. Solution: We will run Ford Fulkerson on the updated graph to find the max flow. The max flow will also be the number of edges in the min cut. (c) Explain correctness. Solution: By setting all edge capacities to 1, no augmenting path will ever use the same edge. This means that all paths are limited to the number of edges in the min cut. Because all of the capacities are 1, the number of edges in the min cut will also be the value of the max flow. (d) Explain runtime. Solution: FF runs in O(E * max flow) and changing the edges will take at most O(E), making the overall runtime O(E * max flow) .

4. We’ve discussed how you can find vertex disjoint paths in a graph. Let us consider another variation of this problem we’re instead of being used in at most one path, a vertex can be used in at most two paths. Give an efficient algorithm to solve this problem. Solution: Transform the graph in the following way, on each vertex, split that into two vertices with a capacity of 2 between them. For each edge, create a new edge with capacity of one. V ′ = { v in , v out : v ∈ V } , E ′ = { ( v in , v out , 2) : v ∈ V } ∪ { ( u out , v in , 1) : ( u, v ) ∈ E }

Array DP 6. It’s a sunny day, and you find yourself at an ice cream parlor with your friends. The ice cream parlor offers a variety of delicious ice cream flavors, each with a different calorie count. You want to enjoy the ice cream but also stay conscious of your calorie intake. You have a list of ice cream flavors, each with its calorie count, and you want to share the ice cream among your friends. However, you want to divide the ice creams into two subsets, ensuring that the calorie difference between the two groups is minimized while still making sure everyone gets their favorite flavors. You are given a list of n ice cream flavors, each with a specific calorie count. The goal is to divide these flavors into two sets, Set 1 and Set 2 , in such a way that: 1. The difference in total calorie counts between the two sets is minimized. 2. All your friends are happy with their chosen flavors. You must ensure that the union of Set 1 and Set 2 covers all the flavors, and each friend has their favorite flavors in one of the sets. Write a dynamic programming algorithm to solve this ice cream dilemma and find the mini- mum calorie difference while satisfying the above conditions. (a) Define your base case. Solution: Let us call the list of ice cream flavor calories A . We create a 2d array with dimensions n × sum ( A ). For i ∈ n : DP ( i, 0) = True (b) Define the recursive step. Solution: DP ( i, j ) =          True if i = 0 and j = 0 False if i = 0 and j ̸ = 0 DP ( i − 1 , j ) if A [ i ] > j DP ( i − 1 , j ) ∨ DP ( i − 1 , j − A [ i ]) if A [ i ] ≤ j To compute the minimum calorie difference: result = min j ≤ Total Sum 2 | sum ( A ) − 2 · j | Here j is the calorie count of one set and sum ( A ) − j is the calorie count of the other set. (c) Give the runtime of your algorithm. Solution: O ( n × sum ( A ))

7. Imagine you are an ambitious treasure hunter on a quest to find the most valuable gem in the world. Your journey takes you to an ancient, mysterious cave filled with various treasures, but also numerous traps and challenges. As you navigate through the cave, you must find a series of gems, and your success is determined by the product of the values of these gems. Your task is to find the most valuable subsequence of gems to maximize your treasure. That is, to succeed in this quest, you must determine the subarray with the largest product and return the product value. Note: the values of gems could be negative. You are given an array A of n integers, where each integer A [ i ] represents the value of a gem at position i . Your goal is to find the subarray (a consecutive sequence of gems) with the largest product value. Write a dynamic programming algorithm to solve this problem. Solution: Base Case: maxProduct [0] = minProduct [0] = A [0] Recurrence: max i> 0        maxProduct [ i ] = max( A [ i ] , maxProduct [ i − 1] · A [ i ] , minProduct [ i − 1] · A [ i ]) minProduct [ i ] = min( A [ i ] , maxProduct [ i − 1] · A [ i ] , minProduct [ i − 1] · A [ i ]) The time complexity is simply O ( n ), as this is a one-pass algorithm.

9. You work in a small printing agency where budgets and schedules are both really tight. You are a new recent hire who promises to squeeze out as many savings as possible from their limited but interesting printing technology. They recently purchased a printer before your arrival that has the ability to print the same text on two different sheets at the same time for the price of one sheet. This would have been a revolutionary spendings saver, however, the text being printed on both sheets have to be the exact same. Furthermore, once anything has been printed on the new printer, it does not accept the same banner to print on. While this would have been great for flyers, you work with banners where each banner proudly displays one highlighted word across and each banner has a different word. You decide to formulate an algorithm that might fit the job within your given constraints. Based on two words for two different advertisements, can you find an algorithm that can give the greatest savings to the company? (Note: While this special printer accepts only empty canvases, regular printers can accept banners that have been printed on and can print the remaining letters on the two banners at the standard cost) Solution: Define your table and the entries of your table. Create a 2D array indexed by i and j in the bounds of the length of both strings, S1 and S2, respectively. Each entry in the table is a length of the largest common substring that can be printed by the special printer for the substrings S1[1:i] for the first word and S2[1:j] for the second word. (a) Define your base cases. Solution: The only base case is that T[0,0] = 0 (b) Define the recursive step. Solution: For each iteration, we use the following recurrence: If i, j > 0 and S 1[ i ] == S 2[ j ], T [ i, j ] = 1 + T [ i − 1 , j − 1] Else, T [ i, j ] = 0 Use a variable to keep track of the current maximum of the string at any given point in time and this value is the solution

Graph DP 10. Let’s revisit the diameter of a Binary Tree. In this problem, we’re trying to find the longest path between two nodes in a binary tree, where the length is represented by the number of edges between them. (a) Define your table and the entries of your table. Solution: Each entry in the table will be a tuple, including the longest path from that node to a leaf, and the largest diameter up to that point. (b) Define your base cases. Solution: Let’s create one fake node representing an empty node. The length of the longest diameter including no nodes is 0 and the length of the longest path to a leaf that doesn’t exist will also be 0. (c) Define the recursive step. Solution: Let l be the left child and r be the right child; if either of these don’t exist use the fake node instead. T [ v ] = (max( T [ l ] . 0 , T [ r ] . 0) + 1 , max( T [ l ] . 1 , T [ r ] . 1 , T [ l ] . 0 + T [ r ] . 0)) (d) Give the runtime of your algorithm. Solution: Each node takes constant time, so it’s linear with respect to the nodes.

(c) Define the recursive step. Solution: Each edge represents a train would extend the path by one. We’ll take the minimum of all edges that go to some vertex. T [ i, v ] = min ( u,v ) ∈ E ( T [ i − 1 , u ] + w ( u, v ) , T [ i − 1 , v ]) (d) Justify the runtime of your algorithm. Solution: The longest path can be | V | , so if we bound k by | V | , our table is at most O ( | V | 2 ). Naively the runtime would be O ( | V | 2 | E | ). However if we think about the rows, there are O ( | V | ) rows, and each take O ( | E | ) time to fill out, so the total runtime would be O ( | V || E | ).

Knapsack 12. Will’s trying to host Thanksgiving dinner for the family, but he’s never hosted it before. He plans to cook all the food, but with his busy lifestyle he can’t cook all the Thanksgiving dinner food. Then, he has the family vote on what they would most like to eat, and he estimates how long it would take to cook the food. He’s ok with only pleasing some portion of the family In other words, given a list of N dishes, the total votes v i for each dish, and how long each dish takes to prepare t i , figure out a set of dishes that can be prepared in the least amount of time and still meet or exceed the vote threshold V . Note that only one dish can be in progress at one time. Which of the following transformations to knapsack would result in a correct result; where in knapsack, C is the capacity, w i is the weight and g i is the value of the good. √ C = − V, w i = − v i , g i = − t i ⃝ C = − V, w i = v i , g i = t i ⃝ C = − V, w i = t i , g i = v i ⃝ C = V, w i = − t i , g i = − v i ⃝ C = V, w i = t i , g i = − v i ⃝ C = − V, w i = − v i , g i = t i