EECS 376: Foundations of Computer Science Winter 2021, University of Michigan,
EECS 376 Practice Final SOLUTIONS
The multiple-choice portion of the exam consists of 10 randomly selected questions out of the “Multiple Choice”, “All/Some/No”, and “True/False/Unknown” sections below. The written portion of the exam consists of 4 randomly selected questions out of the “Written Answer” section below. These two portions are released as separate Canvas quizzes. You are to submit the answers to the multiple-choice portion on Canvas. Submit your written solutions to Gradescope as you would for a homework assignment. You will not submit anything on Canvas for the written part.
The multiple-choice Canvas quiz has a time limit of 30 minutes, plus a 10-minute grace period. The expected time to complete the written portion is 40 minutes. However, you may submit any time within the 2-hour window for the exam. Both portions must be submitted before 9pm Eastern Time.
Copyright By PowCoder代写 加微信 powcoder
Logistics:
• The exam will take place on Thursday, April 29, 7pm – 9pm Eastern Time.
• You must submit your multiple-choice answers on Canvas prior to 9pm Eastern Time. You will have 30 minutes plus a 10-minute grace period to take the quiz, but it must be submitted before 9pm.
• You must submit your written answers to Gradescope prior to 9pm Eastern Time. There will be no grace period for the written portion. As with the homework, we suggest you start your submission at least 15 minutes before the deadline.
• You may use any static resources for the exam, including the textbooks, lecture slides, Google, etc. You may not use calculators (e.g. a physical calculator, WolframAlpha, etc.), as we consider that to be a dynamic resource.
• You are prohibited from searching for answers to any of the exam questions online.
• You are prohibited from soliciting help from anyone, whether in person, over text/chat, on StackOver-
flow, making public Piazza posts, or any other means.
• Your solutions must be entirely your own work.
• If you have clarification questions, make a private post on Piazza, and a staff member will respond as soon as possible.
• If you run into technical issues or have an emergency, contact the staff right away. Do not contact a fellow student for help.
Any deviation from these rules will constitute an Honor Code violation. In addition, the staff reserves the right not to grade any exam taken in violation of this policy.
Attest to the following honor pledge by signing your name below.
Honor pledge:
I have neither given nor received aid on this exam, nor have I concealed any violations of the Honor Code. I will not discuss the exam with anyone who has not already taken it.
I am taking the exam at the time I was assigned by the staff.
Signature:
Recall the following languages (unless otherwise specified, all graphs are undirected): • LHALT = {⟨M, x⟩ : M is a Turing machine that halts on input x}
• L={x∈Σ∗ :x̸∈L}
• SAT = {φ : φ is a satisfiable Boolean formula}
• 3SAT = {φ : φ is a satisfiable 3CNF formula}
• Clique = {(G, k) : G is a graph with a clique of size (at least) k}
• Vertex-Cover = {(G, k) : G is a graph with a vertex cover of size (at most) k}
• Independent-Set = {(G, k) : G is a graph with an independent set of size (at least) k} • Hamiltonian-Cycle = {G : G is a graph with a Hamiltonian cycle}
• TSP = {(G,k) : G is a weighted graph with a tour of weight at most k}
• Max-Cut={(G,k):Gisagraphwithacutofsizeatleastk}
Multiple Choice
1. ConsiderarecurrenceoftheformT(n)=12T(2n−32n)+O(n3). Whatistheasymptoticcomplexity of this recurrence according to the Master Theorem?
B. O(nlog2(12))
D. O(nlog12(2))
E. The Master Theorem cannot be used in this case
Solution: The Master Theorem states that for any recurrence of the form T(n) = kT(n/b) + O(nd)
where k, b > 1, we have
O(nd), T(n) = O(nd logn),
if (k/bd) < 1 if (k/bd) = 1 if (k/bd) > 1.
sok=12,b=2,andd=3. Since
k/bd =12/23 =12/8=3/2>1,
the Master Theorem then tells us that
T(n) = O(nlogb k) = O(nlog2(12)),
which is choice B.
Simplifying, the given recurrence is
O(nlogb k),
T (n) = 12T (n/2) + O(n3),
2. Rice’s Theorem can be used to prove that the language
LLIKES-ZEROES = {⟨M⟩ : M accepts all binary strings with at least one 0}
A. undecidable
B. decidable
C. infinite
D. countable
E. Rice’s theorem cannot be used to analyze this language
Solution: Let S = {x ∈ Σ∗ : x contains at least one 0}. Then we can define a semantic property as follows:
P = {L : S ⊆ L}
In other words, the property is the set of languages that contain all the elements in S. If machine M accepts all binary string with at least one 0, then S ⊆ L(M), and
LLIKES-ZEROES = {⟨M⟩ : M accepts all binary strings with at least one 0} ={⟨M⟩:S ⊆L(M)}
= {⟨M⟩ : L(M) ∈ P} = LP
Then we need to show that there is a recognizable language L1 ∈ P and a recognizable language L2 ∈/P. TakeL1 =Σ∗;itisthecasethatS⊆Σ∗,soΣ∗ ∈P. TakeL2 =∅;itisthecasethat S ̸⊆ ∅, so ∅ ∈/ P. Thus, we can conclude by Rice’s theorem that LLIKES-ZEROES is undecidable.
3. Which of the following implies P = NP?
A. If there exists a language L that is decidable and verifiable.
B. If there exists a language L that is both efficiently decidable and efficiently verifiable.
C. If there exists a language L that is NP-Complete and efficiently decidable. D. If there exists a language L that is undecidable and recognizable.
E. None of the other choices imply that P = NP.
Solution:P=NPifNP⊆P. LetA∈NP. ByNP-CompletenessofL,A≤p Lsothereisa polynomial time function f such that
a∈A ⇐⇒ f(a)∈L
If L has an efficient decider D, then we can efficiently decide A by returning D(f(a)). Thus A ∈ P and we have P = NP.
4. Which of the following is a valid choice for an RSA modulus?
E. None of the other choices are valid.
Solution: To be a valid RSA modulus, the modulus must be the product of two distinct primes, so that the extension of Fermat’s Little Theorem holds (a1+kφ(n) ≡ a (mod n)). Only 33 = 3 × 11 is the product of two distinct primes.
Other variants of this problem:
• {13, 6, 16, 45, None} – only 6 = 2 × 3 is the product of two distinct primes
• {36, 18, 23, 21, None} – only 21 = 3 × 7 is the product of two distinct primes • {70, 73, 75, 77, None} – only 77 = 7 × 11 is the product of two distinct primes • {48, 50, 51, 61, None} – only 21 = 3 × 17 is the product of two distinct primes
All/Some/No. All = A, Some = B, No = C.
5. If ∅ ≤T B then B is (always / sometimes / never) decidable.
6. Let L be a language in coNP. Then L is (always / sometimes / never) recognizable.
Solution: Sometimes.
Although ∅ is decidable and ∅ ≤T B, we cannot say that B would always be decidable. For instance, ∅ ≤T Σ∗ is true, but ∅ ≤T LACC is not since we know that LACC is undecidable, then this statement would be true sometimes.
Solution: Always.
L is in coNP, which means that L ∈ NP. Since an efficient verifier for L exists, we can construct a decider for L. By iterating through all possible certificates (see Homework 6 Problem 4), we can construct a program that runs in exponential time that will accept if its input is in L and reject otherwise – this program is a decider for L. Since L is decidable, L is decidable as well, meaning L is also recognizable.
7. Let φ be an exact 3CNF boolean formula with exactly 800 clauses. There is (always / sometimes / never) an assignment that satisfies exactly 700 of the clauses in φ.
Solution: Sometimes.
If all 800 clauses are exactly the same, then an assignment satisfies either no clauses or all 800, and there is no assignment that satisfies exactly 700.
On the other hand, consider φ defined as follows:
(xi,1 ∨ xi,2 ∨ xi,3). i=1
Clearly, the formula is an exact 3CNF Boolean formula with exactly 800 clauses. Furthermore, the truth value of the each clause is independent of all of the other clauses. An assignment which satisfies exactly 700 of the clauses can be easily constructed – let xi,1 = 1 for all i ≤ 700, and let all other variables be false. Then the first 700 clauses are satisfied, while the remaining 100 clauses are not.
8. Suppose P ̸= NP and let L be an NP-Complete language. Then L (always / sometimes / never) has a polynomial-time decider.
9. If A ≤p B, then it is (always / sometimes / never) true that A ≤T B.
Solution: Never.
Recall that if there exists an NP-Complete language which has a polynomial time decider for it, then it must be the case that P = NP. The contrapositive (and logical equivalent) of this statement is that if P ̸= NP then it must be the case that there does not exist any language that is NP-Complete and has a polynomial time decider.
Solution: Always.
Assume that we have two arbitrary languages A and B and A ≤p B. This means that there must exist a polynomial time computable function f such that for all w ∈ Σ∗, the following properties will hold:
• w∈A ⇐⇒ f(w)∈B • w ∈/ A ⇐ ⇒ f ( w ) ∈/ B
To show that A ≤T B we must show that if there exists a decider for B then there also exists a decider for A.
Assume that we have a decider DB for B.
We can construct a decider DA for A as follows:
DA on input w:
(a) Compute f(w)
(b) Run DB on f(w) and return same.
DA always halts. Step (a) always halts because it runs in polynomial time with respect to the input size as f is a polynomial time computable function. Step (b) always halts because it is running the decider DB and deciders always halt.
If w ∈ A, because of the properties of f described above we know that f(w) ∈ B. Hence, the de- cider for B, DB will accept f(w) making DA accept w correctly. If w ∈/ A we know that f(w) ∈/ B. Hence, DB will reject f(w) making DA reject w as it should.
Assuming that A ≤p B for two arbitrary languages allowed us to show that A ≤T B. Hence, if A≤p BthenitisalwaystruethatA≤T B.
10. Suppose B ∈ P and A ≤T B. Then, it is (always / sometimes / never) true that A ≤p B.
Solution: Sometimes.
IfA=B,thenA≤T B(adeciderforBisalsoadeciderforAwhenA=B)andA≤p B(since we can polynomial time reduce problem instances of A to problem instances of B by keeping them the same, using the function f(x) = x). Thus there are instances where A ≤T B and A ≤p B.
If you choose languages such that A decidable, but is not in P, and B is in P, then it is true that A ≤T B, since all decidable languages are Turing-reducible to each other, but it cannot be true thatA≤p B,becauseB∈P,sothiswouldimplythatA∈P.
(A more detailed solution is in Homework 7, problem 4d)
11. (All/Some/No)primenumberspsatisfy: ak(p−1) ≡1 (modp),foralla̸≡0 (modp)andallk∈N.
Solution: All.
Recall Fermat’s Little Theorem, which states that if p is a prime number, then for any integer a not divisible by p, ap−1 ≡ 1 (mod p). Then ak(p−1) ≡ (ap−1)k ≡ 1k ≡ 1 (mod p).
From the problem statement, we know a is not divisible by p because a ̸≡ 0 (mod p), and it’s true for any integer a since k ∈ N. Thus, all prime numbers p satisfy this.
True/False/Unknown. True = A, False = B, Unknown = C.
Determine whether each of the following statements is known to be true, known to be false, or not known to be true or false.
12. Let A and B be languages. Suppose A is NP-Hard and B is NP-Hard. Then it is always the case that A ≤p B.
Solution: False.
Given two NP-Hard languages, A and B, we cannot conclude whether or not A polytime reduces to B. For example, we can look at the case where A = LHALT and B = 3SAT. LHALT does not polytime reduce to 3SAT. Consider a proof by contradiction. Let’s assume that LHALT ≤p 3SAT. This must mean that LHALT ≤T 3SAT (as proved in Homework 7). Because 3SAT is decidable and LHALT ≤T 3SAT, LHALT must be decidable. We know that LHALT is not decidable, causing a contradiction. Therefore, our original assumption must be wrong, and it must not be the case that LHALT ≤p 3SAT.
13. There exists an efficient 376-approximation algorithm for the search version of Vertex-Cover.
Solution: True.
The Double-Cover algorithm presented in lecture is a 2-approximation of the search version of Vertex-Cover and a 2-approximation also serves as a 376-approximation. This is because by
running the Double-Cover algorithm, we are guaranteed to find a vertex cover that is no larger than 2 · OP T , which would therefore also be no larger than 376 · OP T .
LC-Non-HALT is decidable.
LC-Non-HALT = {⟨M, x, C⟩ : C is an integer, M is a Turing Machine, and M does not halt on input x within C steps}.
Solution: True.
We construct a decider for LC-Non-HALT as follows:
We now show that D is indeed a decider.
D(⟨M, x, C⟩)
1: RunM oninputxforC steps
2: if M halts within C steps then reject 3: else accept”
• Suppose that (⟨M,x,C⟩) ∈ LC-Non-HALT. Then by definition, M(x) does not halt within C steps, so D will accept.
• Suppose that (⟨M,x,C⟩) ∈/ LC-Non-HALT. Then by definition, M(x) does halt within C steps, so D will reject.
In addition, D will run M for at most C steps, and then either accept or reject, meaning that D will never loop.
15. 3-SAT ≤p Vertex-Cover.
Solution: Unknown.
Vertex-Cover is an NP-Complete language, and the complement of an NP-Complete language is coNP-Complete, which by definition is in coNP. If this polynomial-time reduction is true, then it would mean that a coNP-Complete language is NP-Hard. However, it’s not known whether there exists a coNP language that is NP-Hard.
If we find a language L that is in coNP and is NP-Hard, this would allow us to prove that NP = coNP (which is unknown) by the following argument. Since L is NP-Hard, every language in NP could be mapping reduced to L in polynomial time. This would show that NP ⊆ coNP by the following: take an arbitrary language A ∈ NP. We know that A ≤p L, so there exists a polynomial time functionf suchthatx∈A↔f(x)∈L.RecallthatL∈coNP,whichmeansthatgivenx∈A,we could create a coNP algorithm for A by simply computing f(x) and running the coNP algorithm for L on f(x). This would prove that NP ⊆ coNP. We could next use this to prove that coNP ⊆ NP. Consider an arbitrary language B ∈ coNP. We know that B ∈ NP, and with NP ⊆ coNP showed earlier, that means B ∈ coNP. Thus, B ∈ NP, which proves that coNP ⊆ NP. Since the existence of an NP-Hard language in coNP allowed us to prove that NP ⊆ coNP and that coNP ⊆ NP, it would allow us to conclude that NP = coNP. However, since NP is not known to be closed under complement, the answer is unknown.
16. Let L be a language in P and let L′ be an arbitrary language for which |L′| > 0 and |L′| > 0. Then it is always the case that L ≤p L′.
Solution: True.
We will prove that L ≤p L′ by showing that there exists a polynomial-time computable function f suchthatx∈L↔f(x)∈L′.
First, we know that there exists an efficient decider for L because L ∈ P. We will call this decider D. We also know that there exists some a such that a ∈ L′ because |L′| > 0. Similarly, we know that there exists some b such that b ∈/ L′ because |L′| > 0.
We will construct the following function f :
Now we will show that x ∈ L ↔ f(x) ∈ L′.
Ifx∈L,thenDwillacceptx,sof willreturna,whichisinL′.So,ifx∈L,thenf(x)∈L′.
1: Run D(x)
2: if D accepts x then return a 3: else return b
Ifx∈/L,thenDwillrejectx,sof willreturnb,whichisnotinL′.So,ifx∈/L,thenf(x)∈/L′. We know that f is polynomial-time computable because D runs in polynomial time by definition.
17. Define the language LGCD = {(a, b, g) : a, b, g ∈ N and gcd(a, b) = g}. LGCD is NP-Complete.
Solution: Unknown.
Note that we know LGCD ∈ P, and therefore LGCD ∈ NP. We know LGCD ∈ P by the following algorithm which relies on the fact that the Euclidean Algorithm is efficient.
We say that a language L is NP-Complete if L ∈ NP and if L is NP-Hard, that is, for any non-trivial language A ∈ NP, A ≤p L. We know that LGCD ∈ NP but it is unknown if LGCD is NP-Hard.
If P ̸= NP, then we know that there must not exist any NP-Complete language which is in P (see section notes 11 3.1 diagram). Hence, as we know that LGCD ∈ P, LGCD would not be NP-Complete if P ̸= NP.
On the other hand if P = NP, then LGCD would be NP-Complete. We already know LGCD ∈ NP. LGCD must also be NP-Hard. We can prove this by showing that an NP-Complete language is polynomial time mapping reducible to it: let’s say SAT ≤p LGCD.
Recall that if P = NP this must mean that all NP-Complete languages are also in P. This is because all NP-Complete languages are in NP and thus they would also be in P if P = NP. Thus we would have an efficient deciders for all NP-Complete languages including SAT.
We can construct a function f which efficiently maps yes instances of SAT to yes instances of LGCD and no instances of SAT to no instances of LGCD as follows:
We have shown LGCD ∈ P. Therefore if LGCD is NP-Complete then P = NP. It is unknown if P = NP, and thus unknown if LGCD is NP-Complete.
D = “on input (a,b,g):
1: Run the Euclidean Algorithm on (a, b) 2: if the result = g then accept
3: else reject
1: Run D(φ)
2: if D accepts x then return (14, 15, 1) 3: elsereturn(14,15,0)
18. The bitwise complement of a binary string is a string with ones in place of the original string’s zeroes and zeroes in place of the original string’s ones. For example, bitwise-complement(10001) = 01110.
Let L ⊆ {0, 1}∗ . Define flip(L) = {bitwise-complement(x) : x ∈ L}. In other words, bitwise-complement(x) ∈ flip(L) if and only if x ∈ L.
If L ∈ NP, then it is always true that flip(L) ∈ NP.
Solution: True.
Since L ∈ NP, we can build an efficient verifier for flip(L) by just taking the bitwise complement of our input then using the efficient verifier for L. Formally, assume L ∈ NP and let V be an efficient verifier for L. Define
Note that W is efficient: We can compute the bitwise complement of x in O(|x|) time by traversing the bits of x and flipping each one. We then make a single call to V , which by assumption is also efficient.
As well, W is a verifier for flip(L):
• If x ∈ flip(L), then x = bitwise-complement(w) for some w ∈ L. In fact, since flipping a bit
twice just gives us back the original bit, this implies
y = bitwise-complement(x) = bitwise-complement(bitwise-complement(w)) = w,
so y ∈ L. Since V is a verifier for L, there is then a certificate c so that V (y, c) accepts, hence some certificate c where W (x, c) accepts.
• If x ∈/ flip(L), then for any w ∈ L, we know x ̸= bitwise-complement(w). In particular, since x = bitwise-complement(y), we know y ∈/ L. Since V is a verifier for L, V (y, c) will reject for every certificate c, thus W (x, c) will also reject for every certificate c.
Therefore W is indeed an efficient verifier for flip(L), so flip(L) ∈ NP.
W = “on input (x, c):
1: y ← bitwise-complement(x)
2: Run V on input (y, c) and output same. =0
19. Let LLIS = {(S,k) : S is a sequence of numbers, and S has a strictly increasing subsequence of size greater than k}. LLIS is NP-Complete.
Solution: Unknown.
We can define a polynomial-time decider for this language. Recall the Longest Increasing Subse- quence Dynamic Programming algorithm from Lecture 5. This algorithm operates on a sequence S with length n, memoizing to a memo with dimensions 1 × n. This is a bottom-up implementation of that algorithm:
LLIS = “On input S, k:
1. 2. 3. 4. 5. 6. 7. 8.
We define a table M with dimensions 1xn Forifrom1ton:
For j from 1 to i − 1:
If S[i] > S[j] and M[j] ≥ M[i]: M[i] ← M[j] + 1
If M[n − 1] > k, ACCEPT. REJECT.”
This algorithm runs the Longest Increasing Subsequence DP algorithm to find the longest increas- ing subsequence of S. If S, k is in the language then there exists some such subsequence with length
greater than k; the decider will return true once it finds the last element in such a subsequence. If S, k is not in the language, there cannot exist an increasing subsequence with length greater than k; the longest increasing subsequence will have length at most k and so the decider will reject. This decider runs in polynom
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com