CS 577: Introduction to Algorithms Spring 2020 Final Exam
Instructors: Shuchi Chawla & Christos Tzamos Due: May 7, 2020, 11:59 p.m.
Guidelines:
• You have five days to complete this exam. Please upload your solutions in PDF format on Canvas by the due date.
• The exam is due by May 7, 2020, 11:59 p.m. No extensions will be provided under any circumstances.
• You are required to answer each of the THREE multi-part questions.
• You can use all the results we showed in class or in the homework. Clearly state the results you use. Substantiate all other claims you make.
• You are not allowed to consult any material outside of material provided for this course. Any evidence of cheating or plagiarism will be dealt with utmost seriousness.
• For your convenience, at the back of this exam we have included a list of decision problems proven to be NP-Complete in class.
GOOD LUCK!
Problems:
1. [3+1+1+1 points] You have designed a new single-player multi-level game of strategy and chance for your gaming startup where players aim to maximize the number of points they collect before completing all levels. Now you would like to design an algorithm to compute the most number of points a player can obtain in the game in expectation by playing an optimal strategy.
Here is how the game works. There are n levels. In each level i, the player has m actions available. The jth action awards the player Pij points but takes the player to a random level above i. In particular the player has a probability πijk of ending up at a level k > i upon following action j in level i. The game ends when the player reaches level n. A strategy for the player assigns an action to follow at every level i.
In this question you will develop a dynamic program for solving this problem. For full credit, your algorithm should run in time poly(n, m).
(a) Define a function that computes the expected total points obtained by the optimal player strategy. Provide recursive equations for computing the function.
(b) Briefly explain (in 1-2 sentences) why your recursive equations are correct.
(c) Write a dynamic program based on your recursive equations to compute the expected total points obtained by the optimal player strategy.
(d) State the running time of your program.
2. [3+1+1 points] Residents of the city of TrainVille use its extensive public transportation system to commute from home to work everyday. Stations throughout the city are interconnected by subway lines. An advertising company in the city of TrainVille wants to target its ads to all commuters going from the Uptown station to the Downtown station. There are multiple routes going from Uptown to Downtown, and different stations charge different amounts for displaying ads. The advertising company’s goal is to ensure that along any such route, at least one station carries their ad, while minimizing the total amount of money they spend.
In this question, you will develop a polynomial time algorithm for this problem by reducing it to the network flow problem. Your algorithm is given as input a subway map for the city of TrainVille that shows all of the train connections between the n stations in the city, as well as the price of advertisement at each individual station.
(a) Describe a reduction from the advertising problem to max s-t flow or min s-t cut. Remember to specify how to convert a solution of your reduced instance into a solution to the advertising problem.
(b) What does your network flow instance look like when given the map below? What is the optimal solution in this map?
(c) Give a brief (1 paragraph) argument for the correctness of your reduction.
3. [1+2+2 points] You go into a store and want to buy several items. The store has n different items. Item i is priced at $pi, and you have a value of $vi for this item. You want to purchase a set S of items so as to maximize your net utility from the purchase—the total value you get minus the price you pay. In order to do so, you should buy precisely the items for which vi > pi. However, there is a catch. If you spend a total of at least T dollars, you get a 10% discount on your total payment. So it may make sense to buy some items for which vi ≤ pi.
For example suppose that the store has three items, each of which you value at $10. Suppose that the three items are priced at $9, $11, and $13 respectively, and the discount threshold T is $15. Then, without the discount you would want to buy only the first item, which brings you a net utility of $1. However, with the discount, it makes sense to buy the first two items. This brings you a total value of $20 at a price of 90% × $20, or a net utility of $2.
In the decision version of this problem, you are given the n positive integral prices, n positive integral values, the discount threshold T, and a utility target U. Your goal is to determine whether there is a set S of items that brings you utility at least U. You will prove that this problem is NP-hard by providing a mapping reduction.
(a) Specify which problem you will reduce to what. (b) Describe your mapping reduction.
(c) Prove that the mapping reduction is correct. (Remember that you need to show two implications.)
St. A $18
St. B $10
St. C $12
St. D $23
St. E $25
$50
Uptown
$40
Downtown
St. F $20
For your reference, here is a (partial) list of NP-Complete problems discussed in class and their definitions.
• 3-SAT: Given a 3-CNF formula, is the formula satisfiable?
• Vertex Cover: Given a graph G and target k, does the graph contain a vertex cover of size at most k? A vertex cover is a subset of vertices that includes at least one end point of every edge in the graph.
• Independent Set: Given a graph G and target k, does the graph contain an independent set of size at least k? An independent set is a subset of vertices such that no two vertices in the subset are connected by an edge.
• Clique: Given a graph G and target k, does the graph contain a clique of size at least k? A clique is a subset of vertices such that every pair of vertices in the subset is connected by an edge.
• Subset Sum: Given n positive integers x1, · · · , xn and a target k, is there a subset S ⊆ [n] such that the numbers corresponding to the indices in S add up exactly to k, that is, i∈S xi = k?
• Knapsack: Given n positive integer values v1, · · · , vn; n positive integer weights w1, · · · , wn; knapsack capacity C; and a target k, is there a subset S ⊆ [n] such that i∈S wi ≤ C and i∈S vi ≥ k?