CS代考 CS70 Midterm Exam 3 Spring 2022 v4

CS70 Midterm Exam 3 Spring 2022 v4

CS570 Spring 2022: Analysis of Algorithms Exam III

Points Points
Problem 1 20 Problem 5 9
Problem 2 9 Problem 6 15
Problem 3 18 Problem 7 17
Problem 4 12

Instructions:
1. This is a 2-hr exam. Open book and notes. No electronic devices or internet access.
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.
4. If you require an additional page for a question, you can use the extra page provided within

this booklet. However please indicate clearly that you are continuing the solution on the
additional page.

5. Do not detach any sheets from the booklet. Detached sheets will not be scanned.
6. If using a pencil to write the answers, make sure you apply enough pressure, so your answers

are readable in the scanned copy of your exam.
7. Do not write your answers in cursive scripts.
8. This exam is printed double sided. Check and use the back of each page.

Mark the following statements as TRUE or FALSE by circling the correct answer.
No need to provide any justification.

[ TRUE/FALSE ]
If P = NP, then all problems in P are NP-complete.

[ TRUE/FALSE ]
Assuming that we have found a correct optimal solution to an LP problem, if
someone claims to have found a different optimal solution, we know that that solution
must be incorrect.

[ TRUE/FALSE ]
Let X and Y be decision problems for which there exist efficient certifiers, and
assume P ≠ NP. If X ≤P Y and Y ≤P X, then both X and Y are NP-complete.

[ TRUE/FALSE ]
Minimum Spanning Tree (MST) ≤P Hamiltonian Path.

[ TRUE/FALSE ]
The optimization version of the Linear Programming is not in NP.

[ TRUE/FALSE ]
If P=NP, then some NP-hard problems can be solved in polynomial time.

[ TRUE/FALSE ]
Even if P≠NP, there is a polynomial-time algorithm for the 0/1 Knapsack problem
when all items have the same weight-to-value ratio

[ TRUE/FALSE ]
If P = NP, then every decision problem whose solution can be verified in polynomial
time can itself be solved in polynomial time.

[ TRUE/FALSE ]
Integer Max Flow (where flows and capacities are integer-valued) is polynomial-time
reducible to Linear Programming.

[ TRUE/FALSE ]
Maximize Σ xi(1 – xi) (1 ≤ i ≤ n)
subject to xi + xj < 1 and xi ∈ {0, 1} (1 ≤ i ≤ n, 1 ≤ j ≤ m) where n and m are constants, is an integer linear program. i) Which of the following problems have been proved to be not solvable in polynomial time? Circle all correct answers A. Traveling Salesman B. Integer Linear Programming C. Subset sum D. All of the above E. None of the above ii) Let X, Y, Z, and W be problems. Suppose Z is polynomial-time reducible to X, and X is NP-complete. Which of the following statements are true? Circle all correct answers. A. If Vertex Cover is polynomial-time reducible to problem Z, then Z is NP-Complete. B. If there exists an efficient certifier for problem Z, then Z is NP-Complete. C. X is polynomial-time reducible to Independent Set. D. If X is polynomial-time reducible to Y, then Z is polynomial-time reducible to Y. E. If Z is polynomial-time reducible to W, then X is polynomial-time reducible to W. iii) If a problem X is in NP, then it must be NP-complete if… (Circle all correct a. It is polynomial-time reducible to 3-SAT. b. 3-SAT can be reduced to it in polynomial time. c. It can be reduced to every other problem in NP in polynomial time. d. Some problem in NP can be reduced to it in polynomial time. A paper company is building warehouses to supply its m ≥ 1 customers. The company is considering whether to build a warehouse at each of n ≥ 1 potential construction sites. The cost of building a warehouse at site i is denoted by bi ≥ 0. After the warehouses are built, the company assigns each customer to a warehouse that will supply it. Each warehouse that is built may supply paper to any number of customers, but each customer is supplied by exactly one warehouse. The cost of supplying customer j from a warehouse built at site i is denoted by sij ≥ 0. Consider the Warehouse Construction Optimization problem: Given construction costs bi (1 ≤ i ≤ n) and warehouse-customer supply costs sij (1 ≤ i ≤ n, 1 ≤ j ≤ m), make a selection of a subset of construction sites and an assignment of customers to warehouses such that the total cost of building a warehouse at each selected site and supplying each customer from their assigned warehouse is minimized. a) Reduce the above Warehouse Construction problem to Integer Linear Programming. (16 pts total) i) Describe what your ILP variables represent. (5 pts) ii) Show your objective function. (4 pts) iii) Show your constraints (7 pts) b) [ TRUE/FALSE ] (2 pts) The above reduction shows that the Warehouse Construction optimization problem is NP-hard. Suppose that we have developed an approximation algorithm that takes as input a graph G=(V,E) and a real number ρ > 1 and returns a vertex cover whose size is less than ρ
times the size of a minimum vertex cover.

Prove that the running time of this approximation algorithm is not polynomial in the size
of the input unless P=NP.

For each of the problems defined below, determine which class the problem belongs to
from the options below. Assume P ≠ NP.

1. The problem is in P.
2. The problem is in NP but not in P.
3. The problem is neither in P nor NP.

a) Given a list of positive integers A[1..n] and a positive integer k, does there exist an
increasing subsequence of A of length at least k?

b) Given an undirected graph with weights on its vertices, return an independent set with
maximum total weight.

c) Given a computer program and an input to the program, will the program terminate
for the given input?

Several artificial lights are installed in a greenhouse to provide light for several plants.
Each light may provide light to multiple plants, and each plant receives sufficient light so
long as it is exposed to at least one light. The greenhouse operators are planning to
uninstall some lights to reduce their costs.
The greenhouse operators have designed a greedy algorithm for minimizing the number
of lights in the greenhouse such that each plant is still exposed to at least one light:

Begin by turning off all the lights. Then, in each iteration, turn on the light that
exposes the most plants to light that are not exposed yet. Repeat until all plants
are exposed to at least one light. Then, uninstall the lights that are still turned off.

a) Give a counterexample to prove that this algorithm does not always give the optimal
solution. (5 pts)

b) Prove that if we used the above algorithm as an approximation algorithm, this
approximation algorithm has no constant approximation ratio > 1. In other words, if
the minimum number of lights needed is C∗, prove that there is no constant ρ (ρ > 1)
such that we can guarantee the algorithm returns a solution with total number of lights
≤ ρC∗. (10 pts)

Consider the following problem:

Given an undirected graph G(V,E) with n vertices, a list L[1..n] of n
non-negative integers, and a non-negative integer B, does there exist a
function f : L → V that assigns each number in L to a vertex in G such

∑(u,v)∈ E f(u) ⋅ f(v) ≤ B?

For example, the following is a YES instance of this problem (i.e. an instance for
which such a function f exists):

Here is one possible assignment function:
L1 → A, L2 → B, L3 → D, L4 → C

Continued of next page

a) Prove that the problem is in NP. (5 pts)

b) Prove that the problem is NP-Complete. (Hint: use Vertex Cover) (12 pts)

Additional Space

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts