Computationally Hard Problems
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Written exam, December 11, 2023
Course name: Computationally Hard Problems
Course No.: 02249
Aids allowed: all aids are allowed
Duration: 4 hours
Weighting: Exercise 1 – 10%, Exercise 2 – 15%, Exercise 3 – 10%,
Exercise 4 – 20%, Exercise 5 – 15%, Exercise 6 – 10%, Exercise 7 – 20%.
All exercises should be answered by filling out the boxes below the statement of the assignment or ticking boxes in the multiple-choice exercise. You can either use a PDF editing/annotation tool (including a digital pen) directly on this file or put your solutions into the LATEX source that is embedded in this PDF (visible, e.g., in Adobe Acrobat and Evince as well as the PDF viewer built into the Firefox browser) and recompile the document. If you edit the LATEX source, you should put your answers into the environments that look as follows:
{%Here you can write your solution .
}
For the multiple-choice questions, there are instructions in the source of the following kind:
{}% put an X inside the braces if you select TRUE .
If at all possible, do not change the layout of the exam and keep all answer boxes in place. In particular, do not leave out pages from this exam set of 20 pages. In the unlikely case that you need extra space, add extra pages after page 20.
Submit the solved exam as a PDF file on https://eksamen.dtu. dk/ before the deadline. Other file formats are not accepted.
Exercise 1: A permutation on the first n natural numbers, where n ∈ N is a positive integer, is a sequence i1 ,..., in that contains each element from {1,..., n} exactly once. For example, for n = 11 the so-called reverse permutation is 11, 10, . . . , 1.
a) Specify the alphabet Σperm you use.
b) Specify how the language Lperm is defined and describe how the above example is coded in your language.
c) Describe how to check whether a given word w ∈ Σp(*)erm is a description of a permutation on the first n natural numbers for some n ∈ N, and, if so, how the permutation can be reconstructed.
Exercise 2: Consider the following problem:
|
Problem [DegreeConstrainedSpanningTree] Input: An undirected graph G = (V, E) and (only for the decision version) a positive integer k ≤ |V | . Output for the decision version: YES if there is a spanning tree T = (V, E′ ),where E′ 己 E , for G such that the degree of any vertex in T is at most k. NO otherwise. Output for the optimization version: A spanning tree T = (V, E′ ) for G where the maxi- mum degree of the vertices is as small as possible. |
Definition of possibly unknown terms: for an undirected graph G = (V, E), a spanning tree T = (V, E′ ), where E′ 己 E, is a subgraph of G that is connected and does not contain any cycles. The degree of a vertex v ∈ V is the number of edges incident on v.
Task: you are given an algorithm Ad for solving the decision version of DegreeConstrainedSpan- ningTree. Show how to convert this into a polynomial-time algorithm Ao for the optimization version of the problem.
a) Describe an algorithm Ao as explained above. The running time of Ao has to be polynomial in the input size and Ao may make calls to Ad. Recall that such a call counts as one step.
We suggest that you divide the description of your algorithm into two subsequent phases.
a1) Describe the first phase of your algorithm.
a2) Describe the second phase of your algorithm.
b) Argue that your algorithm is correct.
c) Show the polynomial running time of your algorithm.
Exercise 3: Given a directed graph G = (V, E), where V = {1,..., n}, we call a sequence of k pairwise distinct vertices i1 ,..., ik an attractor of size k if for all j E {1,..., k} and all a E V / {i1 ,..., ik } it holds that (a,ij ) E E and (ij , a) E. For example, the following graph has an attractor of size 2.
Consider the following problem.
|
Problem [Attractor] Input: A directed graph G = (V, E), where V = {1,..., n}, and a non-negative integer k. Output: YES if G has an attractor of size k and NO otherwise. |
Show that the problem Attractor is in the class Ⅵ此. Do not try to show that it is Ⅵ此-complete. We suggest the following structure for your proof:
1) Design a deterministic algorithm A(X, R) (in the following just called A) which takes as input a problem instance X and a random sequence R. Especially:
1a) Specify what the random sequence R consists of: bits, integers in some finite range etc.
1b) Specify how A interprets R as a guess.
1c) Specify how A verifies the guess.
2) Show that the following two conditions are met:
2a) If the answer to X is YES, then there is a string R0 with positive probability such that A(X, R0 ) = YES.
2b) If the answer to X is NO, then A(X, R) = NO for all R.
3) Show that the running time of A is polynomially bounded.
Exercise 4: Consider the following problem:
|
Problem [SparseSubSetSum] Input: Positive integers s1 , s2 ,...,sn and a positive integer B . Output: YES if there is a subset A ⊆ {1,..., n} such that both . |A| ≤ n/2 . and：i=A si = B . NO otherwise. |
Prove that SparseSubSetSum is NP-complete. To this end, you may assume that SparseSub- SetSum is in NP. Especially show:
(A) Find a suitable problem Pc which is known to be NP-complete.
(B) Prove Pc ≤p SparseSubSetSum, especially:
(B.1) Describe a transformation T which transforms every instance X of Pc into an instance T(X) of SparseSubSetSum and which runs polynomial in the size ∥X∥ of X .
Hint: use a simple transformation that introduces unusable elements.
(B.2) Show that if the answer to X is YES then so is the answer to T(X).
(B.3) Show that if the answer to T(X) is YES then so is the answer to X .
Exercise 5: Suppose you run the algorithm from Section 5.2 of the lecture notes for computing an independent set on the undirected line graph Gline = (V, E), defined by V = {1,..., n} and E = {{i,i + 1} | i = 1,..., n − 1} for some odd integer n ≥ 3. Note that this graph has n − 3 edges where both endpoints have degree 2, and 2 edges where one endpoint has degree 1 and the other endpoint degree 2. The unique largest independent set consists of the (n+1)/2 odd-numbered vertices 1, 3, 5,..., n − 2,n.
a) Define a choice of the pi (not necessarily all equal) that makes the algorithm return the largest independent set, and explain why this is the case.
b) Compute the bound on the expected size of the independent set constructed by the algorithm for the following three different choices of the pi , using the analysis from the notes. Give an expression depending on n; e.g., you may find out that the expected size is at least 1+(n−1)/4. b.1) pi = 1/davg for i ∈ {1,..., n}, where davg = 2|E|/n is the average degree of Gline :
b.2) pi = 1/di for i ∈ {1,..., n}, where di is the degree of vertex i:
b.3) pi = 1 for i ∈ {1,..., n}:
c) Still using pi = 1 for i ∈ {1,..., n}: Prove that the algorithm returns the largest independent set with probability at least 2 −n. Argue why the probability of returning the largest independent set is at most 2 −(n−1)/2 .
Note: When the algorithm finds for {i,j} ∈ E that both i ∈ I and j ∈ I, it removes either i or j from I, chosen uniformly at random.
Exercise 6: Consider the following five clauses over the boolean variables {x1 , x2 , x3 }:
a) Suppose you draw a truth assignment uniformly at random. Compute for each clause the probability of being satisfied and derive the expected number of satisfied clauses.
b) Compute for each xi , where i ∈ {1, 2, 3}, the fraction
i.e., the relative frequency of positive literals in the literals involving xi.
Suppose you apply randomized rounding as described in Section 5.3 of the lecture notes, using the pi instead of theˆ(y)i as probabilities to determine the truth settings of the corresponding vari- ables. Compute the expected number of clauses satisfied by this kind of randomized rounding. Compare it to the expected number you obtained in part a).
Exercise 7: [Multiple choice] Answer the multiple choice questions below. There are 10 questions in total. An incorrect answer is counted negatively, that is, it cancels out a correct answer. However, the total number of points will be at least 0.
1.) If a problem is in the class 此此 then it is also in the class Ⅵ此 .
2.) The expression Tand(1, 2) Tand(3, 4) is always true.
3.) Las Vegas algorithms always give a YES/NO-answer.
4.) If a randomized algorithm for a decision problem has one-sided error and gives the correct answer with probability at least 1/2, then it can be converted to one that gives the correct answer with probability at least 3/4.
5.) Section 5.4 of the lecture notes describes a pseudo-polynomial al-gorithm for 3-SAT.
6.) A randomized algorithm with expected runtime n2 will not stop within time 100n2 with probability at least 0.99.
7.) The expected value printed by following program snippet is 5.
i — 3
while (Tand(3, 4) + Tand(1, 2) 
6) do
i — i + 1
end while
print(i);
8.) The TSP tour (1, 2, 3, 4, 5, 6) can be transformed into the tour (1, 5, 3, 4, 2, 6) by a single 2-OPT mutation.
9.) The randomized search heuristic (1+1) EA optimizes every function f : {0, 1}n 一 R in expected time O(nn ).
10.) Consider the approximation scheme for Knapsack from Sec- tion 4.5.3 of the notes and suppose that s1 /k is not an integer. Then the output of the algorithm cannot be an optimal solution.
2024-01-18