EECS 376 Midterm 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.  Consider the following algorithm that takes in an array of integers as input.

1: function Mystery(A[1..n])

2:         Initialize table[1..n] to all 0s

3: for i = 1 to n do

4: if A[i] > 10 then

5:                     table[i] = A[i]

6: else

7:                    table[i] = maxj

8: return table[n]

Select the worst-case running time of Mystery.

A    Θ(n)

B    Θ(n · i)

C    Θ(nlog n)

D Θ(n2)

E Θ(2n)

(4 pts)   2.  Consider the reachibility problem for a directed graph G = (V, E).  Let r[i](s, t) be the truth value indicating whether there exists a path from s to t whose internal vertices are in the set {v1,..., vi}, with base cases

Select the correct way to complete the recursive formulation of r[i](s, t) =

A    r[i-1](s, vi) ∨ r[i-1](vi, t)

B    r[i-1](s, vi) ∧ r[i-1](vi, t)

C    r[i-1](s, t) ∨ (r[i-1](s, vi) ∧ r[i-1](vi, t))

D    r[i-1](s, t) ∧ (r[i-1](s, vi) ∨ r[i-1](vi, t))

(4 pts)   3.  Consider the following DFA over alphabet Σ = {a, b}.

Select the language decided by the DFA above.

A    {s ∈ Σ*  : s starts with a b or contains at least one b.}

B    {s ∈ Σ*  : s starts with a b or every a is followed by at least one b.}

C    {s ∈ Σ*  : s contains an even number of a’s or ends with a b.}

D    {s ∈ Σ*  : s contains an even number of a’s or contains at least one b.}

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.  Consider an algorithm that solves an instance of size n by recursively solving two sub-instances of size n/2.  Suppose the time needed to combine the results of the recursive calls is Ω(n) and O(n2 ). Select all possible asymptotic running times of this algorithm.

A    Θ(n)

B    Θ(nlog n)

C    Θ(n1.5)

D Θ(n2)

E Θ(n2 log n)

(5 pts)   5.  Suppose that algorithm X has worst-case running time TX(n) = n2  + n and Algorithm Y has worst-case running time TY(n) = 10n「log2n⌉ .  That is, TX(n) is the maximum number of steps for which X runs, taken over all inputs of size n (and similarly for TY).

Select all statements that are necessarily true about the two algorithms.

A    We can upper bound the running time of Y by O(n log10n).

B    On every input, Y runs faster than X .

C    On every large enough input, Y runs faster than X .

D    For all large enough n, there is an input of size n for which Y runs faster than X .

E    There is an n such that for every input of size exactly n, Y runs faster than X .

(5 pts)   6.  Select all true statements about Kruskal’s algorithm and minimum spanning trees (MSTs).  In

all parts you may assume the given graph G = (V, E) is connected.

A    If (u, v) ∈ E is the unique minimum weight edge incident to u, it is in every MST.

B    If a graph has a negative-weight cycle, then any MST must contain all edges in that cycle.

C    The heaviest edge in the graph is not in any MST.

D    If Kruskal’s algorithm adds an edge e to its growing tree, then there is some MST that contains e.

E    Any graph with at least two edges of the same weight has more than one MST.

(5 pts)   7.  Select all of the decidable languages.

A L1 = {(⟨M⟩, x, n) : M is a TM such that M halts on x within n steps}

B L2 = {(⟨M⟩, x) : M is a TM and ∃n ∈ N such that M halts on x within n steps}

C L3 = {⟨M⟩ : M is a TM and M decides the halting problem}

D L4 = {(⟨M1⟩, ⟨M2⟩) : M1  and M2  are TMs that decide the same language}

E L5 = {(⟨M1⟩, ⟨M2⟩) : M1  and M2  are TMs and ⟨M1⟩ = ⟨M2⟩}

(5 pts)   8.  Select each hypothesis that implies that L is decidable.

A    L is the complement of an undecidable language.

B    L = A ∪ B, and at least one of A, B is decidable.

C    L ⊆ A, and A is decidable.

D    A ≤T  L, and A is decidable.

E    L ≤T ∅ .

(5 pts)   9.  Consider the set of all languages LΣ over an  alphabet  Σ = {a}  (Σ consists of one character ‘a’).

Select all true statements regarding LΣ .

A    There exists an L ∈ LΣ  that is countable.

B    There exists an L ∈ LΣ  that is uncountable.

C    There exists an L ∈ LΣ  that is infinite and decidable.

D    There exists an L ∈ LΣ  that is undecidable.

E    LΣ is uncountable.

Short Answer (24 points)

(6 pts)  10. You are observing a highly unstable process unfolding in a chaotic energy field. The process involves two types of particles:  maize and blue.  In each time unit, one of the following reactions must occur at random:

• Fusion: Two maize particles combine to form one blue particle.

• Decay: One blue particle destabilizes and transforms into one maize particle. The process halts if no more reactions are possible.

(a)  Let b and m be the number of blue and maize particles. Give  a potential function s(b, m) that can be used to prove that this process eventually halts. s(b, m) =

(b) Briefly (in 2-3 sentences) explain why your answer in Part a works.

(4 pts)  11. Compute gcd(144, 84) using Euclid’s algorithm. Give the arguments of each recursive call:

Give the final answer:

(6 pts)  12.  Suppose you are running Karatsuba’s algorithm on the base-10 representations of 2030 × 3760. State the pairs of numerical arguments that will be passed to the three recursive calls for this computation. You may give them in any order, and no justification is needed.

