EECS 376: Foundations of Computer Science University of Michigan, Winter 2019
EECS 376 Practice Final Exam
Instructions:
This exam is closed book, closed notebook. You may not provide your own scratch paper, but the last
four pages are intentionally left blank for scratch work. No electronic devices are allowed (this includes
calculators, cellphones, etc). You may use one 8.5 × 11-inch study sheet written on both sides, as long as
you prepared it yourself. Check your seat assignment. Make sure you are taking the exam at the time slot
and the classroom you were assigned by the staff.
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.
The exam consists of 15 multiple choice questions, 5 short-answer questions, and 3 questions that require
proofs. You only need to answer two of the proof questions. No extra credit will be given if you answer all
three proof questions. For the multiple choice questions, please mark your answers neatly on the Scantron.
For the short-answer and proof sections, please write your answers clearly in the spaces provided. The exam
has 12 pages, including this page and the 3 blank pages at the end.
PLEASE DO NOT DETACH PAGES FROM THE EXAM. Failing to comply with this
requirement may result in grade deduction!
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.
Signature:
Name:
Uniqname:
Section Points
1-15 (Multiple Choice) / 30
16-20 (Short Answer) / 40
21-23 Pick two (Proof) / 30
Total / 100
EECS 376: Foundations of Computer Science University of Michigan, Winter 2019
Recall the following languages:
• LHALT = {〈M,x〉 : M halts on x}
• L = {x : x 6∈ L}
• SAT = {φ : φ is a satisfiable Boolean formula},
• Clique = {(G, k) : graph G has a clique of size k},
• Vertex-Cover = {(G, k) : graph G has a vertex cover of size k},
• Independent-Set = {(G, k) : graph G has a independent set of size k},
• Ham-Cycle = {G : graph G has a Hamiltonian cycle},
• k-Coloring = {G : graph G can be k-colored},
• Maze = {(G, s, t) : graph G has a path from vertex s to vertex t},
• Graph-Isomorphism = {(G1, G2) : graphs G1 and G2 are isomorphic},
• Graph-NonIsomorphism = {(G1, G2) : graphs G1 and G2 are not isomorphic},
• TSP = {(G, k) : weighted graph G has tour of weight at most k},
• Max-Cut = {(G, k) : graph G has a cut of size at least k}.
Remark: Unless otherwise specified, all the graphs are undirected.
Multiple choice (2 points each).
1. Which of the following statements is/are true?
A. Vertex-Cover ≤p Independent-Set
B. Clique ≤p SAT
C. SAT ≤p Vertex-Cover
D. A and B
E. A, B and C
2. In the process of generating shares for Shamir’s secret sharing scheme, the following polynomial is
created:
f(x) = 7 + 3x+ 20x2 + 2x3 + 3x4 + 4x5 (mod 23).
What is the minimum number of shares required to recover the secret?
A. 5
B. 6
C. 7
D. 23
E. Impossible to determine.
3. Use the above setup again. What is the secret?
A. 5
B. 6
C. 7
D. 23
E. Impossible to determine.
Page 2
EECS 376: Foundations of Computer Science University of Michigan, Winter 2019
True/False/Unknown (2 points each). True = A, False = B, Unknown = C
4. Clique is NP-Intermediate.
5. If SAT ∈ P, then P = coNP.
6. The Shortest Path problem is defined as follows: Given a weighted directed graph G = (V,E) with
weight function w : E 7→ R and a pair of vertices s, t ∈ V , determine the (weighted) length of the
shortest path between s and t. Then the Shortest Path problem has an efficient 376-approximation
algorithm.
7. Let A,B,C, and D be the outcomes of rolling 280-sided, 281-sided, 370-sided, and 376-sided fair dice,
where a k-sided not necessarily fair die gives the outcome between 1 and k with the uniform probability.
The following experiment is conducted: The 370-sided die is rolled twice, and the other dice are rolled
once. Let X be the sum of the outcome. Then E[X] = E[A] + 2E[C] + E[D] + E[B].
8. NP is countable.
9. LHALT ≤p SAT.
10. Let S376 be defined as S376 = {x : x is the name of an EECS 376 student in Fall 2018}.
Then SAT ≤p S376.
11. 281-Coloring ≤T 281-Coloring.
12. You are a student of Euclid in Ancient Greece. Your wise teacher has tasked you to travel between
each of the Greek islands and sell his prime numbers. He instructs you to visit each island only once
and then purchase the cheapest boat ride possible to an island you have not visited. Once you have
visited every island you will return home. Euclid asserts that this strategy will minimize the total cost
of your travels. His statement is (true/false/unknown).
Always/Sometimes/Never (2 points each) Always = A, Sometimes = B, Never = C.
13. (All / Some / No) NP-hard languages are undecidable.
14. (All / Some / No) unrecognizable languages are decidable.
15. (All / Some / No) languages in P are polynomial-time mapping reducible to
Graph-NonIsomorphism.
Page 3
EECS 376: Foundations of Computer Science University of Michigan, Winter 2019
Short Answer (8 points each)
16. Describe an algorithm that approximates the value of ln(2). You do not need to prove your algorithm
is correct. How many samples n would we need to approximate ln(2) to within absolute error ±0.03
with probability at least 90%? You do not need to simplify your expression for n.
Hint: See picture below.
Figure 1: A curve of y = 1(x+1) . Note that the area in the shaded region is
∫ 1
0
1
x+1dx = ln 2.
17. Prof. Volkovich is sending exam questions to the EECS 376 course staff. To ensure that the staff can
verify that the questions have not been altered, he uses a RSA-based signature scheme with n = 55
and public key e = 27. What would the signed message (m, s) be, if m = 52?
Page 4
EECS 376: Foundations of Computer Science University of Michigan, Winter 2019
18. Given an input string s and a pattern string p, a Wildcard Pattern Matching with support for ‘?’ and
‘*’ will return true if s and p are a match where,
• ‘?’ Matches any single character.
• ‘*’ Matches any sequence of characters (including the empty sequence).
There is only a Wildcard Pattern Matching if the matching covers the entire input string (not partial).
Note: s contains only lowercase letters a-z, and p contains only lowercase letters a-z, and characters
like ? or *. That is ? or * can only appear in p if at all. Here are some of correct input/output pairs
examples:
Inputs (s, p) Outputs Comments
(“aa”, “a”) false “a” does not match the entire string “aa”
(“aa”, “*”) true ‘*’ matches any sequence.
(“acdcb”, “a*c?b”) false
(“acdcb”, “a*cb”) true
Define WPM(i, j) as true if and only if there is a Wildcard Pattern Matching between s[1 · · · i] and
p[1 · · · j] and write the recurrence relation in this situation.
Hint: Recall that the Longest Common Subsequence algorithm relies on the following recurrence
relation: Let S1 and S2 be two strings that we want to find the longest common substring of, and
define LCS(i, j) as the length of the longest common substring between S1[1 · · · i] and S2[1 · · · j]. Then
LCS(i, j) =
{
LCS(i− 1, j − 1) + 1 if (S1[i] = S2[j])
max{LCS(i, j − 1), LCS(i− 1, j)} if (S1[i] 6= S2[j])
where we have ignored the base cases.
Adapt this recurrence relation to fit in an algorithm that would solve the following related problem.
Note: We do not need the full algorithm, just the analogous recurrence relation. You may also ignore
the base case.
Page 5
EECS 376: Foundations of Computer Science University of Michigan, Winter 2019
19. Given two languages A and B, prove that if A ≤p B and B ∈ NP, then A ∈ NP.
20. The Alan Company provides two different products: Cook’s coke and Karp’s soda. Alan claims that
he can tell them apart, since they taste different. However, Betty thinks these two drinks are entirely
identical. How can Betty test Alan’s claim?
Page 6
EECS 376: Foundations of Computer Science University of Michigan, Winter 2019
Proofs (15 pts each)
Please answer two of the following three questions. If you answer all of them we will pick two ar-
bitrarily to grade. Feel free to use the blank pages for your responses, but please clearly mark the
locations/continuations of your answers.
21. Suppose that you are a consultant for the Port Authority of a coastal city. Its profit is determined
almost entirely by how efficiently it can take away the contents of the ships that arrive in port. Here
is a basic model of the problem it faces.
A ship arrives with n containers having positive integer weights w1, . . . , wn. There are many trucks
near the port, each of which can hold some positive integer K units of weight (which is no less than
the container weights). A truck can hold any number of containers, as long as their total weight does
not exceed K. The goal is to minimize the number of trucks that are needed in order to carry away
all the containers. Unfortunately, it is well known that this problem is NP-hard.
Here is a candidate approximation algorithm:
1. for i = 1, 2, ..., n
2. if item i fits in the current truck, put it there
3. else
4. send the current truck away
5. start using the next available truck, putting item i in it
Example: Consider w1 = 3, w2 = 2, w3 = 2,K = 4. Observe that two trucks is optimal: we can put
item 1 on the first truck, and items 2 and 3 on the second truck. Note also that the above algorithm
yields this optimal allocation.
(a) Prove that in the above algorithm, every pair of adjacent trucks carries a combined weight of at
least K.
(b) Show that for any set of weights wi and any truck capacity K, the number of trucks used by
the above algorithm is at most twice the optimal number of trucks, i.e., the algorithm yields a
2-approximation.
Hint: for any weights wi and truck capacity K, we have OPT ≥ (
∑n
i=1 wi)/K.
Page 7
EECS 376: Foundations of Computer Science University of Michigan, Winter 2019
22. Consider the following language:
DOUBLE-SAT = {φ : φ is a Boolean formula with at least two satisfying assignments.}
Prove that DOUBLE-SAT is NP-complete. You may use any of the languages on the list at the top of
page 2.
Page 8
EECS 376: Foundations of Computer Science University of Michigan, Winter 2019
23. A dominating set for a graph G = (V,E) is a subset D ⊆ V of vertices such that every vertex not in
D is adjacent to at least one member of D. See example below.
Figure 2: An example of dominating set (shaded vertices).
The decision version of the problem is defined as follows:
DOM-SET = {(G, k) : graph G has a dominating set of size k}.
Suppose you have an efficient, black-box decider for DOM-SET. Design and analyze an efficient
algorithm that finds a dominating set of minimal size, given a graph G as input.
Page 9
EECS 376: Foundations of Computer Science University of Michigan, Winter 2019
This page is intentionally left blank for scratch work.
Page 10
EECS 376: Foundations of Computer Science University of Michigan, Winter 2019
This page is intentionally left blank for scratch work.
Page 11
EECS 376: Foundations of Computer Science University of Michigan, Winter 2019
This page is intentionally left blank for scratch work.