Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

EECS 376 Final Exam, Fall 2024

Multiple Choice: Select the one correct option (3 points each)

For each of the problems in this section, select the one correct option. Each one is worth 3 points; no partial credit is given.

(3 pts) 1. WINTER IS COMING. During an Ann Arbor winter, the expected fraction of days in which the temperature exceeds freezing (0 degrees Celsius) is only 1/3. A ‘mild’ winter is one in which the temperature exceeds freezing on at least 3/5 of the days.

Select the bound given by Markov’s Inequality on the probability of a mild winter in Ann Arbor.

⃝ Pr[mild] ≤ 5/9

⃝ Pr[mild] ≥ 4/9

⃝ Pr[mild] ≤ 1/5

⃝ Pr[mild] ≥ 4/5

(3 pts) 2. Consider the language

376-VC = {G : G is an undirected graph that has a vertex cover of size ≤ 376}.

Select the correct description of the following statement: 376-VC ∈ P.

⃝ The statement is known to true.

⃝ The statement is known to be false.

⃝ It is unknown whether the statement is true or false.

(3 pts) 3. Select the value of 7376482 mod 11.

⃝ 1

⃝ 3

⃝ 5

⃝ 7

Multiple Choice: Select all valid options (5 points each)

For each of the problems in this section, select all valid options; this could be all of them, none of them, or something in between.

For each option, a correct (non-)selection is worth one point. In addition, for each problem you will earn one additional point—for a total of five—if all four of your (non-)selections are correct.

(5 pts) 1. Select all the true statements.

□ Let V be an efficient verifier for L ∈ NP; if V (x, c) rejects for some certificate c, then x /∈ L.

□ If A ≤p B and there is no efficient algorithm that decides A, then there is no efficient algorithm that decides B.

□ Let V be an efficient verifier for language L ∈ NP, and let f be the corresponding polynomial-time mapping reduction from the Cook–Levin Theorem (showing that L ≤p SAT). Then f(x) chooses a certificate c, runs V (x, c), and generates a Boolean formula ϕ from its computation tableau.

□ If A ≤p B and B ≤p C, then A ≤p C.

(5 pts) 2. Select all the statements that are known to imply a resolution of the P-versus-NP question (regardless of the outcome).

□ CLIQUE ∈ P

□ CLIQUE ∈/ P

□ {0 k1 k : k ≥ 0} is NP-complete

□ There is an efficient (non-quantum) algorithm for factoring integers

(5 pts) 3. Select all the true statements.

□ In randomized Quicksort, all pairs of elements in the input array are equally likely to be compared at some point during a run of the algorithm.

□ Randomized Quicksort on an n-element array runs in expected time O(n log n) when the input list is in random order, but the expected runtime is larger for worst-case input.

□ In a skip list of n elements, the memory used by the structure is O(n) with probability at least 99%.

□ When searching a skip list, the expected number of items accessed on any single level is a constant that does not depend of the total number of elements in the structure.

(5 pts) 4. Recall the fingerprinting protocol from class, which allows Alice and Bob to test equality of their respective n-bit strings x, y (which are interpreted as integers).

1. Alice chooses p uniformly at random from the first 10n primes, then sends (p, f = x mod p) to Bob.

2. Bob accepts if f ≡ y (mod p), and rejects otherwise.

Select every change to the above protocol that would decrease the probability that Bob wrongly accepts when x = y, while retaining O(log n)-bit communication.

□ Choose p uniformly at random from the first 100n primes.

□ Choose p uniformly at random from the first 20n primes larger than x.

□ Choose a prime p such that the difference |p − x| is minimized, thus reducing the number of prime factors of |p − x|.

□ Run the protocol k times with independently chosen primes, for some constant k > 1.

(5 pts) 5. Select all the true statements.

□ If there is an efficient algorithm that solves the discrete logarithm problem, then the Diffie–Hellman protocol is insecure against an efficient eavesdropper.

