首页 >
> 详细

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 piijk 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.

Uptown Downtown

St. A

St. B

St. C

St. D

St. E

St. F

$40

$10

$18

$12

$23

$50

$20

$25

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.)

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,

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Coursework: Colliding Suns 2021-02-25
- Ecs 36 B Homework #6 2021-02-25
- Comp3258 Final Project 2021-02-25
- Int301 Bio-Computation 2021-02-25
- Assignment 2 Write A Device Driver 2021-02-25
- Cis 415 - Operating Systems 2021-02-25
- Data编程实验代做、代写java编程实验、Python，C++程序代做代写 2021-02-25
- Mat 3373编程语言代写、代做r编程设计、R程序调试代写python程序 2021-02-25
- 代写program编程、代做java，Cs程序语言、C++，Python编程 2021-02-25
- W21 Lab 4代做、代写c++程序、代做c/C++编程实验代做r语言编程 2021-02-25
- 代写ece36800编程课程、代做c++，Java程序、Python程序语言 2021-02-25
- 代做cs 325编程、代写java，Python，Cs程序语言代写web开发 2021-02-25
- Gr5241编程代做、代写r留学生程序、R实验编程调试代写python编程| 2021-02-25
- Program编程设计代做、代写g++程序设计、C++，Cs编程语言代写代写 2021-02-05
- Cs1003编程语言代做、代写programming程序、Java编程设计调 2021-02-05
- 代做cs 505程序实验、代写python，Cs语言编程、Java程序设计调 2021-02-05
- Ics 53留学生程序代做、代写java，C++，Python实验编程代写w 2021-02-05
- 代写csci 3162程序、代做matlab课程编程、Matlab编程语言调 2021-02-05
- Cs 480-2程序设计代做、代写data程序实验、C/C++编程语言调试代 2021-02-04
- Cst8237课程编程代做、代写java，Python编程实验、Cs，Jav 2021-02-04