EECS 376: Foundations of Computer Science Fall 2020, University of Michigan,
EECS 376 Midterm Exam
The multiple-choice portion of the exam consists of 10 randomly selected questions out of the “Multiple Choice”, “All/Some/No”, and “True/False” sections below. The written portion of the exam consists of 4 randomly selected questions out of the “Written Answer” section below. These two portions are released as separate Canvas quizzes. You are to submit the answers to the multiple-choice portion on Canvas. Submit your written solutions to Gradescope as you would for a homework assignment. You will not submit anything on Canvas for the written part.
The multiple-choice Canvas quiz has a time limit of 30 minutes, plus a 10-minute grace period. The expected time to complete the written portion is 40 minutes. However, you may submit any time within the 2-hour window for the exam. Both portions must be submitted before 9pm Eastern Time.
Copyright By PowCoder代写 加微信 powcoder
Logistics:
• The exam will take place on Monday, October 12, 7pm – 9pm Eastern Time.
• You must submit your multiple-choice answers on Canvas prior to 9pm Eastern Time. You will have 30 minutes plus a 10-minute grace period to take the quiz, but it must be submitted before 9pm.
• You must submit your written answers to Gradescope prior to 9pm Eastern Time. There will be no grace period for the written portion. As with the homework, we suggest you start your submission at least 15 minutes before the deadline.
• You may use any static resources for the exam, including the textbooks, lecture slides, Google, etc. You may not use calculators (e.g. a physical calculator, WolframAlpha, etc.), as we consider that to be a dynamic resource.
• You are prohibited from searching for answers to any of the exam questions online.
• You are prohibited from soliciting help from anyone, whether in person, over text/chat, on StackOver-
flow, making public Piazza posts, or any other means.
• Your solutions must be entirely your own work.
• If you have clarification questions, make a private post on Piazza, and a staff member will respond as soon as possible.
• If you run into technical issues or have an emergency, contact the staff right away. Do not contact a fellow student for help.
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.
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 I was assigned by the staff.
Signature:
Multiple Choice (3 points each)
1. Let f and g be functions mapping integers to integers. It is (⃝ always / ⃝ sometimes / ⃝ never) true that g(f(n)) = O(f(g(n))) for functions f and g.
2. For the recurrence T (n) = 2T (n1/4) + O(log n), which of the following is the tightest asymptotic upper bound on T(n)?
(Hint: use the substitution S(n) = T(2n))
⃝ O(logn) ⃝ O(nlogn) ⃝ O(nlog2n)
3. 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.
4. Consider an algorithm to multiply matrices that takes in two n × n matrices, X and Y , and outputs the resulting n × n matrix, Z. The algorithm performs the multiplication by partitioning each of the matrices X, Y , and Z into four n/2 × n/2 matrices. It makes recursive calls to multiply the n/2 × n/2 submatrices, then adds the values gained by these recursive calls to compute the values for each of the elements in Z. Which of the following is an accurate description of the paradigm used by this algorithm?
⃝ Divide and conquer
⃝ Dynamic programming
⃝ Both divide and conquer and greedy
⃝ Both dynamic programming and greedy
5. There are N students in a room standing in a straight line, and there are N seats that are also in a straight line parallel to the students’ line. The students can move in any direction, taking one step at a time, and each step takes one second. The task is to assign the students to seats so that the time for all students to reach their assigned seat is minimized. The algorithm finds the student that is closest to an unoccupied chair (breaking ties arbitrarily), assigns them to that chair, and then repeats the process on the remaining students. Which of the following is an accurate description for the paradigm used by this algorithm?
⃝ Divide and conquer
⃝ Dynamic programming
⃝ Both divide and conquer and greedy
⃝ Both dynamic programming and greedy
6. Which of the following statements is true?
⃝ If L1 and L2 are undecidable languages then L1 ∪ L2 is undecidable. ⃝ If L1 and L2 are undecidable languages then L1 ∩ L2 is undecidable. ⃝ If L is undecidable, then L is unrecognizable.
⃝ If L is unrecognizable, then L is undecidable.
7. A finite subset of an undecidable language is (⃝ always / ⃝ sometimes / ⃝ never) undecidable.
8. Let L1 be a decidable language and L2 ⊆ L1. Then L2 is (⃝ always / ⃝ sometimes / ⃝ never)
decidable.
9. If A ≤T B and B is decidable, which of the following cannot be true? ⃝ A is decidable.
⃝ A is undecidable. ⃝ A is recognizable. ⃝ B ≤T A.
10. The complement of a recognizable language is (⃝ always / ⃝ sometimes / ⃝ never) recognizable.
11. The language
L = {⟨x⟩ : x is the name of a UMich student taking EECS 376 in Fall 2020}
⃝ Decidable and recognizable.
⃝ Undecidable and recognizable. ⃝ Undecidable and unrecognizable. ⃝ Decidable and unrecognizable. ⃝ None of the other choices apply.
12. Let S be an uncountable set of languages over {0, 1}. Let L ∈ S. Then L is (⃝ always / ⃝ sometimes / ⃝ never) decidable.
13. Consider the following function, which takes in non-negative integers a and b that are powers of two.
Which of the following functions can be used as a potential function to prove that the algorithm ALG halts on all valid inputs a, b?
⃝ None of these functions works as a potential function for ALG.
14. Let G be a connected, weighted graph with at least three edges and let T be an MST of G. Let G′ be defined by doubling the weight of the edge with the third-lowest weight in G, and let T′ be an MST of G′. In other words, G′ has all the same edges as G, except that the weight of the third-lowest weight edge is doubled. Then the weight of T ′ is (⃝ always / ⃝ sometimes / ⃝ never) higher than the weight of T.
1: function ALG(a,b)
2: if a=1orb=1ora=bthenreturn0
3: if a > b then return ALG(a/2, 2b)
4: if b > a then return ALG(2a, b/2)
15. Let T be a minimum spanning tree of a graph G. Construct G′ by adding a new vertex v to G and two edges (v, u) and (v, w) of weight 281 and 376, respectively, that connect to existing vertices u and w in G. Then T ∪ {(v, u), (v, w)} is (⃝ always / ⃝ sometimes / ⃝ never) a minimum spanning tree for the new graph G′.
True/False. Determine whether each of the following statements is true or false.
16. Define
M ult = {(a, b, c) : a · b = c}
MST = {(G,k) : G has a minimum spanning tree of size at least k}. Then,Mult≤T MST.
⃝ True ⃝ False
17. Recall that si = xi + yi is the potential function discussed in lecture for the Euclidean algorithm. The algorithm can also be shown to always terminate with a different potential function pi = xi ∗ yi.
⃝ True ⃝ False
18. Any graph with at least two edges of the same weight has more than one minimum spanning tree. ⃝ True
19. A diagonalization argument can be used to show that the set of all rational numbers is uncountable. ⃝ True
20. A Turing Machine with 1047 tapes can decide more languages than a Turing Machine with 29 tapes. ⃝ True
21. There exists a language that is Turing reducible to uncountably many languages. ⃝ True
⃝ False 22. The language
is decidable. ⃝ True
L = {x | x has at least as many 0s as 1s}
23. Use the Karatsuba algorithm on decimal (base-10) numbers to multiply the following numbers. Show all your work.
Version 1: 59 and 55. Version 2: 38 and 29. Version 3: 83 and 19. Version 4: 49 and 39. Version 5: 75 and 48.
24. Given a graph G = (V, E), we wish to compute an assignment of its vertices to values in {−1, 1}. In other words, we are computing a set of values S, where for each vertex v ∈ V , the value of S(v) can either be -1 or 1.
Version 1:
Version 2:
Let G = (V, E) be a weighed graph with a weight function w : E → Z. Note that w(e) is an integer, and it can be negative. The value of an assignment is defined as:
Val(S) = S(v)·S(u)·w(e) e=(u,v)∈E
In other words, edges e = (v,u) for which S(v) = S(u) contribute the weight w(e), while edges for which S(v) ̸= S(u) contribute weight −w(e).
Let G = (V,E) be a weighed graph with a weight function w : E → Z+. Note that w(e) is a positive integer. The value of an assignment is defined as:
V al(S) = 1 · |S(v) − S(u)| · w(e)
In other words, edges e = (v,u) for which S(v) = S(u) contribute the weight 0, while edges for
which S(v) ̸= S(u) contribute weight w(e).
Initially, let S(v) = 1 for all v ∈ V . Then consider the following algorithm that computes new values
(a) LetS(v)=1forallv∈V. (b) Repeat the following:
i. Foreachvertexv∈V:
A. Let S′ ← S (make a copy of S).
B. Set S′(v) = −S(v).
C. If V al(S′) > V al(S) then S ← S′ (replace S with S′).
ii. Continue as long as there exists a vertex v ∈ V such that setting S(v) = −S(v) increases the value; Stop otherwise.
(c) Return S.
Does there exist an input graph on which the algorithm loops, or will the algorithm halt on every input? Prove your answer. In addition, if the algorithm halts on every input, provide an upper bound, with justification, on the number of iterations as a function of V , E, and any other parameters of the problem.
25. Decidability.
Version 1:
In this question we model a line of people (e.g. at a supermarket checkout line, bank counter, etc.) as a binary string x ∈ {0, 1}∗. Each digit of x corresponds to a position in the line, and the digit is 1 if there is a person at that position or 0 if no one is at that position. We consider x to be socially distant if each occurrence of the digit 1 is at least six positions apart from any other occurrence of 1.
Examples of socially distant strings: • 000 – no occurrences of 1
• 100 – only one occurrence of 1
• 10000010 – the two occurrences of 1 are six positions apart
• 00100000000010000000000001000 – the occurrences of 1 are further than six positions apart
Examples of non-socially-distant strings:
• 11 – the occurrences are only 1 digit apart
• 0101 – the occurrences are only 2 digits apart
• 1000100000001 – there are two occurrences only 4 digits apart
For each of the following languages, state whether it is decidable or undecidable. If decidable, describe and analyze a program that decides it. If undecidable, prove that a language L is Turing reducible to it for some language L of your choice that we have previously shown to be undecidable.
i. LSocialDistance = {x ∈ {0, 1}∗ : x is socially distant}.
ii. LTuringSocialDistance = {⟨M⟩ : L(M) = LSocialDistance}.
For each of the following languages, state whether it is decidable or undecidable. If decidable, describe and analyze a program that decides it. If undecidable, prove that a language L is Turing reducible to it for some language L of your choice that we have previously shown to be undecidable.
i. LOnlyOnes = {x ∈ {0, 1}∗ : x consists only of 1’s}. ii. LTuringOnlyOnes = {⟨M⟩ : L(M) = LOnlyOnes}.
Version 2:
26. In this question we model a line of people (e.g. at a supermarket checkout line, bank counter, etc.) as a binary string x ∈ {0,1}∗. Each digit of x corresponds to a position in the line, and the digit is 1 if there is a person at that position or 0 if no one is at that position. We consider x to be socially distant if each occurrence of the digit 1 is at least six positions apart from any other occurrence of 1.
Examples of socially-distant strings:
• 000 – no occurrences of 1
• 100 – only one occurrence of 1
• 10000010 – the two occurrences of 1 are six positions apart
• 00100000000010000000000001000 – the occurrences of 1 are further than six positions apart
Examples of non-socially-distant strings:
• 11 – the occurrences are only 1 digit apart
• 0101 – the occurrences are only 2 digits apart
• 1000100000001 – there are two occurrences only 4 digits apart
For a given length n, we wish to determine how many binary strings of length n are socially distant.
(a) Let S(n) be the number of socially distant binary strings of length exactly n. Write base case(s)
and a recurrence for S(n), and give a brief explanation of your reasoning.
(b) State the asymptotic (big-O) running time, as a function of n, of a bottom-up dynamic program- ming algorithm based on your answer from the previous part. Briefly justify your answer. (You do not need to write down the algorithm itself.)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com