$35
CS 341: Algorithms
Midterm Exam
The full mark is 80. There are 10 bonus marks. This exam paper has three pages and eight problems.
1. (10 marks) In this question of solving recurrences, we assume that constant size problems can be solved
in constant time. More formally, we assume that there exists a constant c0 ≥ 100 so that T(x) ≤ c1
for a constant c1 for all x ≤ c0. We also assume that n is a power of two for simplicity.
(a) (5 marks) For the recurrence T(n) = 9T(n/2) + n
3
, provide the best big-O bound for T(n).
(b) (5 marks) For the recurrence T(n) = T(n/2)+T(n/4)+T(n/8)+n, provide the best big-O bound
for T(n).
Briefly explain your answers. You can use the Master theorem when applicable.
2. (10 marks) Consider the 4-sum problem. We are given as input n integers a1, . . . , an and a target
integer K. Our goal is to output 4 indices 1 ≤ i, j, k, l ≤ n such that ai + aj + ak + al = K, or report
that no such quadruple exists. Note that i, j, k, l are not required to be distinct indices (e.g. we can
return i = j = k = l if 4ai = K).
Provide the fastest algorithm that you can for this problem. Briefly explain the correctness and the
time complexity of your algorithm.
3. (10 marks) Given an undirected graph G = (V, E) and n := |V |, provide an algorithm to determine if
there is a triangle in the graph in O(M(n)) time, where M(n) ≥ n
2
is the time complexity to multiply
two n × n matrices. If there exists a triangle, your algorithm should return a triple of three distinct
vertices u, v, w ∈ V such that uv ∈ E, uw ∈ E, and vw ∈ E. State your algorithm clearly and briefly
explain its correctness and time complexity.
4. (10 marks) Given an undirected graph G = (V, E), provide a O(|V |+|E|)-time algorithm to output all
cut edges of G. State your algorithm clearly and explain the correctness of your algorithm. You can
use all the results in L06 about finding all cut vertices of G in linear time without providing proofs.
5. (10 marks) Some people may think that the number 4 is unlucky. In this problem, you are given a
directed graph G = (V, E) and two vertices s, t ∈ V , and the task is to find a shortest walk from s
to t, but the length of the walk cannot be a multiple of 4, or report that such a walk does not exist.
That is, among all possible walks from s to t whose length is not a multiple of 4 (if they exist), your
algorithm should return one such walk with the shortest possible length. State your algorithm clearly
and explain the correctness and time complexity of your algorithm. You will get full marks if your
algorithm is correct with time complexity O(|V | + |E|).
1
6. (10 marks) Given a directed acyclic graph G = (V, E), your task is to design an algorithm to determine
if there is a directed path that touches every vertex exactly once. State your algorithm clearly and
explain the correctness and time complexity of your algorithm. You will get full marks if your algorithm
is correct with time complexity O(|V | + |E|).
Figure 1: In the graph on the left, the path highlighted touches every vertex exactly once, while in the graph
on the right, there is no such path.
7. (10 marks) Imagine an advertising company would like to post a huge poster in Toronto harbour front.
There are n consecutive buildings there, with positive height h1, . . . , hn and unit width as shown in
the figure. Design an algorithm to find the maximum rectangular space to post their poster. Stated
mathematically, find 1 ≤ i ≤ j ≤ n to maximize (j − i + 1) · mini≤k≤j{hk}.
4 6 5 4 3 1 5 4 3 7
Figure 2: These are three possible solutions. The largest one has area 4 × 4 = 16.
State your algorithm clearly and briefly explain its correctness and its time complexity. You will get
full marks if the time complexity is O(n log n) and the explanation is good.
Bonus (5 marks): There are up to five bonus marks if an algorithm with time complexity O(n) is
provided with correct explanation.
2
8. (10 marks) Given a binary tree, the pre-order traversal is obtained by first printing the root, and then
the left subtree recursively and then the right subtree recursively. The in-order traversal is obtained
by first printing the left subtree recursively, then the root and then the right subtree recursively. See
the following picture for an example.
Figure 3: The pre-order traversal of the tree is 0 1 3 7 4 2 5 6, and the in-order traversal is 7 3 1 4 0 5 2 6.
Given a pre-order traversal, we could not uniquely recover a binary tree, as there are multiple binary
trees with the same pre-order traversal. However, if we are given both the pre-order traversal and the
in-order traversal of a binary tree, then we can uniquely recover the binary tree.
In this question, your task is to give an algorithm to reconstruct the binary tree given its pre-order
traversal and in-order traversal. You will get full marks if the time complexity of your algorithm is
O(n
2
) and the proofs are correct, where n is the number of nodes in the tree.
Bonus (5 marks): You will get the bonus marks if the time complexity of your algorithm is O(n)
and the proofs are correct.
3