CS 124 Midterm: Spring 2023
Your name: Instructions:
• Spend at most 75 minutes on the exam, from the time you first see a problem to the last time you write anything in your solutions.
Time started: Time ended:
• Do not communicate with anyone but the course staff about the contents of the exam.
• Do not use a computer or other electronic aids during the exam for anything except for:
1. (optionally, for extension students or with prior approval) typesetting your solutions, 2. (for extension students only) asking clarification questions of the instructors on Ed.
• You may use no notes but two single-sided (or one double-sided) 8.5”x11” pages of notes you prepare ahead of time.
• After you finish the exam, write your name in affirmation of the following statement:
I, , pledge
my honor that I have obeyed all instructions on this page in taking this exam.
Reminder for extension students:
After you finish, upload your exam to Gradescope as if it were a problem set.
• You have 75 minutes to earn a maximum of 75 points. Do not spend too much time on any single problem: we recommend roughly n minutes on an n point problem. Read all the problems first, and attack them in the order that allows you to make the most progress.
• You can ask clarification questions of the instructors.
• Explain and write clearly. You will be graded not only on the correctness of your answers,
but also on the clarity with which you express them.
• Do not waste time re-deriving results presented in class, psets, or sections. You may simply state and cite them.
1 True or False (18 points)
For each of the following statements, say whether the statement is TRUE or FALSE. Each correct answer is worth 2 points. Incorrect answers are worth 0 points. No explanations are needed.
1. n124 = O((124)log∗ n). False
Note that log∗(n) = 1 + log∗(log n) ≤ 1 + log n, so 124log∗ n ≤ 124nlog 124 = o(n124).
2. If T (n) mapping positive integers to positive integers satisfies T (1) = 1 and
T(n) = T(⌈n/4⌉) + T(⌈n/2⌉) + n2
then T (n) = O(n2 log n). True
T is increasing (e.g. by induction). Then T (n) ≤ 2T (⌈n/2⌉) + n2, so by the Master theorem T (n) = O(n2 log n).
3. If T (n) mapping positive integers to positive integers satisfies T (1) = 1 and T(n) = T(⌈n/4⌉) + T(⌈n/4⌉) + n2
then T (n) = O(nlog4 2). False
T(n) ≥ n2 = ω(nlog4 2).
4. There exists an algorithm to compute the nth Fibonacci number Fn in o(n2) time.
For instance, the matrix power algorithm from lecture takes logn multiplications of O(n)- digit numbers, and using Karatsuba’s algorithm for those multiplications makes the whole runtime at most nlog2 3 log n = o(n2).
5. The classification of an edge in a directed graph as a forward/back/cross/tree edge does not depend on the order in which the vertices and edges are presented to the DFS algorithm.
For instance, in a graph with three vertices {s, a, b} and three edges {(s, a), (s, b), (a, b)}, the edge (a, b) is a tree edge if a is explored first in a DFS from s but a cross edge if b is explored first.
6. If DFS is run on a connected, undirected graph, the vertex with the lowest preorder number must also have the highest postorder number.
Since the graph is connected, DFS won’t finish (and assign a postorder number to the source vertex) until the whole graph is explored.
Code Help, Add WeChat: cstutorcs
7. If all edge lengths in a weighted undirected connected graph are distinct then for every pair of vertices s and t in G there is a unique shortest path from s to t in G.
If G has edges (s, a), (a, t), (s, b), and (b, t) of weights 1, 4, 2, and 3, respectively, then there are two shortest paths from s to t.
8. There exists a weighted graph G on which Kruskal’s algorithm finds an MST of smaller total weight than Prim’s algorithm.
Kruskal’s and Prim’s each find an MST if one exists. All MSTs have equal (minimum) weight.
9. The greedy algorithm for finding satisfying assignments of a Horn SAT formula (i.e. a SAT formula in which each clause has at most one positive literal) always finds an assignment setting the minimum number of variables to True, if any satisfying assignment exists.
Every variable set to True by the greedy algorithm is true in every satisfying assignment.
CS Help, Email: tutorcs@163.com
Depth-First Search (6 points)
1. (4 points) Compute the pre-order and post-order numberings of DFS on the following graph. Assume that, if given multiple choices, DFS explores vertices in alphabetic order. No expla- nation is necessary.
A: (1,16) B: (2,13) C: (3,10) D: (4,7) H: (5,6) G: (8,9) F: (11,12) E: (14,15)
2. (2 points) If the graph above is acyclic, give a topological sort of the graph. Else give its strongly connected components. No explanation is necessary.
The graph is acyclic. There are many topological sorts, including ABCDEFGH and AEBFCGDH.
3 Card Game (15 points)
Consider the following game. A “dealer” lays out a sequence s1, . . . , sn of “cards” face up, where each card si has positive integer value vi. Then two players take turns picking a card from the sequence, but can only pick the first or the last card of the (remaining) sequence. The goal is to collect cards of largest total value. (For example, you can think of the cards as being bills of different denominations.) Assume n is even.
1. (3 points) Show a sequence of card values such that it is not optimal1 for the first player to start by picking up the available card of larger value. That is, the natural greedy strategy is suboptimal. No explanation is necessary.
One example is 1, 2, 4, 2: if the first player picks 1, they’re guaranteed a score of 5; if they pick 2, the second player could pick the 4, so the first player can’t guarantee a score higher than 2 + 2 = 4.
2. (12 points) Give an algorithm to compute the largest integer B such that the that the first player can guarantee earning at least B total value, no matter what the second player does. Your algorithm should run in time O(n2), but you don’t need to prove so. Prove the correctness of your algorithm.
Allocate an n × n array B. In increasing order of i + j with i, j ∈ [1, . . . , n] with i < j, let
max(vi, vi+1)
max(vi +min(B[i+2,j],B[i+1,j−1]),
i + 1 = j else
We’ll prove by induction that B[i, j] is the largest score that the first player can guarantee if the remaining cards are si through sj . This is true for the base cases B[i, i] and B[i, i + 1], where the first player can only pick one card. If the first player picks si, the second player can pick either si+1 or sj, so the first player can guarantee vi plus the minimum of the guarantees B[i + 2, j] and B[i + 1, j + 1] in those two cases. If the first player picks si, they can’t guarantee more than that minimum: if the second player makes the pick corresponding to the minimum, we know by induction that they can’t guarantee more than B[i + 2, j] or B[i+1,j+1]. So,thefirstplayercanguaranteeatleastvi+min(B[i+2,j],B[i+1,j−1]). The case where the first player picks sj is similar, so the first player can guarantee at least vj + min(B[i + 1, j + 1], B[i + 1, j − 1])). Hence the first player can guarantee the maximum of those (and no more, because neither pick guarantees more).
1That is, the first player should be able to guarantee a higher total score if they start by picking the lower-valued card than the best score they could guarantee if they start by picking the higher-valued card.
vj +min(B[i,j−2],B[i+1,j−1]))
(We aren’t required to prove it, but this calculates answers to O(n2) subproblems in O(1)
Return B[1, n].
time each, for a total time of O(n2).)
Code Help
4 Robot meetups (18 points)
A red robot and a blue robot are in distinct rooms r0 and r1 of a space station composed of n rooms, some ordered pairs of which have one-way passages between them. Each passage is colored red or blue and can only be used by the robot of the matching color. Also, each passage has a positive integer energy cost to use. The robots would like to meet up in one room (not necessarily r0 or r1).
1. (8 points) Give an algorithm to determine whether it’s possible for the robots to end up in the same room and, if so, the cheapest possible total energy cost for them to do so.2 You don’t need to prove the correctness of your algorithm. Your algorithm should run in time O(n2), and you should explain why your algorithm uses at most that runtime. For up to 5 points of partial credit, your algorithm can run in time O(n2 log n).
Run Dijkstra’s algorithm, using an unsorted array as the priority queue, on the graph whose vertices are rooms, edges are red passages, and source is r0, to get the least energy costs for the red robot to reach each room. Do the same for blue. For each room, calculate the sum of those costs; return the minimum (or “impossible” if it’s infinite).
Dijkstra’s requires n delete-mins and m updates. m ≤ n2 in each graph since each ordered pair of rooms has at most one passage. With an array as the priority queue, delete-min takes time O(n) and update takes time O(1), for a total of O(n ∗ n + n2 ∗ 1) = O(n2) time.
2The robots won’t run out of energy; they just want to spend as little as possible. It doesn’t matter which robot spends energy; you only care about the total amount spent. At all times the robots can communicate with each other and know exactly where the other robot is.
2. (10 points) Now suppose that in each room there are some buttons. Each button is marked with a passage somewhere in the space station.3 While one robot holds down a button, the other robot can use the passage marked on that button, even if that passage is the wrong color4. Again, give an algorithm to determine whether it’s possible for the robots to end up in the same room and, if so, the cheapest possible total energy cost for them to do so. You don’t need to prove the correctness of your algorithm. Your algorithm should run in time O(n3 log n) and space5 O(n2), and you should explain why your algorithm uses at most that runtime and space. For up to 7 points of partial credit, your algorithm can run in time O(n4 log n) with no restriction on space.
Run Dijkstra’s algorithm, using a binary heap as the priority queue, on the graph G′ whose vertices are ordered pairs of rooms, with an edge from (r, s) to (t, u) if either:
(a) r = t and (s,u) is a blue passage,
(b) r = t and (s,u) is a red passage with a button in room r,
(c) s = u and (r, t) is a red passage, or
(d) s = u and (r,t) is a blue passage with a button in room s,
with source (r0,r1) and edge weights w(s,u) for the first two edge types and w(r,t) for the second two edge types, to find the least-energy ways for the robots to reach each pair of rooms (x, y). Return the minimum, over rooms x, of the distance to the vertex (x, x). (Don’t calculate the whole graph in advance: when Dijkstra’s needs to know whether an edge exists, we can calculate it in O(1) time from the original graph by the description above.6)
This takes O(n2) space: we don’t remember more than, for each of the n2 vertices of G′, an entry in the binary heap, a current distance to that vertex, and Dijkstra’s exploration status of that vertex (plus o(n2) space for Dijkstra’s control flow).
This takes O(n3 log n) time: there are at most n3 edges of G′ of each of the four types since each is determined by a choice of 3 vertices of G, so G′ has O(n2) vertices and O(n3) edges. So, Dijkstra’s requires O(n2) delete-mins and O(n3) updates, and with a heap as the priority queue, that’s a total of O(n3 log n) time.
3There may be any nonnegative integer number of buttons in a room. Each passage may be marked on buttons in any subset of rooms, possibly the empty subset. The robots know the list of buttons in each room and the starting and ending rooms for the passage marked on each of them.
4The energy cost for a blue robot to use a passage is the same as the energy cost for the red robot to use that passage.
5You can assume the entire input fits in O(n2) space
6If the robot needs O(k) time to look through all k buttons in a room, then calculate all edges of types 2 and 4 from a given vertex at once.
5 Union-Find without rank (18 points)
In class we discussed the Union-Find data structure with path compression and rank. In particular, when we linked roots x and y of two trees, we checked the rank of x and y: if the rank of x was larger than the rank of y, we made x the parent of y, if not, we made y the parent of x. In this problem we look at Union-Find without this swap (and so effectively without rank).
In the modified Union-Find data structure the algorithm LINK(x,y), where x and y are roots of trees, simply sets the parent of y to be x, i.e. p(y) = x. All other algorithms are unchanged. The rest of this problem considers this modified algorithm. In the rest of the problems assume an initialization with n disjoint sets of size 1 using MAKESET(·) and no other MAKESET operations, so the data structure contains n elements.
1. (4 points) Give a sequence of O(n) operations (each operation being a UNION or FIND) such that the last FIND operation takes Ω(n) time. No explanation is necessary.
UNION(2,1), UNION(3,2), . . . , UNION(n,n-1), FIND(1). (Then the find explores each vertex 1, 2, …, n on its way to the root.)
2. (7 points) Define the weight w(u) of a node to be the number of nodes in the subtree rooted at u (so the weight of a leaf is 1). Define a node u to be heavy if w(u) > 21w(p(u)) and light otherwise. Prove that, in every root-to-leaf path, after any sequence of union and find operations, the number of light nodes is at most log2 n.
Let v0, v1, …, vk be any root-to-leaf path. For all i, w(vi) ≤ n since the total number
of nodes in all trees is at most n and w(vi) ≤ w(vi+1), because the subtree rooted at vi+1
contains the subtree rooted at vi. Also, if vi is light, w(vi) ≤ 21w(vi+1). So, if there are l light
verticesonthepath,w(v)≤1w(v).Ifl>logn,then1≤w(v)< 1 w(v)≤1n≤1 0 2l k 0 2logn k n
which is a contradiction. (The final inequality here uses w(vk) ≤ n.) So l ≤ logn, as claimed.
3. (7 points) Suppose that the path from a vertex x to the root of the tree is x = v0 → v1 → v2 → · · · → vl where vl is the root. Prove that after an operation FIND(x), at most three vertices in the set {v0, . . . , vl} are heavy.
After FIND(x), the subtrees rooted at v0, ..., vl−1 are disjoint (because path compression
made each of them children of the root vl), so the sum of their sizes is at most w(vl), so at
most two of them have size at least w(vl). Each of them has parent vl, so at most two of 2
them are heavy. The last of those vertices, vl, is only one vertex, making at most three heavy vertices.
4. (0 points, optional) Show that no sequence of O(n) unions and finds takes more than O(nlogn) time. [Hint: Note that light nodes remain light in the future. So if you divide the cost of a FIND into TYPE 1 costs corresponding to steps vi → vi+1 where vi is light or vi is heavy after the FIND and TYPE 2 costs where vi is heavy before the find and light afterwards, can you bound these costs nicely over the course of O(n) operations?]
Each FIND operation explores a light vertex at most logn times, for a total of O(nlogn) time for n FINDs’ exploration of light vertices.
Each FIND operation explores a vertex that remains heavy after the FIND at most 3 times, for a total of O(n) time for n FINDs’ exploration of such vertices.
Each vertex is explored by a FIND that changes it from heavy to light at most once (because it can’t change back), for a total of O(n) cost for O(n) find operations.
Hence the total cost is O(n log n).
Extra page for problem #
Extra page for problem #