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

EECS 376: Foundations of Computer Science

EECS 376 Final Exam, Fall 2023

Questionnaire (NOT GRADED)

Answers to these questions will have no impact on your exam grade or final grade.

1. The percentage of lectures that I attended is roughly:

 0-20%.

 20-40%.

 40-60%.

 60-80%.

 80-100%.

2. What class resources did you routinely use? (Mark all that apply.)

 Live Lectures

 Recorded Lectures

 Discussion Sections

 Piazza

 Office Hours

 Course Notes on eecs376.org

Multiple Choice — 6 Points Each

In all multiple choice questions, fill in all correct boxes and no incorrect boxes.

1. Which of the following languages are guaranteed to be in NP?

 L1 ∩ L2, where L1 ∈ NP and L2 is NP-complete.

 L, where it is known that L 6∈ P.

 L, where L ≤T LHALT, where LHALT = {hM, xi | TM M halts on input x}.

 L1 ∪ L2, where L1 and L2 are both in NP.

 L, where L ∈ NP.

2. Suppose language A is NP-Complete and language B = {x ∈ {0, 1}* | x is a palindrome}. Which of the following are true?

 If B ≤p A then P = NP.

 If A ≤p B then P = NP.

 A ≤T B.

 B ≤T A.

3. Suppose an O(m2 )-time algorithm is discovered that, given a boolean 3CNF formula φ with n variables and m clauses, returns a satisfying assignment, if there is one. What are the guaranteed consequences of this? (MAX-CLIQUE is the problem: given G = (V, E) to find the largest U ⊆ V such that U forms a clique in G.)

 There is an O(N2 )-time algorithm for every problem in NP, where N is the length of the input.

 L = {x ∈ {0, 1}* | x = 0n1 n for some n ≥ 0} is NP-complete.

 P = NP.

 There is an efficient 99/100-approximation algorithm for MAX-CLIQUE.

 The Diffie-Hellman protocol can be broken in polynomial time.

4. Suppose A is a 1/2-approximation algorithm for the MAX-CLIQUE problem. Then

 A(G) is guaranteed to return a clique in G of size n/2 if such a clique exists, where G = (V, E) and |V | = n.

 A(G) is guaranteed to return a clique of at least twice the maximum clique in G.

 A(G) is guaranteed to return a clique of size at least half the largest clique in G.

 A(G) always returns a larger clique than what a 1/4-approximation algorithm for MAX-CLIQUE would return.

5. Which of these decision problems is in the set NP?

 Given a graph G, decide if it has a vertex cover of size k.

 Given a set of distinct integers, decide if they can be partitioned into three sets with the same sum.

 Given a prime p, a generator g, and t ∈ {1, . . . , p − 1}, decide if the integer i ∈ {1, . . . , p − 1} with g i ≡ t (mod p) is even.

 Given two integers p, q, decide whether their greatest common divisor is less than 10.

 Given a Turing machine M, decide if it halts when the input is the empty string.

Short Answer — 11 Points Each

1. Alice and Bob agree on the prime p = 17 and generator g = 6, and wish to establish a shared secret key k using the Diffie-Hellman protocol. Suppose Alice privately chooses a = 3 and Bob privately chooses b = 12. What is Alice’s message to Bob? What is Bob’s message to Alice? What is the secret key k?

Solution: Write all calculations clearly for partial credit:

All three answers should be integers in {1, . . . , 16}.

Alice’s message to Bob:      Bob’s message to Alice:      The Shared Secret k

2. Alice uses modulus n = 65 and RSA public key e = 29. Determine a possible private key d and calculate Alice’s RSA-signature for the message m = 3.

Solution: Write all calculations clearly for partial credit:

Private key d (in {1, . . . , 64}):      Signature for message m = 3 (in {1, . . . , 64}):

Long Answer — 12 Points Each

1. In the EQUITABLE-SAT problem we are given a list of clauses φ = (C1, C2, . . . , Cm), where each clause Cj is a list of exactly 4 literals involving 4 distinct variables, say (x, y, w, z). Given an assignment, we say that a clause is equi-satisfied if it contains equal numbers of true and false literals. For example, if x, y, w are true and z is false, (x, y, w, z) would not be equi-satisfied because it contains one true literal and three false ones.

Give a randomized approximation algorithm for finding an assignment to the variables that, in expec-tation, equi-satisfies a constant fraction ρ ∈ [0, 1] of the clauses. Analyze what ρ is exactly. Give a lower bound on the probability that your algorithm satisfies at least a ρ/2-fraction of the clauses, using Markov’s inequality.

Solution: Write all calculations and reasoning:

ρ =      Probability at least ρ/2-fraction are satisfied

2. SecureCo sells software to produce RSA keys. Every time you run SecureCo’s KeyGen() procedure it randomly generates a tuple (n, e, d), where n = p · q, de ≡ 1 (mod φ(n)), and p and q are 512-bit primes. Unfortunately there is a subtle flaw in the code of KeyGen(): p is a fixed 512-bit prime number, and q is a random 512-bit prime number. (Although p is fixed, you do not know what it is.)

Suppose Alice uses KeyGen() to produce (n, e, d) and publicly announces (n, e), while Bob uses KeyGen() to produce (n', e', d') and publicly announces (n', e'). Explain how to efficiently decode any encrypted message that you intercept, which was encrypted with (n, e). You may assume n ≠ n' . Recall that if n = pq, φ(n) = (p − 1)(q − 1).

Solution: