CS 341, Fall 2020
A. Lubiw, A. Storjohann
Released: Thursday December 10, 8 AM. DUE: Wednesday December 16, 11:59 PM.
IMPORTANT INSTRUCTIONS
Copyright By PowCoder代写 加微信 powcoder
Start each question on a new page and answer the questions in order. If you hand- write, make it legible!
For an algorithm you must include: a description in English; pseudocode (unless the algorithm is really simple); correctness proof; and runtime analysis. Always try for the fastest algorithm you can.
For an NP-completeness proof you must include:
(i) a proof that the problem lies in NP
(ii) a statement (with ≤P ) about which problem you will reduce to which
(iii) your many-one reduction
(iv) a proof of correctness
(v) a justification that your reduction takes polynomial time (in most cases, this can be brief).
You may assume that the following problems are NP-complete: 3-SAT, Clique, Independent Set, Vertex Cover, Hamiltonian cycle/path (both directed and undirected), Subset Sum.
This exam is for students currently enrolled in the Fall 2020 offering of CS 341 only. It may not be copied or distributed in any way, including electronically, to any other person without explicit written permission from the instructors.
YOU MUST HANDWRITE AND SIGN THE FOLLOWING STATEMENT
(e.g., write it on paper, take a photo, and include that with your Crowdmark submission)
I promise, on my honour, that the work on this exam is my own. Apart from the course materials and private Piazza questions, I have not given or received any assistance on this exam.
1. Short Answer [15 marks]
(a) [3 marks] Let G = (V, E) be an undirected graph with k connected components. Given a new edge (u, v) for u, v ∈ V , how may connected components can G′ = (V, E ∪ {(u, v)}) have? Briefly justify your answer.
(b) [3 marks] True or False: If a problem in NP is shown to be in P, then P=NP. Briefly justify your answer.
(c) [3 marks] Consider the following problem.
Given a program P does it output 1 when run on no input? (YES or NO)
FACT: this problem is undecidable.
What is wrong with the following algorithm for the problem: Scan the code and see if
there is a statement of the form “PRINT(1)” (in the appropriate syntax for the language). If there is, then output YES; otherwise output NO.
(d) [3 marks] Give a very short program that takes no input and does not halt.
(e) [3 marks] What is wrong with the following argument that the prime factors of a number
n can be found in polynomial time?
Input: a number n.
if n is prime then output n else
while i < n do
if i divides n and i is prime then output i i := i + 1
This algorithm is correct. Since there is a polynomial time algorithm to test if a number is prime, the algorithm runs in polynomial time.
2. [10 marks] Divide-and-Conquer. In a binary computer, integers are stored using their binary encoding. For example, the binary encoding of integers of a single decimal digit are given by the following table binary[0 . . . 9]:
x0123456789 binary[x] 0 1 10 11 100 101 110 111 1000 1001
When a program reads in a decimal integer from a file it needs to convert from the decimal encoding to the binary encoding. This question is about an efficient algorithm to do the conversion. Assume we have functions Add(a, b) and Multiply(a, b) that take as input two binary numbers a and b and return their sum and product as binary numbers, respectively. Add(a,b) runs in time O(l) and Multiply(a,b) runs in time O(llog2 3) where l is a bound on the number of bits in a and b.
(a) [4 marks] We begin with a helper function PowOfTenToBin(n) that takes as input a number n and outputs the binary representation of 10n. Assume that n is a power of 2.
PowOfTenToBin(n) if n = 1 then
return 1010 else
return Multiply(a,a)
i. [2 marks] Fill in the missing details, that is, complete the line a := ???.
ii. [1 mark] Give a recurrence relation for the running time T (n) of the algorithm.
iii. [1 mark] Give a big-oh expression for the run time. You may use the Master Theo- rem.
(b) [6 marks] Now we want to convert any nonnegative integer x with n decimal digits (where n is a power of 2) to binary. The integer x is given as an array A[1 . . . n] that contains the decimal digits of x in order from most significant to least significant. For example, A[1 . . . 4] = [0, 1, 5, 3] corresponds to the integer x = 153. The following algorithm does the conversion:
DecToBin(A, n) if n = 1 then
return binary[A[1]] else
AL[1...n/2] := A[1...n/2] AR[1 . . . n/2] := A[n/2 + 1 . . . n] return ???
i. [4 marks] Fill in the missing details, that is, complete the line return ???.
ii. [1 mark] Give a recurrence relation for the running time T (n) of the algorithm. Note
that the lookup in the table binary has cost O(1) time.
iii. [1 mark] Give a big-oh expression for the run time. You may use the Master Theo- rem.
3. [10 marks] Greedy. Suppose you are given the positions of n geese along a line, gi ∈ R, i = 1,...,n, and the positions of n goose nests along the same line, hi ∈ R,i = 1,...,n. The goal is to assign each goose to a nest, with only one goose per nest, so that you minimize the maximum distance that any goose must travel to get to its nest. The positions of the geese and the nests are not in sorted order, but the goose positions are distinct and the nest positions are distinct.
First consider the following greedy algorithm: Find a pair gi , hj that minimizes |gi − hj |. Assign goose i to nest j, and recurse on the remaining n − 1 geese and nests.
(a) [2 marks] Give an example to show that this greedy algorithm does not always produce an optimal solution.
Next, consider the following algorithm: Sort the goose positions and the nest positions to get listsgi1 ≤gi2 ≤···≤gin andhj1 ≤hj2 ≤···≤hjn. Assigngooseik tonestjk fork=1..n.
To prove that this algorithm is correct, we need the following Lemma.
Lemma. Consider an assignment A of geese to nests in which two geese are assigned to nests outoforder,i.e.,therearetwogeeseia andib witha
(a) [2 marks] Show that this tree has a vertex cover of size 3:
There is a dynamic programming algorithm to find the minimum size vertex cover of a tree. For each i, let Ti be the subtree that is rooted at vertex i and contains all the descendants of vertex i. (For example, in the above tree, T2 consists of vertices 2, 3, 8, 9.) For each i we find three values:
Cin[i], the minimum size of a vertex cover of Ti that contains i
Cout[i], the minimum size of a vertex cover of Ti that does not contain i C[i], the minimum size of a vertex cover of Ti
We solve these subproblems in order i = n, n − 1, . . . , 1.
(b) [4 marks] Fill in the following high-level pseudocode. You may use expressions like
j∈D[i] · · · instead of explicitly writing the loop. for i = n downto 1 do
if i has no children then Cin[i]:= 1; Cout[i] := 0; C[i] := 0; else Cin[i] :=
Cout[i] :=
(c) [2 marks] Prove that your algorithm correctly finds the minimum size of a vertex cover. (d) [2 marks] Analyze the runtime of the algorithm. Be sure to include the time to compute
any expression of the form j∈D[i].
5. [10 marks] Graph Algorithms. Let G = (V, E) be an undirected graph with n vertices and m edges, and let T ⊆ E be a spanning tree of G. A swap operation on T replaces one edge of T by an edge of E such that the result is again a spanning tree. Give an algorithm that takes as input a graph G and two spanning trees T1 and T2 and finds a sequence of swaps to convert T1 to T2 such that the number of swaps in the sequence is the minimum possible.
Note: This is a harder question. Your answer will be marked based on the runtime of your algorithm and the elegance of your answer. If you are short of time, or having difficulties, we recommend skipping this question.
6. [15 marks] NP-completeness
(a) [7 marks] Prove that the following Scenic Path problem is NP-complete:
Scenic Path
Input: An undirected graph G = (V,E), and number k, and for every edge e ∈ E, a scenic value s(e) ∈ R.
Output: Is there a simple path in G such that the sum of the scenic values of the edges in the path is ≥ k? (YES or NO)
(b) [8 marks] Consider the following SAT variant:
Input: A SAT formula in Conjunctive Normal Form, with n variables and m clauses.
Output: Is there a truth-value assignment to the variables that satisfies at least 32 of the clauses (i.e., that satisfies ≥ 23 m clauses)? (YES or NO)
i. [1 mark] What is the output for (x1 ∨ x2) ∧ (x3) ∧ (¬x3)?
ii. [7 marks] Prove that SAT-23 is NP-complete.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com