EECS 376: Foundations of Computer Science Winter 2021, University of Michigan,
EECS 376 Final Exam
Multiple Choice.
Copyright By PowCoder代写 加微信 powcoder
Select the most appropriate answer. 1. Version 1:
What can we deduce from A ≤p B?
A. IfAisinPthenBisinP.
B. If B is NP-complete, then A is NP-complete. C. IfBisinP,thenAisinNP.
D. IfBisnotinP,thenAisnotinP.
Version 2:
What can we deduce from A ≤p B?
A. IfBisinP,thenAisinP.
B. BothAandBareinPorneitherAnorBisinP. C. If B is NP-complete, then A is NP-hard.
D. If A is NP-hard, then B is NP-hard.
Version 3:
What can we deduce from A ≤p B?
A. If B is NP-Hard, then A is NP-Hard.
B. IfAisinP,thenBisinNP.
C. If A is NP-complete, then B is NP-hard. D. IfBisinP,thenAisNP-hard.
2. Version 1:
Which statements, if true, would imply P = NP?
A. Every NP-complete language is in NP
B. Some NP-complete language is NP-Hard
C. There exists a language in NP but that is not in P. D. Vertex-Cover is in P
Version 2:
Which statements, if true, would imply P = NP? A. Every NP-complete language is NP-hard B. 3SAT can be solved in O(n6) time.
C. Every language in P is in NP.
D. Some NP-hard language is in P
Version 3:
Which statements, if true, would imply P = NP?
A. Leven = {⟨n⟩ | n is even} is NP-complete.
B. An NP-hard language is NP-complete
C. There exists an NP-hard language that is NP-complete D. Every NP-complete language is NP-hard.
3. Version 1:
Suppose A, B ⊆ {0, 1}∗ are languages and f : {0, 1}∗ → {0, 1}∗ is the function used to prove A ≤p B.
A. f(x) must be computable in polynomial time
B. f is a bijection
C. f is onto (surjective) D. Ifx∈A,thenf(x)∈B E. Ifx∈/A,thenf(x)∈/B
Version 2:
Suppose A, B ⊆ {0, 1}∗ are languages and f : {0, 1}∗ → {0, 1}∗ is the function used to prove A ≤p B. A. f is one-to-one (injective)
B. x∈Aifandonlyiff(x)∈B
C. f(x) is computable in O(|x|) time.
D. f(x) must be computable in polynomial time
E. Forallx,f(x)∈B. Version 3:
Suppose A, B ⊆ {0, 1}∗ are languages and f : {0, 1}∗ → {0, 1}∗ is the function used to prove A ≤p B. A. f is onto (surjective)
B. x∈Bifandonlyiff(x)∈A
C. f(x) is computable in O(|x|c) time for some non-negative, integer, constant c. D. If |A| is infinite, then |B| is also infinite
E. Iff(x)∈Bthenx∈A.
4. Version 1:
Suppose a language L is in P and L1 is some other language. Which of the following must be true? Select all that apply.
C. IfL∩L1 ∈P,thenL1 ∈P D. IfL≤p L1,thenL1 ∈P
Version 2:
Suppose a language L is in P and L1 is some other language. Which of the following must be true? Select all that apply.
A. If L1 is a nontrivial language (that is, L1 ̸= ∅ and L1 ̸= Σ∗), then L ≤p L1 B. IfL≤p L1,thenL1 ∈P
C. IfL≤p L1,thenL1 ∈NP
Version 3:
Suppose a language L is in P and L1 is some other language. Which of the following must be true? Select all that apply.
A. IfL1 ≤p L,thenL1 ∈P
B. IfLisNP-Hard,thenP=NP C. IfL≤p L1,thenL1 ∈P
5. Version 1:
Consider the following algorithm which takes an undirected graph G:
while G has edges:
select an arbitrary edge e = (u,v)
add the vertices u,v to a set C
remove all edges incident to either u or v from G
select another edge (if one exists) and remove it from G
The set C is a 2-approximation for the Vertex-Cover search problem. (⃝ True / ⃝ False / ⃝ Unknown) Version 2:
Consider the following algorithm which takes an undirected graph G:
while G has edges:
select an arbitrary edge e = (u,v)
add the vertices u,v to a set C
remove all edges incident to either u or v from G
select a vertex w (if one exists)
add w to C
remove all edges incident to the vertex
The set C is a 3-approximation for the Vertex-Cover search problem. (⃝ True / ⃝ False / ⃝ Unknown) Version 3:
Let S be the set of graphs which satisfy the following conditions:
• Every vertex in the graph is colored either maize or blue.
• Every edge in the graph has one vertex colored maize, and its other vertex colored blue. • Every vertex has at least one incident edge.
• The number of maize-colored vertices is exactly the number of blue-colored vertices.
Consider the following algorithm which takes as input a graph G from S: pick either maize or blue uniformly at random
add vertices of the color selected to the set C
The set C is a 2-approximation for the Vertex-Cover search problem on G ∈ S. (⃝ True / ⃝ False / ⃝ Unknown)
6. Version 1:
Suppose P ̸= NP. Which of the following are true?
A. NP-complete languages cannot be decided efficiently.
B. Every language in the class NP is also NP-hard.
C. There exists a language that is NP-hard and can be decided efficiently. D. Lodd = {n : n is odd} is not NP-complete.
Version 2:
Suppose P ̸= NP. Which of the following are true? A. Vertex-Cover can be decided in O(n7) time. B. If L is NP-hard, then L ̸∈ P.
C. IfLisNP-hard,thenLisnotinP.
D. Lodd = {n : n is odd} is NP-complete. Page 4
Version 3:
Suppose P ̸= NP. Which of the following are true? A. Vertex-Cover can be decided in O(n7) time. B. IfL∈P,thenL̸∈NP.
C. IfL∈P,thenLisnotNP-hard.
D. Clique is not in P.
7. Version 1:
On an exam scored out of 100 points, the average student score was 70 points. Using Reverse Markov’s Inequality, what is the largest possible fraction of students that could have scored less than or equal to 50 points?
Version 2:
On an exam scored out of 100 points, the average student score was 90 points. Using Reverse Markov’s Inequality, what is the largest possible fraction of students that could have scored less than or equal to 60 points?
A. 15 B. 14 C. 49 D. 23 E. 34
Version 3:
On an exam scored out of 100 points, the average student score was 80 points. Using Reverse Markov’s Inequality, what is the largest possible fraction of students that could have scored less than or equal to 40 points??
A. 14 B. 13 C. 12 D. 23 E. 34
8. Version 1:
Suppose a COVID-19 test always comes back positive if a person has COVID-19 and comes back negative with probability ≥ 0.6 if the person does not. If a person tests positive, what is the minimum number of additional tests they need to take to know that they have COVID-19 with at least 98% confidence? Assume that the results of each test is independent of all the others.
A. 6 B. 4 C. 2 D. 3
Version 2:
Suppose a COVID-19 test always comes back positive if a person has COVID-19 and comes back negative with probability ≥ 0.8 if the person does not. If a person tests positive, what is the minimum number of additional tests they need to take to know that they have COVID-19 with at least 98% confidence? Assume that the results of each test is independent of all the others.
A. 6 B. 4 C. 2 D. 3 E. 5
Version 3:
Suppose a COVID-19 test always comes back positive if a person has COVID-19 and comes back negative with probability ≥ 0.5 if the person does not. If a person tests positive, what is the minimum number of additional tests they need to take to know that they have COVID-19 with at least 98% confidence? Assume that the results of each test is independent of all the others.
A. 6 B. 4 C. 2 D. 3 E. 5
9. Version 1:
Which of the following parameters are valid for the RSA cryptosystem?
A. n=33,e=7,d=3 B. n=33,e=7,d=24 C. n=27,e=7,d=7 D. n=27,e=3,d=11
Version 2:
Which of the following parameters are valid for the RSA cryptosystem? A. n=39,e=5,d=5
B. n=39,e=3,d=25 C. n=44,e=7,d=13 D. n=44,e=2,d=11
Version 3:
Which of the following parameters are valid for the RSA cryptosystem? A. n=51,e=5,d=13
B. n=51,e=3,d=40 C. n=27,e=13,d=5 D. n=27,e=11,d=5
10. Version 1:
Suppose that Alice and Bob want to establish a shared private key via Diffie-Hellman key exchange using prime p = 19 and generator g = 15. Bob chooses his private key to be b = 8 and receives the number 11 from Alice. What is the shared key?
A. 5 B. 7 C. 11 D. 12 E. 20
Version 2:
Suppose that Alice and Bob want to establish a shared private key via Diffie-Hellman key exchange using prime p = 17 and generator g = 3. Bob chooses his private key to be b = 8 and receives the number 11 from Alice. What is the shared key?
A. 1 B. 7 C. 11 D. 16 E. 20
Version 3:
Suppose that Alice and Bob want to establish a shared private key via Diffie-Hellman key exchange using prime p = 13 and generator g = 2. Bob chooses his private key to be b = 8 and receives the number 11 from Alice. What is the shared key?
A. 1 B. 3 C. 9 D. 10 E. 12
11. Version 1:
Suppose there are algorithms A and B where TA(n) is the time for algorithm A on inputs of size n, and TB(n) is the time for algorithm B on inputs of size n. Suppose TA satisfies TA(n) = 4TA(n2 ) + TB(n), and suppose TB(n) is O(n2) but not O(1). Then TA(n) is
A. O(n2) but not O(n) B. O(n3) but not O(n2) C. O(n4) but not O(n3) D. None are correct
Version 2:
Suppose there are algorithms A and B where TA(n) is the time for algorithm A on inputs of size n, and TB(n) is the time for algorithm B on inputs of size n. Suppose TA satisfies TA(n) = 8TA(n2 ) + TB(n), and suppose TB(n) is O(n2) but not O(n). Then TA(n) is
A. O(n9) but not O(n6) B. O(n4) but not O(n3) C. O(n2) but not O(n1.5) D. None are correct
Version 3:
Suppose there are algorithms A and B where TA(n) is the time for algorithm A on inputs of size n, and TB(n) is the time for algorithm B on inputs of size n. Suppose TA satisfies TA(n) = 2TA(n2 ) + TB(n), and suppose TB(n) is O(n3) but not O(n2). Then TA(n) is
A. O(n4) but not O(n3)
B. O(n5) but not O(n4) C. O(n8) but not O(n5) D. None are correct
12. Version 1:
Which of the following languages can be shown to be undecidable by a direct application of Rice’s Theorem? (Select all that apply)
A. L={⟨M⟩:|L(M)|=376}
B. L = {⟨M⟩ | M halts in 376 steps for the input ’475’ but not for the input ’477’} C. L = {⟨M⟩ | |⟨M⟩| is 376 bytes}
D. L = {⟨M⟩ | M does not accept the input 376}
E. L={⟨M⟩|M isavalidC++program}
Version 2:
Which of the following languages can be shown to be undecidable by a direct application of Rice’s Theorem? (Select all that apply)
A. L = {(⟨M⟩,x) | M(x) halts in 10 steps}
B. L={⟨M⟩|L(M)=∅}
C. L={x|xiseven}
D. L = {⟨M⟩ | M accepts an even number of inputs} E. L = {⟨M⟩ | M accepts the input ’376’ in 101 steps}
Version 3:
Which of the following languages can be shown to be undecidable by a direct application of Rice’s Theorem? (Select all that apply)
A. L = {⟨M⟩ : |L(M)| divides 376}
B. L={⟨M⟩|L(M)=∅}
C. L = {⟨M⟩ | M does not accept the input 376}
D. L = {⟨M⟩ : |L(M)| is prime}
E. L = {⟨M⟩ | M accepts an even number of inputs}
13. Version 1:
What is the language of the following FSA?
A. aab∗ B. ab∗ab∗ C. ab∗a
D. None of the above
Version 2:
What is the language of the following FSA?
B. ab(ab)∗
C. bab(ab)∗
D. None of the above
Version 3:
What is the language of the following FSA?
B. ab∗(ab)∗
D. None of the above
14. Version 1:
SAT is efficiently decidable. (⃝ True / ⃝ False / ⃝ Unknown)
Version 2:
Clique is efficiently decidable. (⃝ True / ⃝ False / ⃝ Unknown) Version 3:
Vertex-Cover is efficiently decidable. (⃝ True / ⃝ False / ⃝ Unknown)
15. Version 1:
Let n = p · q for distinct primes p and q both greater than 10. Then φ(n) is (⃝ always / ⃝ sometimes / ⃝ never) divisible by 4.
Version 2:
Let n = p·q for distinct primes p and q. Then n·φ(n) is (⃝ always / ⃝ sometimes / ⃝ never) divisible by 4.
Version 3:
Let n = p·q for distinct primes p and q both greater than 10. Then φ(n)2 is (⃝ always / ⃝ sometimes / ⃝ never) divisible by 16.
16. Version 1:
Which of the following sets is countable (select all that apply)?
B. A subset of the power set of {0, 1, 3}
C. The set of languages over the alphabet {0, 1, 3}
D. The set of all simple graphs G = (V, E) (where |V | is finite) which have an MST
Version 2:
Which of the following sets is countable (select all that apply)? A. P
B. A subset of the power set of {0,1,a,b,c}
C. The set of languages over the alphabet {0, 1, a, b, c} D. The set of all undecidable languages
Version 3:
Which of the following sets is countable (select all that apply)? A. NP
B. The set of all simple complete graphs G = (V, E) (where |V | is finite)
C. Asubsetofthepowersetof{g,h,i,j}
D. The set of all simple graphs G = (V, E) (where |V | is finite) which have a vertex cover E. P
17. Version 1:
Suppose A and B are maximization problems, A ≤p B and B ≤p A, and there is an efficient 0.9 approximation algorithm for A. Then there is (⃝ always / ⃝ sometimes / ⃝ never) an efficient 0.9 approximation algorithm for B.
Version 2:
Suppose A and B are maximization problems, A ≤p B and B ≤p A, and there is an efficient 0.7 approximation algorithm for A. Then there is (⃝ always / ⃝ sometimes / ⃝ never) an efficient 0.49 approximation algorithm for B.
Version 3:
Suppose A and B are minimization problems, A ≤p B and B ≤p A, and there is an efficient 2- approximation algorithm for A. Then there is (⃝ always / ⃝ sometimes / ⃝ never) an efficient 2-approximation algorithm for B.
18. Version 1:
Forthisquestion,assumeP̸=NP. SupposeA≤T BandA≤T C.ThenB≤T C.(⃝always/⃝ sometimes / ⃝ never)
Version 2:
Forthisquestion,assumeP̸=NP. SupposeA≤p BandA≤p C.ThenB≤p C.(⃝always/⃝ sometimes / ⃝ never)
Version 3:
Forthisquestion,assumeP̸=NP. SupposeA≤T BandB≤p C.ThenA≤p C.(⃝always/⃝ sometimes / ⃝ never)
Written Answer.
1. Version 1:
Prove that L∅ = {⟨M⟩ : L(M) = ∅} is NP-Hard by a reduction from 3SAT. Explain why L∅ is not NP-Complete.
Version 2:
Prove that LΣ∗ = {⟨M⟩ : L(M) = Σ∗} is NP-Hard by a reduction from VertexCover. Explain why LΣ∗ is not NP-Complete.
Version 3:
Prove that Lε = {⟨M⟩ : M accepts ε} is NP-Hard by a reduction from HamiltonianCycle. Explain why Lε is not NP-Complete.
2. Version 1:
We are organizing a field trip to the Detroit Zoo for all n EECS376 students. Transportation will be provided by t vehicles of various sizes. Vehicle j can carry cj passengers, where j cj ≥ n. Is it possible to assign all students to vehicles so that within each vehicle, each pair of students knows each other? As part of the input, you are given a graph G = (V,E) where V is the set of students and u, v ∈ E if u and v already know each other. Express this problem as a language Field-Trip. Prove that Field-Trip is NP-complete.
Version 2:
We are organizing a field trip to the Detroit Zoo for all n EECS376 students. Transportation will be provided by t vehicles of various sizes. Vehicle j can carry cj passengers, where j cj ≥ n. Is it possible to assign all students to vehicles so that within each vehicle, each pair of students did not already know each other? As part of the input, you are given a graph G = (V,E) where V is the set of students and u, v ∈ E if u and v already know each other. Express this problem as a language Field-Trip. Prove that Field-Trip is NP-complete.
Version 3:
Only 2 versions for this problem.
3. Version 1:
376Poker is a game, each round of which involves rolling a fair 6-sided die and flipping a fair coin. (The rules of 376Poker are not relevant to this question.) Your problem is that you have neither the 6-sided die nor the coin, just a fair 20-sided die.
(a) Explain how you can simulate a round of this game using the 20-sided die. You should be simulating both the 6-sided die and the coin.
(b) Let X be the number of rolls of the 20-sided die used to the simulate a round of 376Poker. What is the expected value of X?
Version 2:
376Poker is a game, each round of which involves rolling a 6-sided die and flipping a coin. (The rules of 376Poker are not relevant to this question.) Your problem is that you have neither a 6-sided die nor a coin, just a 10-sided die.
(a) Explain how you can simulate a round of this game using the 10-sided die. You should be simulating both the 6-sided die and the coin.
(b) Let X be the number of rolls of the 10-sided die used to the simulate a round of 376Poker. What is the expected value of X?
Version 3:
376Poker is a game, each round of which involves rolling a 10-sided die and flipping a coin. (The rules of 376Poker are not relevant to this question.) Your problem is that you have neither a 10-sided die nor a coin, just a 12-sided die.
(a) Explain how you can simulate a round of this game using the 12-sided die. You should be simulating both the 10-sided die and the coin.
(b) Let X be the number of rolls of the 12-sided die used to the simulate a round of 376Poker. What is the expected value of X?
Version 1: Version 2: Version 3:
4. Version 1:
Let L23 = {⟨M⟩ : |L(M)| = 2 or |L(M)| = 3}. That is L23 contains all Turing machines whose languages contain exactly two or three strings. Prove L23 is undecidable using a Turing reduction from LACC (you may not assume any other language is undecidable for purposes of doing this proof).
Version 2:
Let LMI = {⟨M⟩ : L(M) = {“UM”} or L(M) = {“MSU”}}. That is LMI contains all Turing machines whose language contains ”UM” and no other string, or whose language contains ”MSU” and no other string. Prove LMI is undecidable using a Turing reduction from LHALT (you may not assume any other language is undecidable for purposes of doing this proof).
Version 3:
Let LODDM = {⟨M⟩ : |L(M)| = n where n is finite and odd.} That is LODDM contains all Turing machines whose languages have a finite and odd number of elements. Prove LODDM is undecidable using a Turing reduction from LHALT (you may not assume any other language is undecidable for purposes of doing this proof).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com