Karatsuba(                         ,                         )

Karatsuba(                         ,                         )

Karatsuba(                         ,                         )

(8 pts)  13.  You are in charge of taking pictures of cats at the local shelter.  Each cat is brought out exactly once to play in the shared area at pre-decided times.  You want to take the fewest pictures possible, while ensuring that you get at least one picture with each cat in it.

We use the following greedy algorithm:

1: function GreedyPictures(X) // X is a set of time intervals when each cat is there

2:         Sort X by the end times in increasing order

3:         Initialize I ← ∅ // the set of times to take pictures

4: while X is not empty do

5:               Let [ℓ, r] be the first interval in X

6:                I ← I ∪ {r}  // Add the time when this cat is leaving to I

7:               Remove all intervals [ℓ′ , r′] from X where ℓ′ ≤ r // Remove covered intervals

8: return I

By inspection, GreedyPictures ensures that every cat is photographed at least once. Com- plete the following proof that it does so optimally, i.e., using the minimum number of pictures. Fill in each blank with 1-2 sentences.

• Let ALG be the sequence of times the algorithm proposes to take pictures, and let OPT be an arbitrary optimal sequence of picture times, both sorted in increasing order.

• If ALG = OPT, then ALG is optimal.  So now suppose otherwise.

• Then for some k ≥ 1, OPT and ALG agree on the first k-1 chosen photo times

ALG[1] = OPT[1], ..., ALG[k-1] = OPT[k-1], but not on the kth choice: ALG[k] OPT[k].

(a) ALG[k] cannot be less than OPT[k] because:

• Thus ALG[k] > OPT[k].

• Let OPT′ = OPT \ OPT[k] ∪ ALG[k], which has the same  (optimal) number of photo times as OPT. We now need to show that OPT′ takes a picture of every cat.

(b) All cats who left before the time ALG[k] are photographed in OPT’ because:

• All cats who were present at time ALG[k] are photographed in OPT’ because OPT’ took their picture at time k.

(c) All cats who arrived after time ALG[k] are photographed in OPT’ because:

Long Answer (34 points)

(11 pts)  14.  A Mars rover is moving on a flat surface partitioned as a 2D grid. It receives instructions from the set Σ = {F, L, R}, which correspond to moving forward 1 unit, turn left 90◦ , turn right 90◦ , respectively. The rover starts at the origin (0 , 0) and receives an instruction string x ∈ Σ* .  Let LORIGIN  be the language of all instruction strings x ∈ Σ*  that return the rover to the origin. For example, ε, RR and FFRFRFRFLF are all in LORIGIN .  (See the diagram below.)

Prove that no DFA can decide the language LORIGIN .

(11 pts)  15.  SpongeBob is on a quest in the Krusty Krab Treasure Hunt, exploring an underwater labyrinth to collect Barnacle Coins.  However, Squidward, begrudgingly joins the journey, trying to keep the haul as small as possible.

We formally model this problem as follows. The network of rooms is given by a directed  acyclic graph  (DAG) G = (V, E), with:

• n vertices V = {1,..., n} representing each room

• m directed edges (i,j) ∈ E represent a (one-way) door from room i to room j.

•  Let the vertices be in “topological order,” so every door goes from a lower numbered room to a higher numbered room. For each edge (i,j), we have i < j

• Additionally, for each vertex i there is an integer number of coins ci  ≥ 0 the group would collect in room i.

SpongeBob and Squidward both have the map of the entire labyrinth, including the number of coins in each room. Starting at room 1, they take turns choosing the next room to enter, with SpongeBob choosing first. The total coins collected is the sum of coins in all rooms visited. The treasure hunt ends upon reaching a room with no outgoing doors.

SpongeBob wants to maximize the total coins collected, while Squidward wants to mini- mize it.

(a)  Patrick suggests that SpongeBob should always pick the room with the most coins during his turns, while Squidward should always pick the room with the least coins on his turns. Find both the number of coins earned if both of them followed Patrick’s strategy and the number of coins if both picked optimally for the following Labyrinth:

Start: Room 1

In the above graph, the  number of coins  in each room is given in a box next to the room.

Patrick’s greedy strategy:

Both pick optimally:

(No justification is needed for either answer.)

(b)  Now consider the general problem defined above (putting aside the specific graph from the previous part).

Define T(i) to be the maximum total coins SpongeBob would be guaranteed to collect, regardless of Squidward’s choices, if starting the treasure hunt from room i.

Give a recurrence relation for T(i), including base case(s), that is suitable for a dynamic-programming solution to the problem. No justification is needed.

(c)  Suppose you were to write a dynamic programming algorithm to compute these T(i) values. Describe the correct order to compute them. You do not need to give the full algorithm.

(12 pts)  16.  Given two Turing machines M1  and M2  and a string x, we say that M1   disagrees  with M2  on

input x if one of them accepts x, while the other rejects or loops on x.

Define the language

LDISAGREE  = {(⟨M1⟩, ⟨M2⟩) : M1  disagrees with M2  on all inputs} .

(a)  Recall that LACC  = {(⟨M⟩,x) : M is a Turing machine and M accepts x} . Show that LACC ≤T   LDISAGREE by giving a Turing reduction.   Defer  the  correctness argument of your reduction to the next part.

Hint: You may need to construct Turing machine(s) within a Turing machine.

(b) Give a correctness argument for your reduction in (a). Since LACC  is undecidable, we can conclude that LDISAGREE  is undecidable.