Final Exam CS601, Algorithms and Complexity, Fall 2025

Instructions:

1. DO NOT OPEN THE EXAM UNTIL YOU ARE INSTRUCTED TO.

2. There are six problems printed across thirteen pages in total. Please make sure all of you
have exams with all the problems and all the pages.

3. Answer all of the questions as well as you can. You have two hours to complete this exam.

4. The exam is non-collaborative; you must complete it on your own. If you have any clarification
questions, please ask the course staff. We cannot provide any hints or help. No cell phone
or electronic devices or any use of Internet is permitted in this exam. Indeed, if you are
caught engaging in unseemly practices, severe action will be taken.

5. This exam is closed-book, except for

(a) Up to two double-sided sheets of paper that you have prepared ahead of time. You can
have anything you want written on these sheets of paper.

Good Luck Total points: 100

1
1. (20 pt.) (A tryst with Big-Oh and friends)

(a) (5 pt.) Prove or disprove: 3n = O(2n ).

SOLUTION:

(a) This is false. Note that 3n = 2n · (1.5)n . This means 2n = o(3n ) and the statement is
false.
2
 log n
(b) False again. Note that 2log n = 2log n = nlog n . Thus it is seen that
 2

n1.5 = o 2log n .

(c) False, yet again. The trick is to take logs. Note that log f = n!. Letting N = 2n , you
have g = N ! and log g ≤ N log N = n · 2n . It is seen that log g = o(log f ) which means
g = o(f ).

2
2. (20 pt.) (Fun with Induction)

(a) (10 pt.) Recall, the Fibonacci numbers, defined recursively as F1 = 1, F2 = 1, and
Fn = Fn−1 + Fn−2 . Prove that every third Fibonacci number is even. For example,
F3 = 2 is even and F6 = 8 is even.
(b) (10 pt.) For any natural number n ∈ N and x > 0, show that (1 + x)n ≥ 1 + nx.

SOLUTION:

(a) This part is kind of direct. We will prove by induction that for all n ≥ 1, F3n is even and
F3n−1 is odd. Noting that F3 = 2 and F2 = 1, the base case is immediately settled by
n = 1. Suppose this is true for all n ≤ k. Now, we would like to show this for n = k + 1.
Now, let us look at F3n+1 = F3n + F3n−1 . By our induction hypothesis, this adds up an
even number and an odd number. This means F3n+1 is odd. Similarly, you can argue
F3n+2 is odd and F3n+3 is even which settles the inductive claim.
(b) We will prove this by induction. For the base case, let us take the situation where
n = 1. This immediately checks out. Now assume inductively that this claim holds for
n = k > 1. We will like to think about the case n = k + 1. Note that

(1 + x)n+1 = (1 + x)n · (1 + x) = (1 + nx) · (1 + x) = 1 + (n + 1)x + x2 ≥ 1 + (n + 1)x .

3
[Continued...]

4
3. (20 pt.)
Design a linear-time algorithm for the following task:
Input: A directed acyclic graph G.
Question: Does G contain a directed path that touches every vertex exactly once?
[HINT: Use topological sort ]

SOLUTION: The main idea is to use topological sort as a handy subroutine. This algorithm
arranges the vertices in G in a linear order from left to right. To find a path that touches all
the vertices exactly once, we just need to check that for every i ∈ {1, 2, 3, . . . , n − 1}, there is
an edge in this sorted DAG between vi and vi+1 . The time complexity of both of these steps
is O(m + n).

5
[Continued...]

6
4. (10 pt.) (A divide and conquer algorithm for MST)
Is the following algorithm correct? If so, prove it. Otherwise, give a counterexample and
explain why it doesn’t work.

FindMST(G)
(a) If n = 1, return the empty set.
(b) T1 ← FindMST(G1 ). Here G1 is the graph induced on first n/2 vertices.
(c) T2 ← FindMST(G2 ). Here G2 is the graph induced on last n/2 vertices.
(d) e ← cheapest edge across the cut {1, 2, · · · , n/2} and {n/2 + 1, n/2 + 2, · · · , n}.
(e) Return T1 ∪ T2 ∪ {e}.

SOLUTION:
This algorithm does not work; multiple edges of the MST could cross this particular cut.
Another way to see this is that the MSTs of the subgraph needn’t also be part of the MST of
the whole graph. As a concrete counterexample, consider a wide rectangle and the horizontal
cut between the top two vertices and the bottom two. Both edges on this cut should be in
the MST. It is also possible that when you divide the graph it is not possible to construct a
MST of the subsection of the graph.

7
[Continued...]

8
5. (10 pt.) (Quick Rapidfire round with MSTs)
For each of the following statements, either prove or give a counterexample. Always assume
G = (V, E) is undirected and connected. Do not assume the edge weights are distinct unless
specifically stated.

(a) (2 pt.) Let e be any edge of minimum weight in G. Then e must be part of some MST.
(b) (2 pt.) If e is part of some MST of G, then it must be a lightest edge across some cut
of G.
(c) (3 pt.) If G has a cycle with a unique lightest edge e, then e must be part of every
MST.
(d) (3 pt.) For any r > 0, define an r-path to be a path whose edges all have weight less
than r. If G contains an r-path from s to t, then every MST of G must also contain an
r-path from s to t.

