EECS 376: Foundations of Computer Science Winter 2020, University of Michigan,
EECS 376 Midterm SOLUTIONS
• DO NOT DETACH ANY PAGES—EVEN THE SCRATCH PAGES—FROM THIS EXAM!
Removing page(s) may result in a deduction in your grade.
Copyright By PowCoder代写 加微信 powcoder
• This exam is closed book and closed notebook, with no electronic devices allowed. The only resource
you may use is one 8.5 × 11-inch double-sided study sheet that you prepared yourself.
• Make sure you are taking this exam at your assigned time and location unless you have been given
explicit approval from the teaching staff to do otherwise.
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.
• The exam consists of multiple-choice and written-answer problems.
• For the multiple-choice problems, mark your answers by filling in the bubble to the left of your choice. Select only one choice.
• For the written-answer problems, write your answers clearly in the provided space.
• The exam has 10 pages printed on both sides, including this page, the scratch page that follows, and
the two scratch pages at the end.
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 and the location I was assigned by the staff.
Instructions:
Signature: Name: Uniqname: Exam room:
1-10 (Multiple Choice) 11-14 (Written Answer) Total
/ 30 / 40 / 70
Section Points
Multiple Choice (3 points each)
1. Which pair of numbers takes the greatest number of iterations to find the GCD when using the Euclidean Algorithm?
⃝ (800,300)
⃝ (100,55)
⃝ (1000,999)
Solution: gcd(29, 18) takes the most steps:
gcd(800, 300) = gcd(300, 200) = gcd(200, 100) = gcd(100, 0) = 100
gcd(100, 55) = gcd(55, 45) = gcd(45, 10) = gcd(10, 5) = gcd(5, 0) = 5
gcd(29, 18) = gcd(18, 11) = gcd(11, 7) = gcd(7, 4) = gcd(4, 3) = gcd(3, 1) = 1 gcd(1000, 999) = gcd(999, 1) = 1
gcd(19, 11) = gcd(11, 8) = gcd(8, 3) = gcd(3, 2) = gcd(2, 1) = 1
2. Diego is a beekeeper and has several hives on his land. He wants to put down some covers between these hives so the bees can travel even when it is raining. He wants to connect all the hives and wants to use as little material as possible. Assume that he only puts covering on paths directly between hives. Which algorithm would you use to solve the problem?
⃝ Karatsuba
⃝ Floyd-Warshall
⃝ Binary Search
Solution: The hives can be represented as nodes in a complete graph, with the edges between them weighted by the distance between the two associated hives. Then a minimum spanning tree would ensure that all hives are connected with the minimum total distance that needs to be covered. Thus, Kruskal’s algorithm can be used to solve the problem.
3. Consider
What is the most precise recurrence relation for the time complexity? What does the Master Theorem give for this relation?
the sorting algorithm slowsort, which can be represented with the following pseudocode.
1: functionSlowsort(A[1,2,…,n]) ▷nislengthofA
2: Slowsort(A[1, . . . , ⌊ n2 ⌋])
3: Slowsort(A[⌊n2⌋+1,…,n])
4: if A[⌊ n2 ⌋] > A[n] then
5: swap A[⌊ n2 ⌋] and A[n]
6: Slowsort(A[1, . . . , n − 1])
▷ sort both halves of the array recursively ▷ largest item in first half is greater than largest in the second
▷ put largest item in the unsorted array at the end ▷ sort the entire array minus one element recursively
⃝ T(n)=2Tn+T(n−1)+O(1);theMasterTheoremgivesT(n)=On2logn 2
T(n)=2Tn+T(n−1)+O(1); the Master Theorem is unusable 2
⃝ T(n)=3Tn+O(1);theMasterTheoremisunusable 2
⃝ T(n)=3Tn+O(1);theMasterTheoremgivesT(n)=Onlog23 2
⃝ This cannot be written as a relation; the Master Theorem is unusable
4. Which one of the following sets is uncountable?
Solution: Lines 2 and 3 each take T n steps. Line 6 takes T (n − 1) steps. The remaining lines 2
do constant work. The resulting recurrence T(n) = 2T n + T(n − 1) + O(1) is not in the form 2
required by the Master Theorem because of the T (n − 1) term.
5. Which of
The set of all decidable languages.
The set of all Turing machines.
The set of all C++ programs that never terminate. The set S = {‘hello’, ‘world’}
The set of all unrecognizable languages.
the following languages is decidable?
L280 = {⟨M⟩ : M rejects at least 280 different input strings}
L203HALT = {(⟨M ⟩, x) : M is a Turing Machine and M halts on x after at least 203 steps}
L281ACC = {(⟨M ⟩, x) : M is a Turing Machine and M accepts x in strictly less than 282 steps} L376 = {⟨M⟩ : M is a Turing Machine and M accepts the input string ‘101111000’}
None of the above
Solution: The set of all languages is uncountable. The set of recognizable languages is countable, since a recognizable language must have at least one machine that recognizes it, and the set of machines is countable. The difference of these sets must be uncountable, since the class of countable sets is closed under union.
Solution: A decider for L281ACC can simulate M on x for up to 281 steps, and if M accepts in any of those steps, the decider accepts (⟨M⟩,x). Otherwise it rejects (⟨M⟩,x).
All/Some/No.
6. The complements of (⃝ all / some / ⃝ no) undecidable languages are unrecognizable.
True/False/Unknown. Determine whether each of the following statements is known to be true, known to be false, or not known to be true or false.
7. LetL={(T,G):T isanMSTofagraphG}. Lisdecidable. True
8. There are languages that can be decided by a 376-tape Turing Machine but not a single-tape Turing Machine.
⃝ True False
9. When a Turing Machine M is given an input x, it can only reject or accept x.
10. All MSTs of a single graph G have the same weight. True
Solution: Some. LACC is unrecognizable, and it is the complement of the undecidable language LACC. At the same time, LACC is recognizable and is the complement of the undecidable language LACC.
Solution: True. A decider can use Kruskal’s algorithm to compute an MST T ′ of G, check that T is a spanning tree of G, and check that the total weight of T and T ′ are equal.
Solution: False. We saw in discussion that a two-tape TM is equivalent to a single-tape TM. The construction in that proof can be generalized to show that an n-tape TM is equivalent to a single-tape TM.
Solution: False. A TM M can also loop on x – M is not necesarily a decider.
Solution: True. An MST of a graph G is a subset of the edges that connects all vertices with minimum weight. There can only be one minimum weight for this graph G.
Suppose this is not true. Then there exist multiple MSTs for G that have different weights. However, an MST for G must have minimum weight, so we should only consider the MST with the lowest weight among all of them. Therefore, any MST for G is going to share this minimum weight, so the claim is true.
Written Answer (10 points each)
11. Let A and B both be decidable languages, and let A B = A ∪ B. Show that A B is decidable. Note: You do not have to draw the crane operator each time. You can instead write A crane B.
Solution: Since A and B are decidable, there exist deciders MA and MB that decide A and B, respectively. We can construct a decider M for A B as follows:
Ifx∈A B=A∪B,itmustbethecasethatx̸∈Aorx̸∈B. Ifx̸∈A,MA(x)rejects,soM accepts x. If x ̸∈ B, MB(x) rejects, so M accepts x. Thus, M accepts all x ∈ A B. On the other hand,ifx∈/A B,itmustbethatx∈Aandx∈B. ThenbothMA(x)andMB(x)wouldaccept, soMrejectsx. SinceMacceptsallx∈A Bandrejectsallx̸∈A B,MdecidesA B,and therefore A B is decidable.
Alternatively, we can rely on the closure properties proven in class. We saw in discussion section that the class of decidable languages is closed under complement. Thus, if A and B are decidable, so are A and B. We also saw in lecture that the class of decidable languages is closed under union. Thus, if A and B are decidable, so is A ∪ B. Since this is the definition of the crane operator, it follows that A B is decidable.
M = “on input x:
1: if MA(x) rejects then accept
2: if MB(x) rejects then accept 3: reject”
12. Consider the following language.
LREJ = {(⟨M⟩,x) : M is a Turing Machine and M rejects x}
Show that LHALT ≤T LREJ.
Solution: Assume that there is some decider R of LREJ. We will use R to construct a decider H for LHALT. Given a Turing Machine M and an input x as input, H works as follows:
H = “on input ⟨M⟩, x:
1: Construct Turing machine M′ as follows:
2: if R(⟨M′⟩,x) accepts then accept
3: else reject ”
M′ = “on input w:
1: RunMonw 2: reject”
Note that M′ rejects an input w exactly when M halts. More specifically, we have the following cases for the behavior of H(⟨M⟩,x):
• If(⟨M⟩,x)∈LHALT,M haltsonx,eitherbyacceptingorrejectingit. Thenline1ofM′(x) would complete, and M′ rejects x in line 2 of its code. Thus, R(⟨M′⟩,x) would accept, and H(⟨M⟩,x) also accepts.
• If(⟨M⟩,x)∈/LHALT,M loopsonx. Thenline1ofM′(x)wouldloop,soM′ doesnotreject x. Thus, R(⟨M′⟩,x) would reject, and H(⟨M⟩,x) also rejects.
We can see that H decides LHALT, so LHALT ≤T LREJ. It is also a valid solution to hardcode x in M′
H = “on input ⟨M⟩, x:
1: Construct Turing machine M′ as follows:
2: if R(⟨M′⟩,ε) accepts then accept
3: else reject ”
M′ = “on input w:
1: RunMonx 2: reject”
We can then run R on ⟨M′⟩ and an arbitrary input (e.g. ε, as above). The analysis is as before.
13. Given an array A of n integers, a majority element of A is an element in A that appears strictly more than n2 times. The algorithm MajorityElement defined below finds the majority element of A if it exists. If A has a majority element, MajorityElement will return that element. Otherwise, MajorityElement will return ∅.
3: 4: 5: 6: 7:
functionMajorityElement(A[1,2,…,n])) if n = 1 then return A[1]
x ← MajorityElement(A[1, . . . , ⌊ n2 ⌋])
y ← MajorityElement(A[⌊ n2 ⌋ + 1, . . . , n]) if x̸=∅then
iterate over A, counting the number of occurrences of x
if the number of occurrences of x in A is > n2 then return x
if y̸=∅then
iterate over A, counting the number of occurrences of y
if the number of occurrences of y in A is > n2 then return y
(a) Analyze the time complexity of MajorityElement and give the asymptotic time complexity as a closed-form solution.
Solution: Let T (n) be the number of steps the algorithm takes on an array of size n. Lines 3 and 4 each recursively apply the algorithm on subarrays of size n2 , giving us a total of 2T ( n2 ). Lines 6 and 9 iterate over the entire array, taking O(n) time. The remaining operations take constant time. Thus, we have the recurrence T (n) = 2T ( n2 ) + O(n). Applying the Master Theorem with k = 2,b = 2,d = 1 gives us T(n) = O(nlogn).
(b) Show the correctness of the MajorityElement algorithm by proving the following statement: If z is a majority element of an array A of n integers, where n is a power of 2, then z must be a majorityelementofatleastoneofthesubarraysA[1,…,n2]andA[n2 +1,…,n].
Solution: Suppose z is a majority element of A. For the purposes of contradiction, assume that z is not a majority element of A[1,…, n2 ] nor of A[n2 +1,…,n]. Let a be the number of occurrences of z in A[1, . . . , n2 ]. Since z is not a majority, element, a ≤ n2 /2 = n4 . Similarly, if b is the number of occurrences of z in A[n2 + 1,…,n], b ≤ n4 . Then the total number of occurrencestofzinAist=a+b≤ n4 +n4 = n2. Thiscontradictsthatzisamajorityelement of A, since that requires that the number of occurrences be t > n2 . Thus, the assumption that z is not a majority element of A[1,…, n2 ] nor of A[n2 + 1,…,n] must be false, and the statement is proved.
14. Consider the following situation. Sanjana is looking to book a one-way flight from Detroit to Los Angeles. Going to the website for Airline X, Sanjana finds a direct flight from Detroit to Los Angeles for $504. After searching for a bit longer, Sanjana also finds a flight for the same day from Detroit to Vancouver with one stop in Los Angeles for $157. Sanjana realizes that she can save $347 by booking the flight from Detroit to Vancouver and simply leaving the airport at the stop in Los Angeles.
We call such a flight a hidden-city flight from Detroit to Los Angeles, and we will attempt to design an algorithm to find the cheapest hidden-city flights between all pairs of cities in the airline network.
Let G = (V,E) be an edge-weighted graph where each vertex v ∈ V represents a city and each edge (u, v) ∈ E represents a direct flight from u to v. The weight w(u, v) of edge (u, v) represents the cost of the direct flight from u to v. A hidden-city flight from u to v would then be any path in G that starts at u and contains v as an intermediate or final vertex. To use the example above:
Notice that the direct flight from Detroit to Los Angeles is $504 and the direct flight from Los Angeles to Vancouver is −$347. Therefore, the cheapest hidden-city flight from Detroit to Los Angeles goes from Detroit to Los Angeles to Vancouver and costs $157 = $504 − $347.
Use Floyd-Warshall to design an algorithm to find the cheapest hidden-city flights between all pairs of cities in an edge-weighted graph G with weight function w. You do not need to prove your correctness.
Los Angeles
functionFloydWarshall(G=(V,E),w:E→R) for i = 1 to |V |, j = 1 to |V | do
d0(i, j) ← w(i, j)
for k = 1 to |V | do
for i = 1 to |V |, j = 1 to |V | do
dk(i, j) ← min{dk−1(i, j), dk−1(i, k) + dk−1(k, j)} return d|V |
Solution: The Floyd-Warshall algorithm finds shortest standard paths between all pairs of ver- tices. A hidden-city path from u to v consists of any path of the form (u, w1, . . . , wm, v) or (u,w1,…,wm,v,x1,…,xn). The former is just a standard path from u to v, while the latter is a combination of a standard path from u to v and a standard path from v to xn. We need to find the minimal path of either form, and it suffices to compare the lengths of the shortest paths from u to v, or from u to v and then from v to every other vertex xk (principle of substructure optimality). We can use Floyd-Warshall itself to compute the lengths of each subpath.
1: 2: 3: 4: 5: 6:
functionHiddenCity(G=(V,E),w:E→R) d ← FloydWarshall(G, w)
for i = 1 to |V |, j = 1 to |V | do
h(i, j) ← d(i, j)
for k = 1 to |V | do
h(i,j)←min{h(i,j), d(i,j)+d(j,k)} return h
A common mistake is to attempt to construct a u-to-v hidden-city path from u to z and z to v hidden-city paths. However, it is not necessarily the case that the combination of hidden-city paths from u to z and from z to v forms a valid hidden-city path from u to v. As an example, suppose that the best hidden-city path from u to z were (u,z,w), and the best from z to v were
(z, v). Combining the two would result in two disjoint segments (u, z, w) and (z, v), which is not a valid path in the graph.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com