Solution: There exists constants c > 0 and n0 ∈ N such that for every n ≥ n0: f(n) ≤ c · g(n).
(a) f(n) ∈ O(g(n)) (a) f(n) ∈ Ω(g(n)) (a) f(n) ∈ o(g(n)) (a) f(n) ∈ ω(g(n))
(b) f(n) ̸∈ O(g(n)) (b) f(n) ̸∈ Ω(g(n)) (b) f(n) ̸∈ o(g(n))
(b) f(n) ̸∈ ω(g(n))
(c) f(n) may or may not be in O(g(n)) (c) f(n) may or may not be in Ω(g(n)) (c) f(n) may or may not be in o(g(n))
(c) f(n) may or may not be in ω(g(n))
Page 1 of 8
CPSC 320 Sample Final April, 2016
1. [24 points] Short Answers
(a) [6 points] Consider the Gale-Shapley stable matching algorithm. Show that at any step of this algorithm
the following claim is true: if there is a free man, then there is a woman he has not proposed to yet.
(b) [4 points] Write down the exact (mathematical) definition of what it means that f(n) ∈ O(g(n)).
(c) [8 points] In each row below, circle the correct statement (either (a) or (b) or (c)) if we know that for every n ∈ N, 0 < f(n) < g(n):
Solution: Proof by contrapositive. Since each woman keeps the best engagement she has received so far, once a woman gets a proposal she will remain engaged until the end. Hence, if a man m has proposed to every woman, then every woman is engaged at this point. Since # of free men = # of free women, every man (including m) is engaged.
Solution: (a), (c), (c), (b)
Comments: f(n) ∈ O(g(n)) — we can choose in definition c = 1 and n0 = 1. This implies that f(n) ̸∈ ω(g(n)). Whether f(n) ∈ Ω(g(n)) or f(n) ∈ o(g(n)), cannot be decided based on the fact that f(n) < g(n). For instance, if f(n) = g(n)/2, then f(n) ∈ Ω(g(n)) and f(n) ̸∈ o(g(n)), but if f(n) = n/2 and g(n) = n2, then f(n) ̸∈ Ω(g(n)) and f(n) ∈ o(g(n)).
(d) [6 points] What are the two strategies used to show that the greedy solution is an optimal solution? Briefly explain what is the main idea of each strategy.
2. [20 points] Short answers.
(a) [10 points] The worst-case running time of an algorithm you wrote satisfies the recurrence relation
aT (n/4) + nx if n ≥ 4
T(n) =
Θ(1) if n < 4
For which values of the constants a and x will the algorithm run in Θ(n2) time? Hint: there are two cases.
Solution:
• Staying-Ahead: show that the greedy solution is as good the optimal solution at every step.
• Exchange-Argument: show that any optimal solution can be transformed to the greedy solution by a sequence of transformations, each preserving the optimality of the solution.
Page 2 of 8
Solution: We can use the Master Theorem, since the recurrence has the right form (as long as a > 0). The special function is s(n) = nlog4 a and f(n) = nx. Hence, depending on comparison of log4 a and x, we can end up in each of the three cases:
1. x < log4 a, we have Case 1. Hence, T(n) ∈ Θ(s(n)). Since we want Θ(n2), we must have log4 a = 2. Then a = 16 and x < 2.
2. x = log4 a, we have Case 2 with k = 0. Hence, T(n) ∈ Θ(s(n)logn). There is no choice for x and a, how to get Θ(n2) (we can’t get rid off the log n term).
3. x > log4 a, we have Case 3. Hence, T(n) ∈ Θ(f(n)). We must have x = 2, and then log4 a < 2 = log4 16, so a < 16. However, we also need to check the regularity condition: a(n/4)2 ≤ δn2. Since a(n/4)2 = a/16 · n2 and a < 16, the regularity condition holds for δ = a/16 < 1.
The answer: T(n) ∈ Θ(n2) if either a = 16 and x < 2, or a < 16 and x = 2.
(b) [4 points] In our divide and conquer algorithm to find the closest pair of points in the plane, why was it sufficient, during the merge step, to consider points that were at most 11 positions apart in the list of points in the vertical strip around the dividing line sorted by their y-coordinates?
Solution: Divide the strip into δ/2 × δ/2 boxes. Each box can contain at most one point, otherwise two points on the same side of the dividing line are closer than δ apart, which isn’t possible by the definition of δ (the smallest distance found between two points on the same side of the dividing line). Hence, if two points 12 or more positions apart on the list, then there are at least two layers of boxes between them, and hence, their distance is at least δ.
Page 3 of 8
(c) [6 points] Assume n is even. Describe an algorithm that find simultaneously the minimum and the maxi-
mum among n elements using 3n/2 − 2 comparisons in the worst case.
3. [20 points] You and a group of your friends want to play tug-of-war (two teams pulling on opposites sides of a rope). Being the only computer scientist in the group, you have been asked to design an algorithm to build two teams A and B that are as equal as possible. You formalize the problem as follows:
• Each person i has a strength si.
• You would like the sum of the strengths of the people on team A to be as close to equal as possible to the sum of the strengths of the people on team B. That is, you want to minimize
si − sj
i ∈ A j ∈ B Note that the two teams do not need to have the same number of people.
(a) [12 points] Write a pseudocode for a greedy algorithm to build the teams A and B. Your algorithm does not need to always succeed at minimizing the difference in total strength between the two teams, but it should make a good attempt at it.
Solution: Divide the numbers into n/2 pairs. Find the smallest and largest elements for each pair: (s1, l1), . . . , (sn/2, ln/2) [n/2 comparisons]. Then apply standard algorithm to find the minimum among s1,...,sn/2 (n/2 − 1 comparisons) and then the maximum is among l1,...,ln/2 (n/2 − 1 comparisons). The total number of comparisons used is exactly 3n/2 − 2.
Solution: Here is one possible algorithm.
function BUILDTEAMS(S)
sort S by decreasing strength strengthA ← 0
strengthB ← 0
for i ← 0 to length[S] − 1 do
if strengthA < strengthB then
add person i to A
strengthA ← strengthA + strength[i]
else
add person i to B
strengthB ← strengthB + strength[i] end if
end for
return A, B end function
Comments: The idea here is to make a greedy choice for each interval that will make the teams as equal as possible: add the next person to a weaker team. Also to avoid dealing with a strongest person at the end, which could make the teams unbalanced at the end, the people are sorted by their strength in decreasing order.
(b) [4 points] Analyze the time complexity of your algorithm from part (a). Specify only as much of your implementation (for instance, data structures) as needed for your analysis. Try to obtain as tight bound on the running time as possible, but make sure that your answer is correct (otherwise you will lose all points for this part). Justify your answer!
Page 4 of 8
Solution: The algorithm above runs in O(n log n) time, because of the sorting step. The remaining part of the algorithm takes time in O(n), because loop iterates n times and each iteration take a constant time.
(c) [4 points] Give an example where your algorithm will not return the optimal solution (the one that mini- mizes the strength difference between the two teams).
4. [8 points] Let G = (V, E) be an undirected graph with costs c(e) ≥ 0 for all edges e ∈ E. Assume that the edge costs are distinct. Assume you are given a minimum-cost spanning tree T in G. (You don’t need to find or verify it, you can assume it is a minimum-cost spanning tree). Now assume that a new edge is added to E, connecting two nodes v, w ∈ V with cost c that is distinct from costs of edges already in the graph.
Describe an efficient algorithm to test if T remains the minimum-cost spanning tree with the new edge added to G (but not to the tree T ). Make your algorithm run in time O(|E|) time. Please note any assumptions you make about what data structure is used to represent the tree T and the graph G. Justify briefly why your algorithm is correct.
Solution: Suppose we have six people with strengths 10, 9, 6, 5, 4 and 2. The algorithm from part (a) will make two teams with strengths 10 + 5 + 2 = 17 and 9 + 6 + 4 = 19. However there is a solution where both total strengths are equal: 10 + 6 + 2 = 9 + 5 + 4 = 18.
Solution: A simple algorithm is to find a path from v to w in T using BFS or DFS. If we are using a adjacency list, this is linear to the number of edges, since when finding a path we can visit every edge at most twice (once in each direction). If any of the edges on this path has a cost larger than c, then the answer is No, otherwise it’s Yes. This follows by a Cycle Property applied to the cycle containing the path and the new edge {v, w}, which states that the edge with the highest cost is not in any MST of the graph.
5. [12 points] Consider an n-node complete binary tree T , where n = 2d − 1 for some integer d. Each node v of T is labeled with a real number xv. You may assume that the real numbers labeling the nodes are all distinct. A node v of T is a local minimum if the label xv is less than the label xw for all nodes w that are connected to v by an edge.
You are given such a complete binary tree T, but the labeling is only specified in the following way: for each node v, you can determine the value xv by probing the node v. Design a divide and conquer recursive algorithm that find a local minimum in a T and show that the number of probes it will make is in O(log n). Write pseudocode to specify your algorithm. Remember to justify that your algorithm will make O(log n) probes.
Solution: Algorithm:
1: 2: 3: 4: 5: 6: 7: 8:
function LOCALMINIMUM(T, v)◃ v is either the root or xv is smaller than the value of the parent of v if v is a leaf or xv is less than values of children of v then
return v else
letubeachildofvsuchthatxu
Algorithm: To compute V [i, w] we need values of V [i − 1, ∗], so the main loop should iterate i from 0 to n, and inside we can iterate through different values of w between 0 and W in any order.
function KNAPSACK(w1,…,wn,v1,…,vn,W) for w ← 0 to W do
◃ initialization:
Pointstotal: 140
Page 8 of 8
V [0, w] ← 0 end for
for i ← 1 to n do
for w ← 0 to W do
V [i, w] ← V [i − 1, w]
ifwi ≤wandV[i−1,w−wi]+vi >V[i,w]then
V [i, w] ← V [i − 1, w − wi] + vi end if
end for end for
return V [n, W ] end function
◃ filling up the table:
Comments: The complexity of this algorithm is O(nW ). The algorithm relies on the fact that the weights are integers. If would allow weights to be any positive real numbers, then there would be no way how to iterate through all possible weights (the second parameter). If you are wondering if there is a different efficient algorithm for this problem in this case (either a different DP algorithm or some other algorithm), the answer is No. This problem (with weights being real numbers or even with integer weights that can be exponential in n) is NP-complete, which means that it’s very unlikely there is an efficient algorithm for this problem (unless many other hard problems have polynomial-time solutions).
End of exam.