EECS 376: Foundations of Computer Science Winter 2021, University of Michigan,
EECS 376 Practice Final Exam
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
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
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.
4. Which of the following is a valid choice for an RSA modulus? A. 33
E. None of the other choices are valid.
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.
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 φ.
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.
10. Suppose B ∈ P and A ≤T B. Then, it is (always / sometimes / never) true that A ≤p B.
11. (All/Some/No)primenumberspsatisfy: ak(p−1) ≡1 (modp),foralla̸≡0 (modp)andallk∈N.
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.
13. There exists an efficient 376-approximation algorithm for the search version of Vertex-Cover.
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}.
LC-Non-HALT is decidable.
15. 3-SAT ≤p Vertex-Cover.
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′.
17. Define the language LGCD = {(a, b, g) : a, b, g ∈ N and gcd(a, b) = g}. LGCD is NP-Complete.
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.
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.
20. If SAT ̸∈ P, then there is no efficient non-quantum algorithm for the discrete logarithm problem.
21. Suppose NP ⊆ P. Then P = NP.
22. Let L be a language and let A = L ∩ L. Then A is polynomial-time mapping reducible to A.
23. Consider the language LPOWER where LPOWER = {(x, y, z) : x, y, z are natural numbers such that xy = z}. Now consider the following program A.
A = “On input (x, y, z): 1. value := 1
2. Iterate y times:
value := value · x
3. If value is equal to z, ACCEPT 4. Otherwise, REJECT”
Our construction of A demonstrates that LPOWER ∈ P.
24. If P ̸= NP, then NP-Complete ∩ P = ∅.
25. Consider the language LVC-376-281 where
LVC-376-281 = {G : G is a graph that has 376 vertices and a vertex cover of size 281}.
Then LVC-376-281 is in P.
26. If P = NP, then TSP is NP-Hard. 27. Define the language
L is in P.
L={(c,m,n,e):c,m,n,e∈Nandc=md modn,whered≡e−1
Written Answer
28. Professor Volkovich and Professor Kamil would like to share exam solutions using an encryption scheme that requires a single shared key. They decide to use the Diffie-Hellman protocol with prime modulus p = 23 and generator g = 14 to establish a shared key between them. Prof. Volkovich randomly chooses a = 3 and Prof. Kamil randomly chooses b = 13.
[g,a,b can vary – see the variants below]
(a) Compute the values they send to each other.
(b) Compute the resulting shared key.
You must show all your work, and all computations must use an efficient (i.e. polynomial-time) algorithm. (You do not have to show every detail of an individual multiplication or division, but as per the rules of this exam, you are prohibited from using a calculator.)
• g=14,a=3,b=13 • g=15,a=2,b=19 • g=17,a=5,b=7 • g=19,a=3,b=11 • g=21,a=5,b=13
29. The city of has decided to introduce a congestion toll to raise money for pandemic relief. The city’s neighborhoods are to be divided into 3 [variants: 4, 5] districts, with a toll charged for traveling between two different districts. To maximize the money raised for relief, the city wants to organize the districts so that the number of connections between different districts is maximized; that way, tolls are charged at the largest number of locations.
Given a set of n neighborhoods and m connections between pairs of neighborhoods, define Max-Tolls to be the problem of dividing the neighborhoods into 3 [variants: 4, 5] disjoint groups such that the number of connections between neighborhoods in different groups is maximized.
(a) Design an efficient, randomized algorithm that achieves an α-approximation in expectation for Max-Tolls, where α is a constant strictly greater than 1/2.
(b) What is the ratio α achieved by the algorithm? Analyze the algorithm to show that it achieves this ratio in expectation.
30. You are starting a new job as a delivery driver for WindowWalk in , and they have loaned you an electric car for making deliveries. Each night, you need to charge the car so that it has sufficient power to complete a delivery route, but you don’t know the exact route until the next morning. However, you do know the following:
• The route does not visit the same location more than once, except that it begins and ends at your home. We refer to such a route as a delivery route from your home.
• If your route takes you past a charging station, you can also charge your car on the way.
Your goal is to charge your car each night to a sufficient level so that it can make it through any
delivery route that does not pass a charging station.
Formally, you model the problem as an unweighted, undirected graph G, with vertices as locations in
the city and edges as connections between the locations. Given a start vertex s and a set of charging
stations A, you want to find the maximal delivery route (the route with the highest number of edges) from s that does not go through any of the vertices in A. The decision problem is as follows:
Delivery-Route = {(G = (V, E), A, s, k) : G has a delivery route from s of length exactly k that does not go through any vertex in A ⊆ V }
Given an efficient decider for Delivery-Route, design and analyze an efficient algorithm that given (G, A, s), finds the actual ordered sequence of edges that comprise a delivery route of maximal length from s that does not go through any vertex in A.
31. The cities of and Detroit are setting up COVID testing centers along routes between the two cities to ensure safe travels during the holidays. The goal is that for every possible route between and Detroit, there is a testing center along that route, and to minimize the number of testing centers required.
Formally, we model this problem as an unweighted, undirected graph G, with edges as road segments and vertices as road intersections/interchanges. Given a starting vertex s and an end vertex t, we want to find a minimal set of edges A such that every path between s and t goes through at least one edge in A. The decision problem is as follows:
Testing-Centers = {(G = (V, E), s, t, k) : There is a set of at most k edges A ⊆ E such that every path from s to t goes through at least one edge in A}
Given an efficient decider for Testing-Centers, design and analyze an efficient algorithm that given (G, s, t), finds an actual minimal set of edges where testing centers can be placed to ensure there is a center along every path between s and t.
32. We define the following language:
ConstrainedClique = {⟨G = (V, E), k, v⟩ : G has a clique of size (at least) k that includes vertex v} Prove that ConstrainedClique is NP-Complete.
33. We define the following language:
ConstrainedVertex-Cover={⟨G=(V,E),k,u,v⟩: u̸=v,andGhasavertexcoverofsize(atmost)k
that includes vertices u and v} Prove that ConstrainedVertex-Cover is NP-Complete.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com