University of Toronto, Department of Computer Science CSC 373 Midterm Exam, July 3rd, 2014
Lalla Mouatadid
Duration: 50 minutes
No Aids Allowed
PLEASE COMPLETE THE SECTION BELOW: First Name:
Last Name:
Exam Instructions
• Check that your exam book has 13 pages (including this cover page and 2 blank pages at the end). The last 2 pages are for rough work only, they will not be marked. Please bring any discrepancy to the attention of an invigilator.
• There are 4 questions worth a total of 20 points. Answer all questions on the question booklet.
• For Questions C and D, if you do not know how to answer any part of the question then you can leave that part blank or write “I DON’T KNOW.” to receive 10 percent of the points of the question.
Course Specific Notes
• Unless stated otherwise, you can use the standard data structures and algorithms discussed in CSC263 and in the lectures without describing their implementation by simply stating their standard name (e.g. min-heap, merge- sort, DFS, Dijkstra). You do not need to provide any explanation or pseudo-code for their implemen- tation. You can also use their running time without proof. For example, if you are using the merge-sort in your algorithm you can simply state that merge-sort’s worst-case running time is O(n log n). If you modify a data structure or an algo- rithm from class, you must describe the modification and its effects.
• In some questions you will be given a computational problem and then asked to design an efficient algorithm for it. Unless stated otherwise, for data structures and algorithms that you design you should provide a short high-level explanation of how your algorithm works in plain English, and the pseudo-code for your algorithm in a style similar to those we have seen in the lectures. If you miss any of these the answer might not be marked. If you give the name of the country you’re cheering for this world cup on the back of this exam you will receive one extra bonus mark. Your answers will be marked based on the efficiency of your algorithms and the clarity of your explanations. State the running time of your algorithm with a brief argument supporting your claim and prove that your algorithm works correctly (e.g. finds an optimal solution).
1
University of Toronto CSC373 July 3rd, 2014 PLEASE PRINT YOUR STUDENT NUMBER AND YOUR NAME
Student Number: First Name:
Last Name:
The section below is for marker’s use only. Do NOT use it for answering or as scratch paper.
Questions
Points
A
/3
B
/6
C
/4
D
/7
Total
/20
2
University of Toronto CSC373
July 3rd, 2014 [3]
[1]
[1]
3
A. Definitions
Give the inputs and outputs of the following problems.
1. Minimum Weight Spanning Tree Input :
An edge weighted graph G(V, E, w) where w : E → N. Output :
A spanning tree T of G that minimizes w(e). e∈T
2. A Maximum-Flow Input :
A flow network (G, s, t, c) with source s, terminal t and edge capacity c. Output :
The value of a maximum flow f on G, val(f ) = f (s, u) is maximized. (s,u)∈E
3. A minimum cost prefix-free code [1] Input :
An alphabet Σ = {a1, a2, …, an} and a corresponding list of probabilities (or frequencies) {p1, p2, …, pn} where pi is ai’s probability.
Output :
An encoding C = {b1, b2, …, bn} that minimizes pi ∗ length(bi) where bi is the encoding of ai.
University of Toronto CSC373 July 3rd, 2014 B. Algorithmic Paradigms [6]
1. What is the difference between an adaptive and a non-adaptive greedy algo- rithm? [2]
We’ve been exposed to the adaptive vs non-adaptive greedy algorithms when dealing with minimum spanning tree algorithms. An adaptive greedy algo- rithm is one that would ”adapt”, rearrange, readjust its input at every iter- ation to its own convenience. A non-adaptive greedy algorithm on the other hand only re-orders it’s inputs once, and then it blindly takes it one by one until it has been completely exhausted.
2. What distinguishes dynamic programming from memoization? [2]
Dynamic programming is a bottom-up approach, where we solve all related subproblems first (i.e. filling up the table), then extract the solution of the original problem. Memoization on the hand is a top down approach, we start by solving the ”top” problems, which typically recurses down to solve the subproblems.
3. What is the difference between a greedy algorithm and a local search algo- rithm? [2]
A greedy algorithm is an algorithm where at every iteration, we make a myopic decision. That is, we make the choice that is best at the time, without worrying about the future. And decisions are irrevocable; you do not change your mind once a decision is made. Local search starts with an arbitrary solution to the problem, then keep refining this solution by making small repeated local changes that will increase the quality of the solution. Once a solution converges to a local optimum, then no number of small changes will increase its quality and we are done
C. Maximizing Payoff [4]
Suppose you are given two sets A and B, each containing n positive integers. You
can choose to reorder each set however you like. After reordering, let ai be the ith
element of set A, and let bi be the ith element of set B. You then receive a payoff n
4
of abi.
i i=1
1. Give a greedy algorithm that will maximize your payoff. Your algorithm must run in O(n log n) time. [1.5]
University of Toronto CSC373
July 3rd, 2014
Algorithm 1 MaximizingPayoff
1: Sort A in nondecreasing order a1 ≥ a2 ≥ … ≥ an
2: Sort B in nondecreasing order b1 ≥ b2 ≥ … ≥ bn n
3: return abi
◃ Pair ai with bi
[0.5]
i i=1
2. Give an argument about its running time.
If the two sets A and B are already sorted, the time complexity is O(n).
If the sets are not sorted, then sort them first and the time complexity is O(n log n).
3. Prove that your algorithm is optimal. [2]
Proof. Suppose the optimal payoff is not produced from the above solution. Let S be the optimal solution, in which a1 is paired with bp and aq is paired with b1. Notethata1 ≥aq andb1 ≥bp.
Consider another solution S′ in which a1 is paired with b1, aq is paired with bp, and all other pairs are the same as S. Then
abi
i
S
= (a1)bp(aq)b1 (a1 )b1 (aq )bp
= (a1 )bp−b1 aq
Sincea1 ≥aq andb1 ≥bp,wehave
Payoff(S) ≤ 1
Payoff(S ′ )
This contradicts the assumption that S is the optimal solution. Therefore a1 should be paired with b1. Repeating the argument for the remaining elements completes the proof.
D. Ski Allocation [7]
A set S of n students from UofT organized a sking trip to Whistler. A ski rental agency has m pairs of skis, m ≥ n, where the height of the ith pair of skis is si.
5
Payoff(S )
Payoff(S′) = abi
i S′
University of Toronto CSC373 July 3rd, 2014 Ideally, each skier should obtain a pair of skis whose height matches his/her own
height as closely as possible. Let hj denote the height of the jth student.
The agency’s goal is to assign skis to students as to minimize the cost |hi − si|.
i
Input: A list A = {s1, s2, …, sm} where si denotes the length of ith pair of skis
and a list B = {h1, h2, …, hn} where hj denotes the height of the jth student. Output: The minimum possible cost to match n pairs of skis to the n students.
Give a dynamic programming algorithm to solve this problem. Your algorithm must run in O(nlogn+mlogm+(m−n)m) time.
Hint: How can sorting help you? Suppose you have two students with heights h1,h2 and two pairs of skis with length s1,s2, what’s the optimal matching?
6
1. First, show that if m = n, a simple greedy algorithm solves the problem in O(n log n) time. Be sure to give an argument about the running time. [1] If m = n, we just sort the students and the skis in increasing heights and lengths and assign correlatively.
Both sortings take O(nlogn) time each, and the matching take O(n) time, so the algorithm has a total runtime of O(n log n).
2. Prove that your greedy algorithm is correct. [0.5] The proof follows from the following lemma, that we will also use for when m ̸= n.
Lemma: For any pair of skis with si < sj and any pair of students with hi < hj, there exists an optimal solution that assigns si to hi, sj to hj.
Proof. Case si ≤hi
Case si ≤hi ≤sj ≤hj:
1. If we match si to hi and sj to hj then hi −si +hj −sj = (hj −si)−(sj −hi). 2. If we match si to hj and sj to hi then hj −si +sj −hi = (hj −si)+(sj −hi). As (sj − hi) ≥ 0, the matching (1) costs less than (2).
Inthesamemannerwecanarguewiththecasesi
University of Toronto CSC373 July 3rd, 2014
3. Give a high-level description of each entry in the recurrence used by your
algorithm. [0.5] Let S[i,j] be the optimal cost of matching the first j pairs of skis with the
first i students.
4. Give a formal definition of the recurrence you defined in part (1). [1]
0 Ifi = 0 or j = 0 S[i,j]=min(S[i,j−1],S[i−1,j−1]+|hj −si|) If1≤i≤j
i
∞ I f i > j > 1
5. Give a dynamic programming algorithm implementing the recurrence rela- tion. Give a brief, high-level description of your algorithm, a pseudocode implementation, and an argument about the running time. [2]
S[1…n,1…m] is a table with n rows (students) and m columns (skis). We sort both lists in increasing order of heights and lengths, and at every stage i,j decide whether it’s best to assign the jth pair of skis to the ith students or not.
Algorithm 2 Ski Rental
Input: : A list A = {s1, s2, …, sm} where si denotes the length of ith pair of skis and a list B = {h1, h2, …, hn} where hj denotes the height of the jth student.
Output: : The minimum possible cost to match n pairs of skis to the n students. n ← |A|, m ← |B|
Sort A and B by increasing height and length.
for i ← 0 to n do
S[i,0] = 0 end for
for j ← 0 to m do S[0,j] = 0
end for
for i ← 0 to n do
for j ← 0 to m do if j