CSCI 3110 Midterm posted: 15.06.2020
Instructor: Travis Gagie due: midnight 19.06.2020
You are not allowed to work in groups for the midterm. You should submit your solutions
on Brightspace with your name and banner number. For programming questions you should
submit your code, which should compile and run correctly to receive full marks.
You cannot consult anyone except the TAs regarding the midterm. You can look in the book
and online for ideas but you must understand fully everything you write. You may be asked
to explain your answers later in a recorded online meeting; if you cannot do so adequately
then you may receive a 0 for the midterm and/or be reported to the faculty.
You can ask the TAs to clarify their respective questions or material presented in the lectures,
either by email or in the tutorial on Friday, June 19th. For the sake of fairness, they will
not help you in any way that takes more than a few minutes of their time. Contact Travis
for medical emergencies, etc, but please don’t ask him about the midterm problems unless
the TAs tell you to.
Due to the circumstances this summer, this is not a regular midterm exam. It will be posted
in the morning of Monday, June 15, and solutions are due at midnight Friday, June 19th.
There are 5 questions and for each one you are asked to describe and/or analyze and/or
implement an algorithm.
You can think of this midterm as practice for technical interviews: imagine you have made
it through the first round or two and now a potential employer has given you these five
questions and a work-week to demonstrate that you understand algorithms; show you know
your stuff!
1
1. (5 marks; questions to Sarah) Describe an O(n log n)-time divide-and-conquer
algorithm that, given n points (x1, y1), . . . , (xn, yn) in the plane, returns the area inside
the points: i.e., the area of the shape that is the union of all the triangles with vertices
(xi, yi), (xj, yj), (xk, yk). Analyze your algorithm’s running time.
You need not implement your algorithm nor prove it correct, and you can assume
you have a function float triangleArea(xi, yi, xj, yj, xk, yk) that returns
the area of the triangle with vertices (xi, yi), (xj, yj), (xk, yk) in O(1) time.
Idea: They should use the divide-and-conquer algorithm for finding the convex hull of
the points (mentioned on page 1030 of the text) and then break the shape inside the
convex hull into non-overlapping polygons, either recursively or iteratively, as Sarah
suggested.
2. (5 marks; questions to Mozhgan) Implement an algorithm that, given an integer
n and a pointer to an array of n sorted positive integer weights, builds a Huffman tree
for them in O(n) time and returns a pointer to the root of the tree. You need not
prove your algorithm correct nor analyze it but you should document your code.
Idea: They should implement Van Leeuwen’s algorithm:
• start with queue Q1 containing all the weights in sorted order with the lightest
at the head and queue Q2 empty;
• repeat n− 1 times:
– dequeue the smallest enqueued weight x;
– dequeue the smallest enqueued weight y;
– make x and y the children of a new weight x + y;
– enqueue x + y in Q2;
• return a pointer to the remaining enqueued weight.
This works because the queues always remain sorted: we never enqueue anything in
Q1 and whenever we enqueue some weight x+y in Q2, either it’s at the head or it’s
preceded by a weight x′ + y′ for some weights x′ and y′ that were dequeued before x
and y, so x′, y′ ≤ x, y and x′ + y′ ≤ x + y. (The students don’t have to explain this.)
3. (5 marks; questions to Reza) Modify the C program in the notes for Lecture 10
such that it takes an integer n and a pointer to an array of n floating-point weights,
and returns the expected depth of an optimal binary search tree on n keys with those
weights in O(n2) time. (Currently the algorithm works in O(n3) time.) You need not
prove your modification correct nor analyze it but you should document the changes.
Knuth’s observation is that if we add keys to the right of a binary search tree then
the best choice of root cannot move left (and vice versa). The students don’t need to
know why this is true.
2
To find the best choice rs,i of root for the subtree with size s whose leftmost key is the
ith, we just have to check between the best choice rs−1,i of root for the subtree with
size s − 1 whose leftmost key is the ith, and the best choice rs−1,i+1 of root for the
subtree with size s− 1 whose leftmost key is the (i + 1)st.
Finding rs,i takes O(rs−1,i+1 − rs−1,i + 1) time so, summing over s and i, we use a total
of
O
∑
2≤s≤n
∑
1≤i≤n−s+1
rs−1,i+1 −
∑
2≤s≤n
∑
1≤i≤n−s+1
rs−1,i + n
2
= O(n2)
time. The students don’t have to know this, either.
4. (5 marks; questions to Yifan) Describe an O(n log n)-time dynamic-programming
algorithm that, given a sequence S = s1, . . . , sn of integers, finds the longest subse-
quence s′1, s
′
2, . . . , s
′
k such that s
′
i < s
′
i+1 ≤ 5s′i/4 for 1 ≤ i < k. You need not implement
nor analyze your algorithm, nor prove it correct.
Idea: This is Question 1 on Assignment 4 from the fall semester. If they find the
solutions in the fall course directory, good for them. I don’t think this can be done
easily with the array trick from Leetcode, but it’s not hard with a dynamic range-max
data structure (like an augmented AVL tree). If the students just say they use such a
data structure, that’s ok.
5. (5 marks; questions to Sarah) Implement an algorithm that, given an integer m
and a pointer to an array A [0..m - 1][0..2] containing the edges of a connected
graph G and their integer weights, sorted in non-decreasing order by weight, returns
the total edge-weight of a minimum spanning tree of G in o(m logm) time. Notice that
is an o and not an O!
You can assume the vertices of G are also integers and, for 0 ≤ i < m, A [i][0] is one
endpoint of the ith lightest edge e (counting from 0), A [i][1] is e’s other endpoint,
and A [i][2] is e’s weight. You need not prove your algorithm correct nor analyze it
but you should document your code.
Idea: They should implement the union-find data structure with union-by-size and
path compression (when we do perform a find query, make all the nodes we visit on the
path to the root point to the root). They don’t have to know why this works, and it’s
easy to implement.
6. (1 bonus mark) List the counties of Nova Scotia in alphabetical order.
Idea: List the counties of Nova Scotia in alphabetical order.
3