□ In the RSA protocol with public modulus n = p · q (for distinct primes p, q), it is insecure to reveal the value ϕ(n) = (p − 1)(q − 1).

□ If P = NP, then both the Diffie–Hellman and RSA protocols can be broken by efficient (non-quantum) algorithms.

□ Merlin has discovered a group of half of Arthur’s “Knights of the Round Table” in which every pair of Knights are enemies of each other. Arthur knows which individual pairs of Knights are enemies, but is skeptical of Merlin’s claimed discovery. Merlin can convince Arthur of this claim without revealing anything about which Knights are in the group.

Short Answer (points vary)

1. Alice’s RSA public key consists of modulus n = 33 and exponent e = 7.

(4 pts) (a) Fill in the blank: Alice’s private key (exponent) is d =              .

(4 pts) (b) Suppose Bob sends Alice the ciphertext c = 8. Then the message is m =           .

(6 pts) 2. Recall the decision version of the independent set problem:

IS = {(G, k) : G is an undirected graph that has an independent set of size (at least) k}.

In this problem, suppose that there is an efficient algorithm (or oracle) D that decides IS. The following incomplete algorithm uses D to efficiently solve the search version of independent set, which is: given an undirected graph G, output an independent set in G of maximum size. Fill in the blanks in the pseudocode to make the algorithm correct and efficient. You do not need to justify these answers.

1: function FindMaxIndependentSet(G = (V, E))

2: for i = 0, 1, . . . , |V | do // find the size of a maximum independent set

3: if D(G, i) accepts then

4: k = i

5: for each v ∈ V do

6: let G′ =

7: if                         then

8: G =

9: return V (G), i.e., the set of vertices in G

3. Professor Υ has just learned about the language

Double-SAT = {ϕ : ϕ is a Boolean formula that has at least two satisfying assignments}.

Υ suspects that this language is NP-hard, and has even proposed two polynomial-time mapping reductions (PTMRs) from SAT that might prove this. However, it is wise to be skeptical of Υ’s enthusiasm.

For each of Υ’s proposed reductions (described below), state whether it is a correct PTMR from SAT to Double-SAT.

If it is not correct, give a small counterexample (with justification) to the correctness requirement.

If it is correct, just say so; do not provide justification.

(6 pts) (a) This reduction outputs the AND of two copies of the input formula, where in the second copy, all the variables are consistently renamed as new variables.

For example, the formula ϕ = (x1∧x2)∨x1 is mapped to ϕ ′ = ((x1∧x2)∨x1)∧((y1∧y2)∨y1). Observe that in ϕ ′ , each variable xi in the second copy of ϕ has consistently been replaced by yi .

(6 pts) (b) This reduction, on input formula ϕ, outputs ϕ ′ = ϕ ∧ (z ∨ z), where z is a new variable that doesn’t appear in ϕ.

For example, the formula ϕ = (x1 ∧ x2) ∨ x1 is mapped to ϕ ′ = ((x1 ∧ x2) ∨ x1) ∧ (z ∨ z).

(8 pts) 4. Kermit the Frog is looking forward to a relaxing afternoon jumping from lily pad to lily pad, catching flies. (He never revisits any—these are ‘one-time pads’!)

Each lily pad he jumps on has probability p ∈ [0, 1], independently of all the others, of being unable to hold his weight and submerging under the water; otherwise, it stays afloat.

• If Kermit is dry and jumps on a lily pad that submerges, he becomes wet, and remains wet for as long as he jumps on pads that submerge.

• Similarly, if Kermit is wet and jumps on a lily pad that stays afloat, he becomes dry, and remains dry for as long as he jumps on pads that stay afloat.

Starting on land, where Kermit is already dry, he jumps on n lily pads in sequence.

Derive, with justification, the expected number of times Kermit becomes dry, in terms of p and n, via suitably defined indicator random variables.