SOLUTION:

(a) True. Imagine calling Prim’s algorithm from one of the endpoints of the edge e.
(b) True. Indeed, consider removing the edge e = (u, v) from the MST, T . The tree breaks
into two subtrees. We will call the subtree containing u as Tu and the subtree containing
v as Tv . If there is an edge e′ that connects the vertex set of Tu and the vertex set of Tv
which has a cheaper cost than e, then the tree T could not have been a MST. In other
words, e has to be the cheapest edge across V (Tu ) and V (Tv ).
(c) False. Suppose I have a graph where the edge e is the unique smallest weight edge on
some cycle and additionally, the same edge is also the heaviest edge on some other cycle.
Consider the following picture:
10
C F

10 10

5
B E

1 1

A D
1

(d) True. Let s = v1 , v2 , . . . , vk = t denote the r-path in G. Suppose the MST still does not
contain an r-path from s to t. Thus, there are some edges on the r-path above which do
not appear on the s-to-t path in the MST. Consider the first edge on this path that is
not in the MST and write it as (vi , vi+1 ) where 1 ≤ i < k. Consider adding this edge to

9
the MST. This produces a cycle and if there is any edge on this cycle with weight strictly
greater then we can safely swap that heavy edge out and include the edge (vi , vi+1 ) in
the MST instead and this gives a contradiction.

10
6. (20 pt.) (Shortest Paths with colored edges)
I am given a graph G = (V, E) whose edges come in 3 colors – red, blue, and yellow (which
are denoted ER , EB , EY respectively). I know E = ER ∪EB ∪EG . The edge e has cost ce ≥ 0.
Devise an efficient algorithm to compute the length of the shortest path from a vertex s ∈ V
to a vertex t that never uses the edges of the same color consecutively along the path. For
example, if the path takes a red edge from vertex i to vertex j, then it can’t take a red edge
out of vertex j.
Also, write out the proof of correctness and also give the running time of your algorithm.
[HINT: It is helpful to start with three copies of the vertex set V . One in red, the other in
blue, the last in yellow. You want to now add edges in this empty graph to capture what kind
of paths you want. As in, you want to prohibit two consecutive red edges say (i, j) and (j, k).
What kind of edges should you add in this auxiliary graph so that running Dijkstra’s on this
graph does the job? ]

SOLUTION:

(a) We would like to have one graph where we can apply Dijkstra, have it find the kind of
shortest paths we want and then go and relax. The hint provides one possible such graph
you can construct where applying Dijkstra can offer some meaningful insights. As noted
in the hint, the key is to make three copies of the vertex set in each of – GR , GB , GY . I
denote the copy of vertex u in Gi as ui . Keep in mind we want to think of G as being
directed and the graph I will produce will also be directed.
If you want to follow along better, draw n rows each containing a red vertex, a blue
vertex and a yellow vertex. The first row contains 3 copies of s – sR , sB , sY – and the
last row contains 3 copies of t – tR , tB , tY . Hmm, I don’t like this as I want to have one
copy of s and one copy of t. I fix this by adding a zeroth row containing exactly one s in
that row and inserting directed edges with zero weight from s to each copy of s (called
sD ) in row 1. Similarly, we add a vertex called t (called tD ) in row (n + 1). We insert
edges of weight zero from each copy of t in row n to the copy of vertex t in the last row.
Now let us try to see how you want to capture direceted edge information in G in the
graph we are producing. For each edge (u, v) in ER , make a copy between the uB to vR
and between uY and vR .
For each edge (u, v) in EY , make a copy between the uB to vY and between uA and
vY . For each edge (u, v) in EB , make a copy between the uR to vB and between uY
and vB . Run Dijkstra’s Algorithm on this newly constructed graph starting at sD , and
return dist(tD ). Intuitively, (WLOG) arriving at a node vB in GB means that you
took a blue edge to arrive at v, so you need to leave using either a red or a yellow edge;
this construction of the graph captures that information. Indeed to get more intuition
about this construction, suppose you have no “color-alternating path” which goes from
sD to tD , our new graph will have no path from sD to tD ! Note that, thanks to our
construction, an edge from (say) a red vertex in i-th row will not connect it to a red
vertex in any other row. In particular, this means that any color-alternating path will
survive in our new graph and so will the color-alternating path with smallest cost.

11
(b) Runtime: Θ((m + n) · log n).
(c) Proof of correctness: Our auxiliary graph does not have an edge between two vertices
in the same color class. Denoting this auxiliary graph as G′ , this means if I reach some
vertex vB by using a blue edge, then I cannot use a blue edge leaving this vertex!
When constructing our three sub-graphs, every edge we add will have the same weight
as its respective edge in G. Therefore any path in our new graph will have the same cost
as the path in G visiting the same vertices in the same order and thus respects the colors
of the edges along the path in G. Thus this problem can be solved by simply finding the
shortest path from any one of sR , sB , or sY to any one of tR , tB , or tY . We add the
dummy nodes so we only have to run Dijkstra’s once.

12