闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

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

EECS 376 Midterm 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. Consider the following algorithm.

1: function FloorCubeRoot(n) // n is a non-negative integer

2: for i = 0, 1, 2, . . . do

3: if i3 > n then return i - 1

Select the one correct option that describes the algorithm’s running time, and whether it is “efficient” according to the definition used in this class.

⃝ O(log3n) iterations, efficient

⃝ O(n1/3 ) iterations, efficient

⃝ O(n1/3 ) iterations, not efficient

⃝ Unbounded running time (possibly infinite), not efficient

(3 pts) 2. Select the one false statement about DFAs and Turing machines (TMs).

⃝ Every DFA decides a language.

⃝ Every DFA and every TM has a finite number of states.

⃝ If a TM writes to any cell(s) beyond those where its input string was written, then it loops (does not halt) on that input.

⃝ Every state of a DFA must have a transition rule for every symbol in the DFA’s alphabet.

(3 pts) 3. Suppose that A ≤T B. Select the one option that is not possible.

⃝ Both A and B are decidable

⃝ Both A and B are undecidable

⃝ A is decidable, and B is undecidable

⃝ A is undecidable, and B is decidable

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 decidable languages.

□ L0 = {⟨M⟩ : M is a TM and L(M) is recognizable}

□ L1 = {⟨M⟩ : M is a TM that does not accept “eecs376”}

□ L2 = {⟨G⟩ : G is a weighted graph whose spanning trees all have weight ≥ 50}

□ L3 = {⟨D⟩ : D is a DFA with at least 10 states}

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

□ If a language L is decidable, then every subset of L is decidable.

□ If a language L is undecidable, then there is no Turing machine whose language is L.

□ If a language L is undecidable then there is some string in L that no Turing machine accepts.

□ If a Turing machine M recognizes language L and decides language L′ , then L = L′ .

(5 pts) 3. Select every cardinality that an undecidable language could possibly have.

□ 0 (empty)

□ finite

□ infinite but countable

□ uncountable

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

□ If p is the unique shortest s-to-t path in a graph—i.e., every other s-to-t path has strictly larger length—and v is a vertex on p, then the s-to-v portion of p is the unique shortest s-to-v path in the graph.

□ In the Floyd–Warshall recurrence, the values d[i](s, t) are non-increasing as i increases, i.e., d[j](s, t) ≤ d[i](s, t) for all j ≥ i and all vertices s, t.

□ If a graph has no negative-weight cycle, then no shortest path in the graph contains a cycle.

□ To fill each individual entry of the DP table in the Floyd–Warshall algorithm, we need to look at only a constant number of cells, whereas this may not be the case in the Bellman–Ford algorithm.

(5 pts) 5. Recall that the following language is undecidable:

Lε-HALT = {⟨M⟩ : M is a TM and M(ε) halts} .

Say that a Turing machine T is wrong on input ⟨M⟩ if:

• T(⟨M⟩) rejects or loops when ⟨M⟩ ∈ Lε-HALT , or

• T(⟨M⟩) accepts or loops when ⟨M⟩ Lε-HALT .

Select all the true statements.

□ Every Turing machine is wrong on every input ⟨M⟩ .

□ Every Turing machine loops on at least one input ⟨M⟩ .

□ Every Turing machine is wrong on infinitely many inputs ⟨M⟩ .

□ Every Turing machine is wrong on at least one input ⟨M⟩ .

(5 pts) 6. Select all the hypotheses that imply that L is recognizable.

□ L is the complement of a decidable language.

□ L = A ∩ B, and both A and B are recognizable.

□ L ⊆ A, and A is decidable.

□ L ≤T A, and A is recognizable.

Short Answer (points vary)

1. Consider a one-player game involving a pile of red and white chips. Initially, there is a finite number of each color of chip. The player repeatedly takes a “turn” until no chips remain in the pile, if this ever happens.

In each turn, the player must remove one chip of its choice from the pile, and if the removed chip is red, the player may add up to four white chips to the pile.

(1 pt) (a) State (yes or no) whether the game must eventually end, regardless of the initial

number of each type of chip and how the player plays:

(You will justify your answer in the next part.)

(4 pts) (b) If your answer is ‘yes’: prove it by defining and briefly analyzing a potential

function in terms of the number of each type of chip.

If your answer is ‘no’: give an initial (finite) number of each type of chip, and describe how the player can play, to make the game continue forever.

(4 pts) 2. Compute gcd(98, 56) using Euclid’s algorithm.

Specifically, give the arguments of each recursive call, as well as the final output. (You do not need to show any work beyond this.)

(5 pts) 3. Give the state-transition diagram of a DFA having at most 5 states, with alphabet

Σ = {a, b, c}, that decides the language of strings that have abc as a subsequence.