For example: suppose that Kermit jumps from land to a pad that submerges, to one that stays afloat (where he becomes dry), to one that stays afloat, to one that submerges. In this case, he becomes dry exactly once.

Hint: Consider what must happen for Kermit to become dry on the ith lily pad.

Long Answer (16 points each)

1. Let S be a set and C = (C1, . . . , Cm) be a collection of subsets Ci ⊆ S.

A subset H ⊆ S is a hitting set of the collection C if H has at least one element from every Ci , i.e., H ∩ Ci = ∅ for every i = 1, . . . , m. In other words, H ‘hits’ every subset in the collection.

This question is concerned with the problem of minimizing the size of a hitting set, which is captured by the following language:

HITTING-SET = {(S, C, k) : collection C has a hitting set H of size |H| ≤ k}.

(4 pts) (a) Briefly justify (in 2-3 sentences, without pseudocode) why HITTING-SET ∈ NP.

(6 pts) (b) Toward proving that HITTING-SET is NP-hard, define a polynomial-time mapping reduction from the NP-hard language VERTEX-COVER to HITTING-SET, and briefly argue that it is efficient. (Do not prove correctness; you will do that in the next part.) Recall that

VERTEX-COVER = {(G, k) : undirected graph G has a vertex cover of size ≤ k}.

(6 pts) (c) Prove that your reduction from the previous part is correct.

2. Given a collection T = (t1, . . . , tn) of non-negative numbers ti ≥ 0, our goal is to partition it into some X and Y = T \ X that so that the largest of their sums is minimized.

We assume that the elements of T sum to 1, by rescaling them if necessary. Define the value of a partition X, Y to be max{s(X), s(Y)}, where s(U) = P u∈U u denotes the sum of any collection of numbers U. Note that s(Y) = 1 − s(X).

Finding a partition with the minimum possible value is an NP-hard problem (in its decision version), so we instead seek an approximation algorithm.

Assume that the numbers in T are sorted in descending order, i.e., ti ≥ ti+1 for all i. Consider the following greedy algorithm:

• Start with empty X, Y = ∅.

• For i = 1, . . . , n: place ti into whichever of X or Y has the smallest current sum (breaking ties arbitrarily).

• Output X, Y .

For example, if the input is T = (.25, .25, .2, .2, .1), then a possible output of the algorithm is X = (.25, .2) and Y = (.25, .2, .1), which has value .55. An optimal partition for this input is X = (.25, .25) and Y = (.2, .2, .1), which has value .5.

In this problem you will show that the above algorithm obtains a certain approximation factor (on any input). You may use the following notation and observations, which are without loss of generality.

1. Let X, ˆ Yˆ denote the partition output by the algorithm. So, s(Xˆ) + s(Yˆ) = 1.

2. Assume that s(Yˆ) ≥ s(Xˆ), so the value of the output partition is just s(Yˆ). (Otherwise, we can just flip all the algorithm’s decisions, by symmetry.)

3. Assume that s(Yˆ) > t1, because the optimal value is at least t1. So, if s(Yˆ) ≤ t1 then the algorithm’s solution is optimal, and there is nothing to prove.

Answer the three parts on the next page. The answers do not rely on each other, so you may work on the parts in any order.

(6 pts) (a) Suppose that t1 ≥ 1/3. Prove that s(Yˆ) ≤ 2/3 (or equivalently, s(Xˆ) ≥ 1/3).

Hint: Consider the two cases where the algorithm places t1 in either X or Y , and use the abovee assumption that s(Yˆ) > t1.

(6 pts) (b) Now suppose that t1 < 1/3, and prove that s(Yˆ) ≤ 2/3 in this case as well.

Hint: Consider how much s(X) and s(Y) can differ from each other throughout the execution of the algorithm.

(4 pts) (c) Prove that the above is an α-approximation algorithm for the smallest value of α ≥ 1 you can manage, by giving a lower bound on the value OPT of an optimal solution, and using the conclusions from the previous parts.