代写EECS 376 Final Exam, Winter 2025代写Python语言

EECS 376 Final Exam, Winter 2025

Multiple Choice:  Select the one correct option (12 points)

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

To select an option, fill in the entire bubble like this:  . Improper markings such as  and  may result in your response not being recognized.

(4 pts)   1.  Suppose there exists an NP-hard language that is not polynomial-time reducible to SAT.  Select

a correct conclusion about P and NP, if any, if the supposition is true.

    A       P = NP.

    B       P ≠ NP.

    C       No definitive conclusion can be drawn from this assumption.

    D       Such a language cannot exist.

(4 pts)   2.  Suppose you somehow obtained n, e, and (most importantly) ϕ(n) = (p - 1)(q - 1) from an

RSA system. You then use the Extended Euclidean Algorithm to find integers a, b such that ae + bϕ(n) = 1.  Suppose c is the ciphertext, select the expression that gives the original message.

    A       cφ(n) mod n

    B       ca mod ϕ(n)

    C       cb mod ϕ(n)

    D      ca mod n

O  E       cb mod n

(4 pts)   3.  Select the value of 399999933 mod 11.

    A       1

    B       3

    C       4

O  D       5

    E       9

Multiple Choice:  Select all valid options (30 points)

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.

A fully correct solution earns all 5 points. Each error (selection or non-selection) reduces your score by 2 points (to a minimum of 0 points).

To select an option, fill in the entire box like this:  . Improper markings such as  and  may result in your response not being recognized.

(5 pts)   4.  Recall from class that one critical ingredient in the proof of the Cook-Levin theorem is to specify which contents of the 2 × 3 “windows” of the verifier’s computation tableau are valid.  Consider the following Turing machine M over the input alphabet Σ = {1} and tape alphabet Γ = {1, ⊥}.

 

 

Select all the valid 2 × 3 windows for the tableau of M.

(5 pts)   5.  Consider the language

BIG-CLIQUE = {G : G = (V, E) has a clique of size (at least)  |V | − 1}.

Let L be a language.  Select  all statements that are  known  to be  necessarily  true regarding L.

□  A       If BIG-CLIQUE ≤p  L, then L is NP-hard.

口   B        If BIG-CLIQUE ≤p  L, then L ∈ NP.

口   C        If L ≤p  BIG-CLIQUE, then L ∈ NP.

口   D        If L ≤p  BIG-CLIQUE, then L ∈ P.

口   E        If L ≤p  BIG-CLIQUE, then L ∈ P.

(5 pts)   6.  For which of the following α values can we say that Kruskal’s algorithm gives an α-approximation

for finding the MST of a graph?  Select all that apply.

口   A       α = 0

口   B        α = 0.5

口   C        α = 1

口   D       α = 2

口   E        This statement cannot be applied to Kruskal’s algorithm.

(5 pts)   7.  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.

Suppose that Alice’s bit string is x = 010111 (23 in decimal) and Bob’s bit string is y = 101100 (44 in decimal). Select all the primes p for which the fingerprinting protocol fails on x and y.

口   A       2

口   B        3

口   C        5

口   D       7

口   E        11

(5 pts)   8.  Suppose you sort the array A[1,..., n], n > 1000, using QuickSort, choosing pivots uniformly at random.  Let Xi,j  be the indicator random variable for whether the ith and jth smallest elements are compared by the algorithm, and Yi  be the random variable denoting the number of comparisons involving the ith smallest element.  Select all true statements.

    A       There exists i < j such that E[Xi,j] = 0.01.

    B        Pr[Y1 = 1] = 0.

    C        For all i, E[Yi] = Θ(log n).

    D       E[X5,10] = 1/6.

    E        E[Y5] < E[Y10].

(5 pts)   9.  A k2  × k2  Sudoku puzzle consists of a k2  × k2  table T, partitioned into k2  boxes of size k × k , with some of the table cells already filled with integers.  A solution  is an assignment to the blank cells of T so that each row, column, and k × k box contains the integers {1,..., k2 }.  (Standard Sudoku is k = 3.) This problem is known to be NP-complete.

Consider the proposed zero-knowledge protocol for proving that a puzzle T has a solution.

Step 1.  Merlin privately writes a solution on the blank table cells of T, and covers up those

numbers with sticky notes. He shows the partially covered table to Arthur.

Step 2. Arthur chooses an arbitrary row, column, or k × k box (3k2  choices).

Step 3.  Merlin removes any sticky notes covering the row/column/box chosen by Arthur, who accepts if he sees the numbers {1,..., k2 } in that row/column/box.

In the example above, Arthur chooses the top right box in Step 2.

A zero-knowledge proof must satisfy several properties.  Select all the properties that this protocol satisfies.

    A       Completeness:  If T has a solution, Arthur accepts with certainty.

    B        Soundness: If T has no solution, any strategy of Merlin will cause Arthur to accept

