EECS 376: Foundations of Computer Science Winter 2021, University of Michigan,
EECS 376 Final SOLUTIONS
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. If B is in P, then A is in NP.
D. IfBisnotinP,thenAisnotinP.
Solution: (C)
(A)ConsiderB=LHALT,andanyA∈P. SinceAisinP,thenA≤p LforanylanguageL other than L = Σ∗ and L = ∅, so A ≤p B. A is in P, but B is undecidable so it can’t be in P.
(B) Consider A = ∅, and any NP-complete language B. Since B is NP-complete, then ∀L ∈ NP =⇒ L ≤p B, so A ≤p B. B is NP-complete, however A can never be NP-Complete (even if P = NP).
(C) Since A ≤p B, then exists a polynomial time function f such that ∀x ∈ A ↔ f(x) ∈ B. Let B be any language in P, then there exists a efficient decider for B. So you can construct an efficient decider for A on input x by computing f(x) and running B’s decider on f(x). Therefore, A is in P, so A must also be in NP.
(D)ConsiderB=LHALT,andanyA∈P. SinceAisinP,thenA≤p LforanylanguageL otherthanL=Σ∗ andL=∅,soA≤p B. BisnotinPasitisundecidable,howeverAis in P.
Version 2:
What can we deduce from A ≤p B?
A. If B is in P, then A is in P.
B. BothAandBareinPorneitherAnorBisinP.
C. If B is NP-complete, then A is NP-hard. D. If A is NP-hard, then B is NP-hard.
Solution: (A), (D)
(A) Since A ≤p B, then exists a polynomial time function f such that ∀x ∈ A ↔ f(x) ∈ B. Let B be any language in P, then there exists a efficient decider for B. So you can construct an efficient decider for A on input x by computing f(x) and running B’s decider on f(x). Therefore, A is in P.
(B)ConsiderB=LHALT,andanyA∈P. SinceAisinP,thenA≤p LforanylanguageL otherthanL=Σ∗ andL=∅,soA≤p B. Itisnotthecasethatbothorneitherofthe languages are in P as A is in P, but B is undecidable so it can’t be in P.
(C) Consider A = ∅, and any NP-complete language B. Since B is NP-complete, then ∀L ∈ NP =⇒ L ≤p B, so A ≤p B. B is NP-complete, however A can never be NP-Hard (even if P = NP).
(D)LetAbeanyNP-Hardlanguage,then∀L∈NP =⇒ L≤p A. SinceA≤p B,thenby transitivity ∀L ∈ NP =⇒ L ≤p B, so 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.
Solution: (C)
(A) Consider A = ∅, and any NP-Hard language B Since B is NP-Hard, then ∀L ∈ NP =⇒
L ≤p B, so A ≤p B. B is NP-Hard, however A can never be NP-Hard (even if P = NP).
(B)ConsiderB=LHALT,andanyA∈P. SinceAisinP,thenA≤p LforanylanguageL other than L = Σ∗ and L = ∅, so A ≤p B. A is in P, but B is undecidable so it can’t be in NP.
(C) Let A be any NP-complete language, then ∀L ∈ NP =⇒ L ≤p A. Since A ≤p B, then by transitivity ∀L ∈ NP =⇒ L ≤p B, so B is NP-Hard.
(D) ConsiderA=Σ∗,andanyB∈P. SinceAisinP,thenA≤p LforanylanguageLother thanL=Σ∗ andL=∅,soA≤p B. BisinP,butAcanneverbeNP-Hard(evenif P = NP).
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
Solution: (D)
(A) By definition of NP-Complete, NP-Complete languages are in NP.
(B) By definition of NP-Complete, NP-Complete languages are NP-Hard. (C) This would imply P ̸= NP.
(D) Vertex-Cover is known to be NP-Complete, so if it is in P, then P = NP
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
Solution: (B, D)
(A) By definition of NP-Complete, NP-Complete languages are NP-Hard.
(B) This would imply that 3SAT is in P, and since it is NP-Complete, P = NP. (C) P ⊆ NP is a known fact.
(D) By definition of NP-Hard problems, this would imply P = NP
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.
Solution: (A)
(A) Leven is efficiently decidable (by checking the last bit of n), so it is in P. If it is also NP-
Complete, then P = NP.
(B) By definition of NP-Complete, NP-Complete languages are NP-Hard. For example, 3SAT is
an NP-Hard language that is also NP-Complete.
(C) This would imply P ̸= NP.
(D) By definition of NP-Complete, NP-Complete languages are 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. If x∈A, then f(x)∈B E. Ifx∈/A,thenf(x)∈/B
Solution: (A, D, E)
(A) By definition of a polynomial time mapping reduction, f(x) must be computable in polyno-
mial time.
(B) There is no requirement for each input of f to produce a unique output.
(C) There is no requirement for each output of f to be mapped to from the domain. (D) By definition of a polynomial time mapping reduction, x ∈ A ⇐⇒ f(x) ∈ B. (E) By definition of a polynomial time mapping reduction, x ∈/ A ⇐⇒ f(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∈A if and only if f(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.
Solution: (B,D)
(A) There is no requirement for each input of f to produce a unique output.
(B) By definition of a polynomial time mapping reduction, x ∈ A ⇐⇒ f(x) ∈ B.
(C) f(x) does not need to be strictly computable in linear time. It must only be computable in linear time, O(xd).
(D) Therefore, for any x ∈ A, f(x) ∈ B. Since f is polytime computable, that means that A ≤p B, but A is infinite in size, where as B is finite. Therefore this statement is false as shown by this counter example.
(E) Suppose A is the set of even numbers and B = {0}. Construct a function f which takes in an input x and returns a 0 if x is even and 1 if x is odd. Construct a function f which takes in an input x and returns a 0 if x is even. Therefore for every x ∈ A, f(x) = 0. Therefore, for any x ∈ A, f(x) ∈ B. Since f is polytime computable, that means that A ≤p B. If x is odd, then f(x) = 1 therefore f(x) ∈/ B. Thus this statement is false.
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. If f(x)∈B then x∈A.
Solution: (C,E)
(A) There is no requirement for each output of f to be mapped to from the domain.
(B) f(x) is a mapping between A ≤p B not B ≤p A. This statement would be true if f(x) was used to prove B ≤p A.
(C) By definition f(x) must be computable in polynomial time, thus it must have a at most a polynomial time complexity.
(D) Suppose A is the set of even numbers and B = {0}. Construct a function f which takes in an input x and returns a 0 if x is even. Therefore for every x ∈ A, f(x) = 0. Therefore, for any x ∈ A, f(x) ∈ B. Since f is polytime computable, that means that A ≤p B, but A is infinite in size, where as B is finite. Therefore this statement is false as shown by this counter example.
(E) By definition of a polynomial time mapping reduction, x ∈ A ⇐⇒ f(x) ∈ B.
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.
A. L ∈ NP B. L ∈ P
C. IfL∩L1 ∈P,thenL1 ∈P D. IfL≤p L1,thenL1 ∈P
(a) P⊆NP,sosinceL∈P,itfollowsthatL∈NP.
(b) We know P is closed under complement (we proved this in HW6Q4a).
(c) Counter example: Consider L = ∅ ∈ P and L1 = LHalt ̸∈ P. Then L∩L1 = ∅∩LHalt = ∅∈P,yetL1 ̸∈P.
(d) Counter example: Consider L = {0} ∈ P and L1 = LHalt ̸∈ P. Then, L ≤p L1 (we proved this in HW7Q1c). Yet, L1 ̸∈ 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
(a) We proved this in HW7Q1c.
(b) Counter example: Consider L = {0} ∈ P and L1 = LHalt ̸∈ P. Then, L ≤p L1 (we proved
this in HW7Q1c). Yet, L1 ̸∈ P.
(c) Counter example: Consider L = {0} ∈ P and L1 = LHalt ̸∈ NP. Then, L ≤p L1 (we proved this in HW7Q1c). Yet, L1 ̸∈ NP.
(d) We know P is closed under complement (we proved this in HW6Q4a). So L ∈ P, and P ⊆ NP, so it follows that L ∈ NP, too.
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. If L is NP-Hard, then P=NP
C. IfL≤p L1,thenL1 ∈P D. L ̸∈ P
(a) We proved this in HW7Q1d.
(b) Since L ∈ NP-Hard, we know that ∀A ∈ NP,A ≤p L. Then by HW7Q1d, we know that A∈P(becauseL∈P). Wehaveshownthat∀A∈NP,A∈P,soNP⊆P. Thispairedwith P ⊆ NP tells us that P = NP.
(c) Counter example: Consider L = {0} ∈ P and L1 = LHalt ̸∈ P. Then, L ≤p L1 (we proved this in HW7Q1c). Yet, L1 ̸∈ P.
(d) We know P is closed under complement (we proved this in HW6Q4a). So L ∈ 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)
Solution: Consider the following graph:
a1b c3d e4f2g
If the algorithm considers edges in the order prescribed on the above graph, C contains neither f nor g and is not a vertex cover.
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. (
Version 3:
Let S be the set of graphs which satisfy the following conditions:
True / ⃝ False / ⃝ Unknown)
Solution: Let k be the number of times vertices were added for an arbitrary edge were added to the C. We know that |C| ≤ 3k. Furthermore, opt(G) ≥ k, so 3 opt(G) ≥ 3k ≥ |C|.
• 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. ( ⃝ 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.
True / ⃝ False /
Solution: The minimum vertex cover of graphs in S is half the number of vertices. The algorithm described generates a vertex cover with size exactly half the number of vertices, so it solves the problem exactly and thus is also a 2-approximation for the search problem.
(a) P ̸= NP implies that no NP-complete language can be decided efficiently.
(b) If P ̸= NP, languages in P are not NP-hard.
(c) If P ̸= NP, there can be no NP-hard, language that can be decided in polynomial time
(efficiently).
(d) Lodd is in P. If P ̸= NP, languages in P are not NP-hard.
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.
(a) If P ̸= NP, no language is simultaneously in P and NP-hard. (b) If P ̸= NP, no language is simultaneously in P and NP-hard.
(c) If P ̸= NP, no language is simultaneously in P and NP-hard. If P ̸= NP and L ∈ P, then L ∈ P because P is closed under complement.
(d) Lodd is in P. If P ̸= NP, languages in P are not NP-hard.
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. If L∈P, then L is not NP-hard. D. Clique is not in P.
(a) If P ̸= NP, no language is simultaneously in P and NP-hard. (b) P ⊆ NP.
(c) If P ̸= NP, no language is simultaneously in P and NP-hard. If P ̸= NP and L ∈ P, then L ∈ P because P is closed under complement.
(d) If P ̸= NP, no language is simultaneously in P and NP-hard. Clique is NP-hard.
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?
Solution: 35
Let us define the random variable Z to be the average number of points earned on the exam. We
are therefore interested in finding an upper bound to P r[Z ≤ 50]. Additionally, we can note that
P r[Z ≤ 50] = 1 − P r[Z > 50]. Using Reverse Markov’s Inequality, we are able to find a lower
bound to Pr[Z > 50] since Z is bounded above by 100 and since E[Z] = 70. This means that
Pr[Z>50]≥70−50 =2.Combining: 100−50 5
Pr[Z ≤50]=1−Pr[Z >50] ≤ 1 − 25
Therefore, 35 is the upper bound on the fraction of students would scored less than 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
Solution: 14
Let us define the random variable Z to be the average number of points earned on the exam. We
are therefore interested in finding an upper bound to P r[Z ≤ 60]. Additionally, we can note that
P r[Z ≤ 60] = 1 − P r[Z > 60]. Using Reverse Markov’s Inequality, we are able to find a lower
bound to Pr[Z > 60] since Z is bounded above by 100 and since E[Z] = 90. This means that
Pr[Z>60]≥90−60 =3.Combining: 100−60 4
Pr[Z ≤60]=1−Pr[Z >60] ≤ 1 − 34
Therefore, 14 is the upper bound on the fraction of students would scored less than 60 points.
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
Solution: 13
Let us define the random variable Z to be the average number of points earned on the exam. We
are therefore interested in finding an upper bound to P r[Z ≤ 40]. Additionally, we can note that
P r[Z ≤ 40] = 1 − P r[Z > 40]. Using Reverse Markov’s Inequality, we are able to find a lower
bound to Pr[Z > 40] since Z is bounded above by 100 and since E[Z] = 80. This means that
Pr[Z>40]≥80−40 =2.Combining: 100−40 3
Pr[Z ≤40]=1−Pr[Z >40] ≤ 1 − 23
Therefore, 13 is the upper bound on the fraction of students would scored less than 40 points.
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? A. 6 B. 4 C. 2 D. 3 E. 5
Assume that the results of each test is independent of all the others.
Solution: Let A = “a person doesn’t have COVID-19 but the result gives positive back.” P r(A) ≤ 0.4. In order to boost the probability of confidence, we use the strategy of repeat the test several times, more specifically: we repeat the test k times, and if any of the test returns negative, then return negative. Therefore, the probability that a person doesn’t get COVID-19 but will still get a positive is P r(A)k . Therefore the probability of success is 1 − P r(A)k , and we want is to be at least 98%,i.e. 1 − Pr(A)k ≥ 0.98 =⇒ 0.4k ≤ 0.02 =⇒ k ≥ 5. Hence we would need 4 additional test to guarantee to desired probability of success.
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? A. 6 B. 4 C. 2 D. 3 E. 5
Assume that the results of each test is independent of all the others.
Solution: Let A = “a person doesn’t have COVID-19 but the result gives positive back.” P r(A) ≤ 0.2. In order to boost the probability of confidence, we use the strategy of repeat the test several times, more specifically: we repeat the test k times, and if any of the test returns negative, then return negative. Therefore, the probability that a person doesn’t get COVID-19 but will still get a positive is P r(A)k . Therefore the probability of success is 1 − P r(A)k , and we want is to be at least 98%,i.e. 1 − Pr(A)k ≥ 0.98 =⇒ 0.2k ≤ 0.02 =⇒ k ≥ 3. Hence we would need 2 additional test to guarantee to desired probability of success.
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? A. 6 B. 4 C. 2 D. 3 E. 5
Assume that the results of each test is independent of all the others.
Solution: Let A = “a person doesn’t have COVID-19 but the result gives positive back.” P r(A) ≤ 0.5. In order to boost the probability of confidence, we use the strategy of repeat the test several times, more specifically: we repeat the test k times, and if any of the test returns negative, then return negative. Therefore, the probability that a person doesn’t get COVID-19 but will still get a positive is P r(A)k . Therefore the probability of success is 1 − P r(A)k , and we want is to be at least 98%,i.e. 1 − Pr(A)k ≥ 0.98 =⇒ 0.5k ≤ 0.02 =⇒ k ≥ 6. Hence we would need 5 additional test to guarantee to desired probability of success.
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
Solution: A
For it to be a valid RSA cryptosystem, this e · d ≡ 1 (mod φ(n)) has to be true. Out of the choices given, only choice A satisfies.
For each of the n values, find two primes p and q to compute φ(n).
(A) n=33=3(11),p=3,q=11
φ(n) = (p − 1)(q − 1) = (3 − 1)(11 − 1) = 20 Checkife·d≡1 (modφ(n))
7 · 3 ≡ 1 (mod 20)
21 ≡ 1 (mod 20) is true
(B) n=33=3(11),p=3,q=11
φ(n) = (p − 1)(q − 1) = (3 − 1)(11 − 1) = 20 Checkife·d≡1 (modφ(n))
7·24≡1 (mod20)isnottrue
(C) n = 27, cannot find two primes p, q that compute n = pq
(D) n = 27, cannot find two primes p, q that compute n = pq
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
Solution: A
For it to be a valid RSA cryptosystem, this e · d ≡ 1 (mod φ(n)) has to be true. Out of the choices given, only choice A satisfies.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com