Instructions:
EECS 376 Midterm Exam, Winter 2022
This exam is closed book, closed notebook. You may not provide your own scratch paper. No electronic devices are allowed. You may use one 8.5 × 11-inch study sheet (both sides). Make sure you are taking the exam at the time slot and the classroom you were assigned by the staff. Please print your UNIQNAME at the top of each page.
Any deviation from these rules will constitute an honor code violation. In addition, the staff reserves the right not to grade an exam taken in a violation of this policy.
Copyright By PowCoder代写 加微信 powcoder
The exam consists of 10 multiple choice questions, 4 short-answer questions, and 3 longer proofs.
You only need to answer two of the longer proof questions. You are to cross out the one proof question you don’t want graded. For the multiple choice questions, please fill-in the circle you select completely and clearly.
For the short-answer and proof sections, please write your answers clearly in the spaces provided. If you run out of room or need to start over, you can use the blank pages at the end but you MUST make that clear in the space provided for the answer. The exam has 15 pages printed on both sides, including this page and the blank page at the end.
You must leave all pages stapled together in their original order. Write out and sign the full honor pledge 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 before exam grades are released.
I attest that I am taking the exam at the time slot and the classroom I was assigned by the staff.
Signature: Name:
UNIQNAME (print):
Multiple Choice – 30 points
Each question has one answer unless otherwise indicated. Fully shade in the circle with a pencil or black ink. Each question is worth 3 points.
1. Which of these is an intermediate step in the computation of gcd(70,29) when using the Euclidean algorithm?
⃝ gcd(29,13)
⃝ gcd(13,7)
⃝ gcd(7,1)
2. In the following algorithm, input() is a function that returns a user-specified positive integer.
Solution: (70, 29) → (29, 12) → (12, 5) → (5, 2) → (2, 1).
1: 2: 3: 4: 5: 6: 7: 8: 9:
a ← input()
b ← input() whilea<376andb<376do
c ← input()
if c is odd then
b←b+1 else
a←b+2 b←a+2
Which of the following is a valid potential function for proving that the algorithm halts? ⃝ a+2b
⃝ a+b √ 376−b
⃝ (376−a)+(376−b) ⃝ (376−a)+2(376−b)
Solution: We claim that f = −b serves as a valid potential function for this program. Let ai and bi denote the value of a and b after the i’th loop iteration, let ci the i’th input value of c, and let fi = −bi.
fi is strictly decreasing: If ci is odd, fi = −bi = −(bi−1 + 1) = fi−1 − 1. Otherwise, fi =−bi =−(bi−1+4)=fi−1−4. Inbothcases,fi
The solution is just f shifted by 376.
UNIQNAME (print):
3. Put the following functions in order by increasing asymptotic complexity.
i nlog2(π) ii n!
iii log2(log2(n))
iv log3(4cos(π/2))
⃝ iii, iv, i, ii
⃝ ii, iv, iii, i
⃝ iv, iii, ii, i
⃝ iv, i, iii, ii
iv, iii, i, ii
Solution: Let f(n) and g(n) be functions. If there exist constants M > 0 and n0 such that for all n > n0, |f(n)| ≤ M|g(n)|, then we say that f(n) = O(g(n)).
• log3(4cos(π/2)) is just a constant. It doesn’t grow with the size of the problem
• log2(log2(n)) = O(nlog2(π)) with M = 1, n0 = 5.
• nlog2(π) = On! with M = 1, n0 = 10. 2
4. What algorithmic technique does the Karatsuba algorithm use?
⃝ Dynamic Programming
⃝ Bottom-up table
⃝ None of the above
5. Andrew doesn’t like doing homework, so he incentivizes himself with food. At each hour, until he finishes his homework, he chooses to do one of the following (as appropriate):
(i) Do one problem and eat a chocolate chip cookie; (ii) Do two problems and eat two oreos;
(iii) Do three problems and eat three tootsie rolls; (iv) Do three problems and eat a cup of ice cream.
Assume that Andrew does his homework problems in order. Let W(n) denote the number of ways for Andrew to do a homework with n problems (i.e., the number of sequences of foods he eats). Which of the following is a valid recurrence for W (n), when n ≥ 3?
Divide and Conquer
Solution: No explanation provided.
UNIQNAME (print):
⃝ W(n)=W(n−1)+2W(n−3)
⃝ W(n)=W(n−1)+2W(n−2)+4W(n−3) ⃝ W(n)=W(n−1)+W(n−2)+W(n−3)
√ W(n)=W(n−1)+W(n−2)+2W(n−3) ⃝ None of the above
Solution: The solution is W(n) = W(n−1)+W(n−2)+2W(n−3), because to do a homework with n problems, Andrew could do the last problem and the rest n − 1 in any valid way (W (n − 1) ways). Or Andrew could do the last two problems together and do the rest n − 2 in any valid way (W (n − 2) ways), or do the last three problems together and make a cup of ice cream or three tootsie rolls (2 different choices) and do the rest n − 3 in any valid ways (W (n − 3) ways).
6. Which of the following subsets of {0,1}∗ are uncountable?
i {⟨M⟩|M isaTMthatisadecider}
ii {⟨M1, M2⟩ | M1, M2 are TMs such that L(M1) = L(M2)}
iii {⟨M,x⟩ | M is a TM that halts on input x ∈ {0,1}∗}
⃝ Only (i) and (ii)
⃝ Only (i)
⃝ Only (ii) and (iii)
⃝ Only (i), (ii) and (iii)
None of the above
Solution: (E)
All of the languages are subsets of {0,1}∗. {0,1}∗ is countable, and therefore all of its
subsets are as well.
It is also worth noting that the collection of all languages (a set of sets) is in fact uncountable. We used the this fact to prove that there exists some undecidable languages, with Cantor’s Diagonalization Method. (The size of a language is countable, but the number of possible languages is uncountable.) Should it confuse you with concepts in this question, think of the (uncountable) set of all languages as the power set of Σ∗.
7. Fill in the blank to make the following statement true and as strong as possible:
L is decidable
L is recognizable
UNIQNAME (print):
√ Only if (⇒)
⃝ If and only if (⇔) ⃝ None of the above
If L is decidable, then both L and L are recognizable, so “only if” is correct. We have seen that LACC is recognizable but undecidable, so “if” is not correct.
UNIQNAME (print):
8. What language does the following TM decide?
qaccept 1 → 1, R
⊥ → ⊥, R 1 → ⊥,R
Note: In the following, (0|1)∗ denotes a binary string of any length. ⃝ 0∗10
√ 0∗11(0|1)∗
⃝ 0∗01(0|1)∗
⃝ None of the above
9. Which of the following are true?
i Let LPAL = {x ∈ Σ∗ | x is a palindrome}. Then LPAL ≤T LHALT. ii LACC is recognizable but not decidable.
iii Let M be a Turing Machine that rejects all input strings x ∈ Σ∗. Then M does not recognize any language.
⃝ Only (i)
⃝ Only (ii) and (iii)
⃝ Only (i), (ii) and (iii)
⃝ None of the above
Only (i) and (ii)
Solution: We start in qstart and may read in an number of 0′s before potentially accept- ing. Furthermore, after accepting, we may still have arbitrarily bits after the 1 which we read to take the 1 → 1,L transition from q1. This implies that neither the first nor the last are the answer. To get from qstart to qaccept, a TM must read two consecutive 1’s, so the second must be the correct answer.
UNIQNAME (print):
Solution: i. is true because LPAL is decidable and we can do a Turing Reduction from any decidable language.
ii. is true and was done in class.
iii. is false because if M rejects all inputs x ∈ Σ∗ then L(M) = ∅. Therefore M recognizes the empty language.
10. Which of the following are true?
i The Kolmogorov complexity function is uncomputable.
ii LHALT ≤T LHALT
iii There are countably many PowerPoint files.
⃝ Only (i) and (ii)
⃝ Only (i)
⃝ Only (ii) and (iii)
⃝ None of the above
Only (i), (ii) and (iii)
i is true–Kolmgorov complexity is not computable.
ii is true–any language can be trivially Turing reduced to its complement.
iii is true. PowerPoint files is a subset of the set of finite strings. And the set of finite strings is countable, so a subset of it is too.
Short Answer – 30 points
1. (10) Mark and Mary are competing to write a new algorithm to sort an array of size n. After some complexity analysis, they find that Mark’s algorithm has time complexity Θ(n2), while Mary’s algorithm has time complexity Θ(n log n). Mary expects her algorithm to run faster, but real-world testing on some moderately large arrays shows that Mark’s algorithm runs faster. Briefly (ideally in two sentences or less each) answer the following questions:
(a) Explain why this could be the case.
(b) Can you be sure there are inputs for which Mary’s algorithm will run faster than Mark’s? Justify your answer.
UNIQNAME (print):
(a) Big-Θ allows us to disregard constant factors for performance in the long-run, but for smaller values of n, these constant factors might matter.
(b) As the input size grows at some point, Mary’s algorithm will outperform Mark’s. This is because n2 = ω(n log n).
UNIQNAME (print):
2. (5) Let Leven be the language of all binary strings with an even number of 1s. Is Leven the
language of the following DFA? Justify your answer.
1 q1 0 q2 q3 1
Solution: This does not. For example, the string 1010010 would be accepted, although it has an odd number of ones. And such an input can’t be in the language Leven.
UNIQNAME (print):
3. (10) The following is a valid recognizer for the language LACC:
A = “on input (
Run M on x and return the same.”
A student, , is not convinced that the language LACC is unrecognizable. He proposes the following recognizer A′ for the language LACC:
A’ = “on input (
Run M on x and return the opposite.”
Why is A′ not a recognizer for LACC?
Solution: Remember that LACC is the set of all machines and input (⟨M⟩,x) where M does not accept x. Or in other words, M either rejects or loops on x.
Now suppose we have the input (⟨M⟩,x) where M loops on x. If A′ runs M on x, then A′ will loop forever because M loops on x forever- which means that A′ does not accept (⟨M⟩,x) and A′ does not accept all strings in LACC. Thus, A′ is not a valid recognizer for LACC.
Alternative Solution: Observe that LACC is an undecidable but recognizable language. As proven in class, if some language L is undecidable and recognizable, then it must be the case that L is unrecognizable. Thus, no recognizer exists for LACC.
UNIQNAME (print):
4. (5) Draw a DFA for the language of binary strings that consist of zero or more 01’s followed by zero or more 10’s. So the language (01)∗(10)∗. For example, the DFA should accept ε, 01, 1010, and 011010, but it should not accept 011, 101, or 1001. Your solution should use no more than 7 states.
UNIQNAME (print):
Proofs and longer questions – 40 points
Answer two of the following three questions. Clearly cross out the question you do not want graded. If it isn’t clear what problem you don’t want graded, we will grade the first two. Each of the two questions are worth 20 points.
1. The 2-Geometric Subsequence Problem is defined as follows: Given a sequence of n positive integers a1, . . . , an, find the length of the longest subsequence where each value in the subsequence is twice the previous value. For example, in the sequence 6, 2, 3, 4, 6, 8, 12, 10, the length of the longest twice-the-previous subsequence is 3 and is achieved by the subsequence 2, 4, 8 (also by 3, 6, 12).
(a) Find a recurrence relation that can be used to solve the 2GSP.
(b) Write pseudocode which solves the problem using dynamic programming. It should have a run time that is O(n2).
Let L(i) be the length of the longest 2-geometric subsequence that ends at ai. Then we may define the recurrence L(i) = 1+max({L(j) : 1 ≤ j < i and aj = ai/2}∪{0}) if ai is even and L(i) = 1 if ai is odd. In other words, we compute the length of the longest such subsequence ending at each aj = ai/2 if ai is even (so that we can extend it with ai). We may then compute the length of the longest such subsequence as max{L(i) : 1 ≤ i ≤ n}.
The pseudocode is as follows:
(a) InitializeL(i)=0foreach1≤i≤n
(b) For i = 1..n:
1+max({L(j):1≤j