EECS 376: Foundations of Computer Science Winter 2020, University of Michigan,
EECS 376 Midterm Exam
Instructions:
• DO NOT DETACH ANY PAGES—EVEN THE SCRATCH PAGES—FROM THIS EXAM!
Copyright By PowCoder代写 加微信 powcoder
Removing page(s) may result in a deduction in your grade.
• 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.
Signature: Name: Uniqname: Exam room:
Section Points
1-10 (Multiple Choice) 11-14 (Written Answer) Total
/ 30 / 40 / 70
This page is intentionally left blank for scratch work.
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) ⃝ (29,18)
⃝ (1000,999) ⃝ (19,11)
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
3. Consider the sorting algorithm slowsort, which can be represented with the following pseudocode. What is the most precise recurrence relation for the time complexity? What does the Master Theorem give for this relation?
⃝ T(n)=2Tn+T(n−1)+O(1);theMasterTheoremgivesT(n)=On2logn 2
⃝ T(n)=2Tn+T(n−1)+O(1);theMasterTheoremisunusable 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?
⃝ 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.
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
5. Which of 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
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.
9. When a Turing Machine M is given an input x, it can only reject or accept x. ⃝ True
10. All MSTs of a single graph G have the same weight. ⃝ 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.
12. Consider the following language.
LREJ = {(⟨M⟩,x) : M is a Turing Machine and M rejects x}
Show that LHALT ≤T LREJ.
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.
(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].
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 |
This page is intentionally left blank for scratch work.
This page is intentionally left blank for scratch work.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com