Fall 2008 Term Test # 1 — Solutions CSC 373 H1
Note to Students: This file contains sample solutions to the term test together with the marking scheme and comments for each question. Please read the solutions and the marking schemes and comments carefully. Make sure that you understand why the solutions given here are correct, that you understand the mistakes that you made (if any), and that you understand why your mistakes were mistakes.
Remember that although you may not agree completely with the marking scheme given here it was followed the same way for all students. We will remark your test only if you clearly demonstrate that the marking scheme was not followed correctly.
For all remarking requests, please submit your request in writing directly to your instructor. For all other questions, please don’t hesitate to ask your instructor during office hours or by e-mail.
General Marker’s Comments:
• Pay a little attention when using notation referring to sets as opposed to sequences.
• When you use recursion to describe a DP algorithm you should be very careful to memoize it. Otherwise
you end up running in exponential time.
• Induction is not magic. You have an inductive claim (induction predicate) on the natural numbers
and you perform induction to show it’s true for every natural number. Showing the induction basis and then defining the predicate makes no sense. You don’t prove the induction basis for the induction basis. You don’t follow the steps of the induction just to get full marks! 🙂 You start by defining the induction claim (predicate) and then you do all the required steps.
• Also, it doesn’t make any sense to do induction without using the induction hypothesis in the construc- tion of your inductive claim. You have something from your hypothesis. Take this “something” and construct “something new” in your induction step. Mention all these things explicitly.
The following comment codes were used. The fact that a comment code appears in your paper does not mean that you necessarily lost marks because of it (depends on the context of your writeup for the specific question). Refer to the marking scheme for each question for more specific details.
• E1: What are you proving by induction? Induction on what? (You may see this comment for any of these two reasons.)
• E2:
• E3:
• E4:
• E5:
• E6:
• E7:
• E8:
• E9: Extend the solution to optimal using what?
Define promising solution explicitly.
No justification/not sufficient justification for the recurrence relation. State the recurrence explicitly.
Compute the actual path, not only its length.
Where do you use the induction hypothesis?
Running time?
The definition of a promising solution has nothing to do with the iterations of the algorithm. The details of the algorithm should not appear in the definition of promising solution.
Page 1 of 6 over…
Fall 2008 Term Test # 1 — Solutions CSC 373 H1 Question 1. [14 marks]
You are consulting for a trucking company that does a large amount of business shipping packages from Toronto to Montr ́eal. The volume is high enough that they have to send a number of trucks each day between the two locations. Trucks have a fixed integer limit W > 0 on the maximum amount of weight they are allowed to carry. Boxes arrive at the Toronto loading platform one by one, and each package i has a positive integer weight wi W . The loading platform is quite small, so at most one truck can be at the platform at any time. Company policy (and the limited space available at the platform) requires that boxes are shipped in the order they arrive—there would be complaints if boxes made it to Montr ́eal out of order!
At the moment, the company is using a simple greedy algorithm for packing: they pack boxes in the order they arrive (as required), putting as many boxes as possible in each truck without exceeding the weight limit W, i.e., whenever the current box would make the load exceed the weight limit W, they send the truck on its way and keep the box for the next truck. But they wonder if they might be using too many trucks, and they want your opinion on whether the situation can be improved: maybe one could decrease the number of trucks needed by sometimes sending off a truck that was less full, and in this way allow the next few trucks to be better packed? More formally, the current algorithm used by the company can be written down as follows.
TruckPacking(W, w1, w2, . . . , wn):
k = 1
Tk = [w1]
t = w1
S = [Tk]
for i = 2,…,n:
# current truck number
# list of packages in current truck # total weight of current truck
# current partial solution
if t+wi W: #packageifitsincurrenttruck;putitin Tk.append(wi)
t += wi
else: # package i does not fit in current truck; start next one
k += 1
Tk = [wi]
t = wi S.append(Tk )
return S # = [T1,T2,…,Tk]
Following the structure given in class, give a detailed proof that the current algorithm is guaranteed to always use the minimum number of trucks. In particular, give a clear, precise definition of what it means for a partial solution to be “promising” for this problem. (Your solution will be marked on its structure as well as its content.)
Sample Solution:
Let S1, S2, . . . , Sn be the sequence of partial solutions generated by the algorithm, at the end of each iteration of the main loop (i.e., Si has put packages 1,2,…,i into trucks, but has not yet considered package i + 1). We say that Si is “promising” if there is an optimal solution Sˆi such that Sˆi puts packages 1, 2, . . . , i on the same trucks as Si. We provethatS1,S2,…,Sn areallpromising,byinduction.
Base Case: S1 is promising because every optimal solution must put package 1 on the first truck, which is what the algorithm does.
Page 2 of 6 cont’d. . .
Fall 2008 Term Test # 1 — Solutions CSC 373 H1 Ind. Hyp.: Suppose i ∈ {1, 2, . . . , n} and Si is promising, i.e., there is an optimal
solution Sˆi that puts packages 1, 2, . . . , i on the same trucks as Si.
Ind. Step: Consider Si+1. Either package i + 1 is put on a new truck, or it is put on
the same truck as package i (call this truck Tj).
Case 1: If package i + 1 is put on a new truck (Tj+1), it must be because wi+1 plus the total weight of the packages already on truck Tj exceeds the weight limit W . Hence, Sˆi cannot put package i + 1 on truck Tj , which means it must be put on truck Tj+1 (because packages cannot be send out of order). So Sˆi+1 = Sˆi puts packages 1,2,…,i+1 on the same trucks as Si+1.
Case 2: If package i + 1 is put on truck Tj (the one that contains package i), then
either Sˆi puts package i + 1 on truck Tj , or it doesn’t.
Subcase A: If Sˆi puts package i + 1 on truck Tj , then Sˆi+1 = Sˆi puts packages 1,2,…,i+1 on the same trucks as Si+1.
Subcase B: If Sˆi puts package i + 1 on a different truck, it must be on truck Tj+1 (because packages cannot be send out of order). Let Sˆi+1 be the same as Sˆi except that package i+1 is moved from truck Tj+1 to truck Tj. Then, Sˆi+1 is an optimal solution (it uses no more trucks than Sˆi and is a valid solution because package i + 1 fits on truck Tj) that puts packages 1,2,…,i + 1 on the same trucks as Si+1.
In every case, Si+1 is promising.
Hence, S1, S2, . . . , Sn are all promising. In particular, Sn is promising, which means that there is an optimal solution Sˆn that puts packages 1, 2, . . . , n on the same trucks as Sn—but this is simply saying that Sn is optimal.
Marking Scheme:
• Structure: [3 marks]
clear attempt to define “promising”, to prove each partial solution is promising (by induction on the number of iterations of the main loop), and to use this to conclude that the greedy solution is optimal
• Promising: [3 marks]
correct definition of “promising”—give up to 2 marks if the notion is used correctly, even if it was not defined explicitly at the start
• Induction: [4 marks]
correct proof by induction, up to the exchange argument (including setting up the correct cases and sub-cases)
• Exchange: [2 marks]
correct proof of the exchange argument
• Conclusion: [2 marks]
correct proof that the final solution is optimal
Page 3 of 6
over…
Fall 2008 Term Test # 1 — Solutions CSC 373 H1
Question 2. [19 marks]
An “ordered graph” G = (V, E) is a directed graph whose nodes can be ordered v1, v2, . . . , vn such that:
(i) every edge goes from a lower indexed node to a higher indexed node, i.e., i < j for all (vi,vj) ∈ E; (ii) all nodes except vn have at least one outgoing edge.
Given an ordered graph G = (V,E), we want to find a longest path from v1 to vn, i.e., a path with the maximum number of edges. For example, in the graph below, (v1,v2), (v2,v4), (v4,v5) is a longest path of
length 3.
Part (a)
x
v1 E v2 v3 E v4 E v5
T 0)
[5 marks]
Give a simple greedy algorithm that attempts to solve this problem, on input G = V = {v1, v2, . . . , vn}, E where the vertices have already been ordered to satisfy the conditions above. Then, show that your algorithm does not always return an optimal solution (give an explicit counter-example and describe the solution returned by your algorithm, as well as why it is not optimal).
Sample Solution:
Main idea of algorithm: take edges to low-numbered vertices as much as possible, to stretch out the path.
LongPath(G = (V, E)):
P = [] # partial path found so far i = 1 # current vertex
while i < n:
find smallest j such that (vi,vj) ∈ E P =P +(vi,vj)
i=j
return P Counter-example:
x
v1 E v2 v3 E v4 E v5
The algorithm returns path P = (v1, v2), (v2, v5) of length 2, when the graph contains
a path (v1, v3), (v3, v4), (v4, v5) of length 3. Marking Scheme:
• Structure: [1 marks]
clear attempt to give an explicit greedy algorithm and to provide an explicit counter-example for the algorithm
• Algorithm: [2 marks]
reasonable and clear greedy algorithm—give full marks even if the algorithm is not given in pseudo-code, as long as the description is clear and detailed enough
• Counter-example: [2 marks]
good counter-example, including justification that the algorithm fails
Page 4 of 6 cont’d. . .
Fall 2008 Term Test # 1 — Solutions CSC 373 H1 Part (b) [14 marks]
Following the structure given in class, give a dynamic programming algorithm for this problem; state the running time of your algorithm. (Your solution will be marked on its structure as well as its content.)
Sample Solution:
For i = 1,2,...,n, let L[i] be the length (number of edges) of a longest path from v1 to vi (L[i] = −∞ if there is no path from v1 to vi).
Then, L[1] = 0 because the only path from v1 to v1 is the one with no edge, and for i = 2,...,n,
L[i] = max 1 + L[j] : (vj , vi) ∈ E
(L[i] = −∞ if there is no edge (vj,vi) ∈ E), because a longest path from v1 to vi must
consist of a longest path from v1 to vj followed by the edge (vj,vi), for some j < i.
The values in L can be computed in a bottom-up fashion, as follows (the meaning and
purpose of array P will be explained below):
L[1] = 0
P[1] = 0
for i = 2,...,n:
L[i] = −∞
P[i] = −1
for (vj,vi) ∈ E:
if 1 + L[j] > L[i]: L[i] = 1 + L[j]
P[i] = j
To reconstruct the actual longest paths, we use a second array P[i] to store the prede- cessor of i on a longest path from v1 to vi, while computing the values of L. Then, the following code constructs a longest path from v1 to vn:
P = [] # current path
if L[n]>−∞: #ifthereisapathfromv1 tovn
i = n # current vertex while i > 1:
P =(vP[i],vi)+P
i = P[i]
# At this point, P is a longest path from v1 to vn.
The running time of the first piece of code is Θ(n2) (because of the nested loops) and for the second piece of code it is Θ(n), for a total of Θ(n2).
Marking Scheme:
• Structure: [3 marks]
clear attempt to define an array, give a recurrence relation for it (with justification), compute its values bottom up, use those values to construct a solution, and state the running time of the entire algorithm
• Definition: [1 mark]
reasonable and clear array definition
Page 5 of 6 over…
Fall 2008 Term Test # 1 — Solutions CSC 373 H1
• Recurrence: [3 marks]
correct recurrence for the array, including appropriate base case(s)
• Justification: [2 marks]
good justification for the recurrence—give part marks even if the recurrence is incorrect, for reasonable attempts to justify it
• Bottom-up algorithm: [1 mark]
correct bottom-up algorithm to compute array—give full marks for correctly computing array values following the recurrence, even if array and/or recurrence are incorrect
• Constructing solution: [3 marks]
correct algorithm to find actual solution, including technique used to figure out correct predecessor (either a second array or an appropriate loop)—give full marks for correctly finding a solution assuming that the array values have been computed correctly, even if they haven’t been
• Time: [1 mark]
correct runtime stated for the algorithm
Page 6 of 6 Total Marks = 33 End of Solutions