As a few examples, the DFA should accept the strings abbc, abc, and abbaaaca, and reject the strings ε , cba, and acacb.

4. Suppose you are choosing among the following three algorithms for a particular problem.

A. Algorithm A solves an input of size n in worst-case running time O(n3 ).

B. Algorithm B solves an input of size n by recursively solving two subinputs of size n - 1 and then combining the solutions in O(1) time.

C. Algorithm C solves an input of size n by recursively solving nine subinputs of size n/3, then combining the solutions in O(n2 ) time.

The base cases of Algorithms B and C both take O(1) time.

(4 pts) (a) State the tightest correct big-O bounds on the running times of Algorithms B

and C. (You do not need to provide any justification.)

Algorithm B: Algorithm C:

(3 pts) (b) Professor Υ considers this information and declares:

“On all inputs larger than some fixed threshold, Algorithm C is the fastest of the three!” Briefly give one reason why this conclusion is unfounded.

5. Along a hallway of an art gallery, n paintings are located at positions p1 ≤ p2 ≤ · · · ≤ pn , where pi is the position of the ith painting. A guard placed at position g will protect all paintings within unit distance, i.e., in the closed interval [g - 1, g + 1]. We want to place guards so that every painting is protected by at least one guard, using as few guards as possible.

We use the following greedy algorithm.

1: for i = 1, . . . , n do

2: if the ith painting is not protected by the existing guards then

3: place an additional guard at pi + 1 // largest position that protects ith painting

S By inspection, the algorithm protects all the paintings. We now claim that it does so optimally, i.e., using the fewest possible number of guards. The structure of the proof is as follows.

1. Let OPT, a set of guard locations, be an arbitrary optimal solution.

2. If the algorithm’s output is a subset of OPT, the claim holds. So now suppose otherwise.

3. Then for some k ≥ 1, OPT contains the algorithm’s first k - 1 chosen guard positions g1 < g2 < ··· < gk-1, but not the algorithm’s kth choice gk .

4. In this problem you will show that there is another optimal solution OPT′ that contains g1 , . . . , gk, by exchanging out a suitable h ∈ OPT for gk .

The claim ultimately follows by repeating Steps 2–4 of the argument (formally, via induction). Answer the parts of this problem that appear on the next page.

(4 pts) (a) We choose to exchange out an h ∈ OPT for which gk-1 < h ≤ gk . By convention, g0 = -∞

(when k = 1).

Briefly justify (in a few sentences) why OPT must have such an h.

(3 pts) (b) Clearly, OPT′ = OPT ∪ {gk} \ {h} has the same cardinality as OPT. So it just remains to

show that OPT′ is a valid solution, i.e., that it protects all the paintings.

Briefly justify that OPT′ protects all the paintings at positions ≤ gk + 1.

(3 pts) (c) Briefly justify that OPT′ protects all the paintings at positions > h + 1.

By part (a), it follows that OPT′ protects all paintings at positions > gk + 1.

Long Answer (15 Points Each)

1. Kermit the Frog is visiting his favorite group of lily pads, wanting to catch flies for lunch. He is able to jump from certain pads to others, and each pad has a certain number of flies he would catch at that pad. He wants to catch as many flies as possible.

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

• n vertices V = {1,..., n} representing the lily pads in “topological order,” and

• m directed edges (i,j) ∈ E with i < j, which represent that Kermit can jump from pad i to pad j. Every vertex i < n has at least one outgoing edge.

• Additionally, for each vertex i there is an integer number of flies fi ≥ 0 Kermit would catch at the corresponding lily pad.

Kermit wishes to find a path, following edges in the graph, from vertex 1 (his starting location) to vertex n (the end) that maximizes the sum of the fi for all the vertices i he visits.

(3 pts) (a) Consider the following greedy algorithm for this problem: at each step, jump (via an edge)

to a neighboring lily pad that has the most flies (breaking ties arbitrarily), until arriving at the end.

In the above graph, the number of flies at each vertex is given in a box next to the vertex. State the number of flies obtained by the greedy algorithm on this graph:

Also state the optimal number of flies for this graph:

(No justification is needed for either answer.)

(7 pts) (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 number of flies Kermit could catch if he were to start at vertex i (and end at vertex n).

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.

(5 pts) (c) Give pseudocode for a (bottom-up) dynamic-programming algorithm that outputs

the maximum number of flies that Kermit can catch, in O(n + m) time.

The input to your algorithm is n (the number of vertices), and for each vertex i = 1, . . . , n:

• the number of flies fi at i, and

• the “adjacency list” Ai of i’s out-neighbors, i.e., the vertices j for which (i, j) ∈ E. You do not need to justify your algorithm’s correctness or running time. But to receive full credit it must be clear, correct, and run in the stated time O(n + m).