with probability at most 1 − (1/3k2 ).

    C        Zero knowledge: When T has a solution, Arthur learns nothing beyond the fact that T has a solution.

    D       Efficiency:  Arthur runs in time polynomial in the size of T.

Short Answer (24 points)

(8 pts)  10.  Alice has announced her public RSA key to be (n, e) = (46, 5). Bob sends Alice an encrypted

message c = m5  mod 46 = 7. Unfortunately, Alice misplaced her private key information.  Show how she can nonetheless decode Bob’s message from the encoded message c = 7. Show your work in the box below:

Give the following quantities:

ϕ(n) =

d =

m =

(8 pts)  11.  Alice and Bob want to establish a shared secret key using Diffie-Hellman key exchange protocol. Both decided on a prime number p = 23 and a generator g = 5.  Suppose Alice picks a = 9 as her private key and receives B = 10 from Bob. Compute Alice’s message to Bob and their shared secret key.

Show your work in the box below:

Give the following quantities:

Alice’s message to Bob:

Shared secret key:

(8 pts)  12. You are given a sequence of n bar magnets placed in a line.  Each magnet is independently oriented as either NS (north-south) with probability 2/3 or SN (south-north) with probability 1/3.

Two magnets attract and stick together if the pole of one magnet that touches the next is opposite to the touching pole of its neighbor; otherwise, they repel and remain separate.  Magnets that are connected via attraction form a block—a maximal contiguous group of magnets stuck together. A magnet that does not attract either neighbor counts as a block by itself. In the example below, there are three blocks of magnets.

Find the expected number of resulting magnet blocks after all possible attractions occur in terms of n.

Hint: Each block either starts at a beginning of the line or starts at a repulsion point.

Show your work in the box below:

Give the final answer:

Expected number of magnet blocks (in terms of n):

Long Answer (34 points)

(17 pts)  13.  Consider the maximum  acyclic subgraph  (MAS) problem:  Given a directed graph G = (V, E), find a largest subset of edges E′  ⊆ E such that E′  contains no directed cycles.  This problem is known to be NP-hard, and we will analyze a randomized approximation algorithm for MAS.

Since any acyclic subgraph corresponds to some vertex ordering, a simple randomized strategy is to randomly permute  (order) the vertices and take all edges that go forward in this random order.  Formally, given a directed graph G = (V, E) with n vertices and m edges, we first generate a random permutation  (π(v1),...,π(vn)) for the vertices in V.  Then, we output E′ = {(u, v) ∈ E : π(u) < π(v)}, i.e., the set of edges oriented from a lower-indexed vertex to a higher-index vertex in the random order.

By inspection, this algorithm runs in O(n + m) time (for random sorting and scanning edges) and always produces an acyclic subgraph.

(a)  Show that the randomized algorithm obtains a 1/2-approximation for the MAS problem in expectation.

(b) Using Markov’s inequality, give a lower bound on the probability that the random- ized algorithm gives a 1/4 approximation for the MAS problem.

(c)  Using the randomized algorithm above, describe how we could produce an edge subset E′ that is a 1/4-approximation for the MAS problem with probability at least 0.9.  Briefly justify your answer.

(17 pts)  14.  A linear system of inequalities S consists of a collection of m linear inequalities over n variables x1 , . . . , xn  as follows:

a11x1 + a12x2 + ... + a1nxn  ≥ b1

a21x1 + a22x2 + ... + a2nxn  ≥ b2

.

.

.

am1x1 + am2x2 + ... + amnxn  ≥ bm ,

where aji’s and bj’s are constants.

A solution to a linear system is an assignment of values to x1 , . . . , xn  such that all inequalities are satisfied. We define ε xi  to be the penalty of the solution, and we often want to minimize it. This problem is known as linear programming.

Interestingly, if we restrict (x1,..., xn) to be an integer solution, i.e., xi  ∈ Z for all i, then the problem becomes significantly harder. Formally, we define the decision problem integer linear programming as

ILP = {(S, p) : S is a linear system that has an integer solution with penalty at most p}.

In this problem, you will show that ILP is NP-complete.

(a)  Briefly (in 2-3 sentences) explain why ILP ∈ NP.

(b)  Recall the language

VERTEX-COVER = {(G, k) : G is a graph with a vertex cover of size (at most) k}.

Show that VERTEX-COVER ≤p  ILP by defining a suitable polynomial time map- ping reduction f from VERTEX-COVER to ILP.  Since VERTEX-COVER is NP-hard, we can conclude that ILP is also NP-hard.

Defer the correctness proof to the next part, but briefly  (in  1-2 sentences) argue why your reduction is efficient here.

Hint: Create a variable for each vertex v.

(c)  Prove that your reduction in Part b is correct. Specifically, show that (G, k) ∈ VERTEX-COVER  ⇐⇒ f(G, k) ∈ ILP.