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 17 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. Consider the following code. Note that the variables x and y are real numbers.
Which of the following is a valid potential function for the algorithm Foo376 (above)?
⃝ s = ey − x
2. In a new software company “Three-and-Out” a new “three-way” mergesort algorithm is used. The new algorithm splits the array into three equal parts instead of two equal parts, then sorts the three sub-arrays recursively and at the end merges the sorted sub-arrays. What is the correct recurrence relation for this new algorithm?
⃝ T(n) = 2T(n/3) + O(n)
⃝ T(n) = 3T(n/2)+O(nlogn)
T (n) = 3T (n/3) + O(n)
⃝ T(n) = 2T(n/2) + O(n)
⃝ T(n) = 3T(n/2) + O(n)
⃝ None of the above
Require: x > y > 0 are real numbers ▷ Hint: This actually matters… 1: functionFoo376(x,y)
2: if x≤0thenreturn1;
3: z ← Foo376(x − log y, y)
4: return (z + 1)
None of the above
Solution: If we choose some y < 1, then log y will always be negative, so that x is strictly increasing. Thus, the condition x ≤ 0 will never become false. There is no valid potential function because Foo376 does not halt on all inputs.
Solution: (C)
In each of the splitting, three new sub-arrays are generated and each of them have a length of n3 . The algorithm then runs the following two stages: recursion on three different sub- arrays, with a total time complexity of 3 × T (n/3); merging all three sub-array into a
UNIQNAME (print):
larger array. In the second stage we can potentially use three pointers on the three sub- arrays and increment the smallest one, append it to the final array. Which shows that the second stage has a time complexity of O(n).
Thus the time complexity is T (n) = 3T (n/3) + O(n)
3. Let T (n) = 4T (n/3) + O(
⃝ O(nlogn)
O(n ) ⃝ O(2n)
n). What is the tightest asymptotic upper bound for T (n)?
Solution: Using the Master Theorem. k = 4, b = 3, d = 0.5. So k > 1. From the bd
Master Theorem we get O(nlogbk) or O(nlog34). That’s about O(n1.26). Of the options, √
n 2 is the tightest bound.
UNIQNAME (print):
4. Suppose S1 ⊆ R is an uncountable set and S2 ⊆ R is a countable set. Which of the following
will always true?
i Their intersection S1 ∩ S2 is countable. ii Their union S1 ∪ S2 is countable.
iii The complement of S1 is sometimes, but not always, countable.
⃝ only iii
⃝ ii and iii
Solution: Choice i is correct. Consider the intersection of the set of reals (uncountably infinite) and the set of integers. Their intersection is just the set of integers which are countably infinite.
Choice ii is incorrect. For contradiction assume this is true and the union is countably infinite. Then as the uncountably infinite language is a subset of this union it should also be countably infinite. This is clearly a contradiction.
Choice iii is correct. Consider the set where the Universe is the reals. The set of all the reals other than the integers has the integers as a complement and the integers are countable.
Now consider the set of of the non-positive reals. The complement of that, where the universe is the reals, are the positive reals, which are uncountable.
This makes option C the correct answer.
5. A bottom-up dynamic programming algorithm fills the entire table, where the table has dimensions n × m. What can be said about the runtime of the algorithm?
⃝ No conclusions can be drawn from the information given.
6. Let L1, L2 be languages such that L1 ≤T L2. If L2 is undecidable, L1 is Page 4
undecidable.
Solution: The bottom-up dynamic programming approach involves filling each entry in the table. There are n × m entries in the table, and each gets filled. This takes at least nm steps, which gives us a lower-bound of Ω(nm) for the algorithm. Note that O(nm) and Θ(nm) only hold if filling each entry takes constant time, and that is not always the case.
UNIQNAME (print):
L2 being undecidable tells nothing on the decidability of L1. To show this, we offer 2 examples.
If L1 is decidable, then its decider can call a black-box decider for L2 and simply ignore its results, making it true that L1 ≤T L2.
If it is true that L1 ≤T L2, L1 being undecidable means that L2 is undecidable as well. Thus, L1 can also be undecidable, and this relation would still be possible.
Because we have shown both cases where L1 is decidable or undecidable, the answer is sometimes.
7. Consider the following algorithm for the 0-1 knapsack problem. Here n is the number of items, K is the total weight the knapsack can carry, and V [i], W [i] are respectively the value and weight of the ith item. The output is the maximum total value of items that can be carried in the knapsack.
What is the tightest bound on the worst-case running time of Knapsack? ⃝ O(n)
⃝ O(n2) ⃝ O(nK)
√ O(2n) ⃝ O(2K)
1: functionKnapsack(n,K,V,W)
2: if n==0orK==0thenreturn0
3: if W [n] > K then return Knapsack(n − 1, K, V, W )
4: else return max{ Knapsack(n − 1, K, V, W ),
Knapsack(n−1,K −W[n],V,W) + V[n] }
Solution: Notice that this function does not solve the knapsack problem using dynamic programming—it doesn’t use a table to save answers to subproblems—so its time com- plexity is not necessarily O(nK). Instead, in the worst case, the function will make two recursive calls while decreasing n by 1, so it will compute every possible combination of items in V to see which one has the greatest total value without exceeding a weight of K. Since there are n items in V , there are 2n possible combination of items in V , so the
UNIQNAME (print):
worst case time complexity of this function is O(2n).
By way of illustration, consider that when this function starts with n elements in V , it can make 2 calls, each with n−1 elements in its respective input vector V . This continues until n = 0. In the worst case, each call makes 2 more calls to the function, which will create 2n calls. Each call (ignoring the work done by subroutine calls) takes constant O(1) work, resulting in a time complexity of O(2n).
8. Which of the following languages (over ASCII) are decidable?
i The set of all legal names of this term’s EECS 376 IAs. ii The set of all prime numbers.
iii The set of all valid natural deduction proofs.
⃝ only i and ii
⃝ only ii and iii
⃝ none of i, ii, or iii
9. Fill in the blank to make the following statement true and as strong as possible: L is recognizable L is decidable.
⃝ Only if (⇒)
⃝ If and only if (⇔)
⃝ None of the above make the statement true
10. Which language is decidable? Assume M is a Turing Machine.
√ {⟨M⟩|M isaTMand∃M′ suchthatε∈/(L(M)∩L(M′))}
⃝ {⟨M⟩|M isaTMsuchthat|L(M)|isodd} Page 6
all of i, ii, and iii
Solution: All are true. i) if finite and so countable. ii) is a subset of the integers and so countable. iii) is finite and so countable.
Solution: A
If L is decidable, then both L and L are recognizable, so “if” is correct. We have seen that LACC is recognizable but undecidable, so “only if” is not correct.
UNIQNAME (print):
⃝ {⟨M⟩|M isaTMsuchthat0376k ∈L(M), forallk≥1}
⃝ {⟨M⟩|M isaTMsuchthatx∈/L(M)forsome|x|=376}
⃝ {⟨M⟩|M isaTMand∃M′ suchthatL(M)∪L(M′)={376}}
Solution: The language Linc = {⟨M ⟩| there exists a TM M’ such that the empty string ε ∈/ L(M)∩L(M′)} includes all languages (if M′ = ∅ for example) and all machines have that property and so the language is trivially decidable.
UNIQNAME (print):
Shorter Answer – 30 points
1. (8) Briefly prove or disprove the following statement:
If L1, L2 ⊆ {0, 1}∗ are undecidable languages and L1 ̸= L2, then their symmetric difference, (L1 \ L2) ∪ (L2 \ L1), is also an undecidable language.
Solution: The statement is False. Consider L1 = L and L2 = L where L is an undecidable language. Then their symmetric difference is {0,1}∗, which is decidable.
UNIQNAME (print):
2. (6) Alice and Bob are competing to write a new algorithm to sort an array of size n. After some complexity analysis, they find that Alice’s algorithm has time complexity Θ(n2), while Bob’s algorithm has time complexity Θ(n log n). Bob expects his algorithm to run faster, but real-world testing on some moderately large arrays shows that Alice’s algorithm actually 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 exist inputs for which Bob’s algorithm will run faster than Alice’s? Justify your answer.
(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, Bob’s algorithm will outperform Alice’s.
UNIQNAME (print):
3. (6) A stay-put TM is an alternate model of TM. It is identical to the model of TM we learned in class (tape bounded on left, unbounded on right) except that the tape head is allowed to perform a “no-move.” Namely, on each transition, the tape head is allowed to move one spot left, one spot right, or stay in place. Briefly answer the following questions (at a high level; one sentence per part is fine).
(a) Can a stay-put TM simulate a normal TM?
(b) Can a normal TM simulate a stay-put TM? If your answer is “yes,” you only need to address how a normal TM would simulate writing a character and performing a “no- move.” If you answer “no,” you only need to provide a brief justification.
Solution: Yes. A stay-put TM can simulate a normal TM by never using the “no- move.”
Solution: Yes. Whenever a stay-put TM would write a character and perform a “no move,” a normal TM could perform that same write, then move one spot right, not modify the cell it just moved to (i.e. write the character that is already in the cell), and move one spot left.
Note that moving left and then moving right is not a valid solution because this would not work if we were in the left-most cell of the tape.
UNIQNAME (print):
4. (10) All DFAs in this problem are over the alphabet Σ = {0, 1}.
1 q1 0 q2 q3 1
(a) What is the language of the above DFA?
Solution: Regular expression: 1(010)∗
(b) Draw a DFA whose language is the set of all binary strings that begin with zero or more 0’s followed by zero or more 01’s (so 0∗(01)∗). You should use 5 or fewer 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-Arithmetic 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 increasing by 2. For example, in the sequence 6, 1, 2, 3, 12, 4, 5, 6, the length of the longest increasing-by-two subsequence is 3 and is achieved by the subsequence 2, 4, 6 (also by 1, 3, 5).
(a) Find a recurrence relation that can be used to solve the 2ASP.
(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 increasing-by-2 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}). In other words, we compute the length of the longest such subsequence ending at each aj = ai − 2 (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) Fori=1..n: L(i)=1+max({L(j):1≤j