Fall 2008 Term Test # 2 — 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.
Question 1. [10 marks]
Consider the following task: given a list that contains stock prices over the last several days, determine if there are any three consecutive days during which the stock price increased. Write a divide-and-conquer algorithm that carries out this task; more specifically, give an algorithm A(L,b,e) that returns an index i such that b+1 i e−1 and L[i−1] < L[i] < L[i+1], if such an index exists—your algorithm should return the value −1 if there is no such index. Include descriptive comments, or a concise English description of the main ideas, and analyze the running time of your algorithm. (For your reference, the Master Theorem states that a recurrence of the form T(n) = aT(n/b)+Θ(nd) has solution Θ(nd) if a < bd, Θ(nd log n) if a = bd, and Θ(nlogb a) if a > bd.)
Note: For full marks, your answer must make use of the divide-and-conquer method (even though there is a simple iterative solution), and your algorithm must run in no more than linear time.
Sample Solution:
# Return an index i such that b + 1 i e − 1 and L[i − 1] < L[i] < L[i + 1], # or −1 if there is no such index.
A(L, b, e):
if b+1>e−1: return−1
m = (b + e)/2
# Check if the midpoint works.
if L[m−1]
#L[b…e]containsatmost2elements returnm
# Otherwise, check if there are three consecutive increasing values in L[m . . . e]. if A(L, m, e) > 0: return A(L, m, e)
# Otherwise, there are no three consecutive increasing values in L[b . . . e]. return −1
The worst-case runtime of the algorithm satisfies the recurrence T (n) = 2T (n/2) + Θ(1) soT(n)=Θ(nlog22)=Θ(n)bytheMasterTheorem(sincea=2>1=20 =bd).
Page 1 of 5 over…
Fall 2008 Term Test # 2 — Solutions CSC 373 H1 Marking Scheme:
• Structure: [2 marks]
clear attempt to give a divide-and-conquer algorithm, to give a high-level English description of the main idea, to analyze the runtime of the algorithm
• Algorithm: [5 marks]
correct algorithm, including correct use of divide-and-conquer method and at most linear runtime
• Correctness: [1 mark]
good explanation of algorithm’s behaviour
• Runtime: [2 marks]
correct analysis of algorithm’s runtime
Marker’s Comments/Error Codes:
• DC: [−3 marks]
The algorithm is not divide and conquer.
• WN: [−0.5 marks]
Using Wrong Notation. The question specifically asks to ”give an algorithm A(L, b, e)”, and specified the output format. Marks were deducted for using a different notation.
• B: [−2···−0.5 marks] Insufficient or missing base cases.
• NI: [−1 mark]
Not Informative explanation for correctness. Simply restating your algorithm in words does not add any clarity or help prove correctness.
• A surprising number of people had trouble with the indexes. When you’re working out a mathematical function (for example, to find the middle element, or the length given b and e) it helps to work through at least one example; it’s better to try a few until you convince yourself that your function works.
Question 2. [16 marks]
A vertex cover in an undirected graph G = (V, E) is any subset of vertices C ⊆ V such that every edge in GhasatleastoneendpointinC(i.e.,∀(u,v)∈E,u∈Corv∈C,orboth). Intheminimumvertex cover problem, the input is a graph with a positive integer weight w(v) for each vertex v ∈ V , and we want to find a vertex cover C with the smallest possible total weight w(C) = v∈C w(v). In this question, we are interested in constructing minimum weight vertex covers for trees, using dynamic programming.
General Marker’s Comments: The question asks for finding a vertex cover (which covers edges), not a dominating set! The answers that solved the dominating set problem got at most 8/16, with further marks taken off for other mistakes.
Part (a) [3 marks]
Given a tree T = (V, E), state precisely the information contained in your dynamic programming table(s)—
in particular, specify the exact sub-problem whose solution is stored in each entry of your table(s).
Sample Solution:
For every vertes v ∈ V , define
In(v): minimum weight of all vertex covers that contain v, within the subtree rooted at v;
Out(v): minimum weight of all vertex covers that do not contain v, within the subtree rooted at v.
Page 2 of 5 cont’d. . .
Fall 2008 Term Test # 2 — Solutions CSC 373 H1 Marking Scheme:
• Structure: [1 mark]
clear attempt to describe tables stored at each node in the tree, to store the minimum weight of vertex covers with specific properties
• Correctness: [2 marks]
correct tables, that would allow one to find overall answer
Part (b) [6 marks]
Give a recurrence that could be used to compute the entries in your table. Justify that your recurrence is
correct.
Sample Solution:
For all leaves v, In(v) = w(v) (v is included) and Out(v) = 0 (there is no edge to cover).
For all internal vertices v,
In(v) = w(v) + min In(u), Out(u)
u child of v
(v covers every edge (v,u) to v’s children, so none of them must be included—though
they can be) and
Out(v) = In(u) u child of v
(every edge (v, u) to v’s children must be covered by including u). Marking Scheme:
• Structure: [1 mark]
clear attempt to give complete recurrence, including appropriate base cases, and to justify its correctness based on the recursive structure of optimal solutions
• Recurrence: [3 marks] correct recurrence
• Justification: [2 marks] good justification of correctness
Marker’s Comments: A lot of solutions did not even attept to justify the answer. Part (c) [7 marks]
Give an algorithm that will determine the vertices in a minimum vertex cover, given the entries in your table. Briefly justify that your algorithm is correct, and analyze its runtime.
Sample Solution:
The call VC(r), where r is the root of tree T, will return a vertex cover of T with
Page 3 of 5
over…
minimum total weight. VC(v):
if In(v)Out(v): return VCIn(v)
else:
return VCOut(v)
VCIn(v):
C ={v}
for u child of v:
C = C ∪ VC(u)
return C
VCOut(v): C =∅
for u child of v:
C = C ∪ VCIn(u)
return C
Fall 2008 Term Test # 2 — Solutions CSC 373 H1
For all vertices v, VC(v) returns a minimum weight vertex cover for the subtree rooted at v, VCIn(v) returns a minimum weight vertex cover that contains v, for the subtree rooted at v, and VCOut(v) returns a minimum weight vertex cover that does not contains v, for the subtree rooted at v. Each routine’s correctness follows immediately from the reasoning given in the previous part for the recurrence relation.
The algorithm’s runtime is Θ(n) in the worst-case (where n = |V |), because either VCIn(v) or VCOut(v) is called exactly once for each vertex v.
Marking Scheme:
• Structure: [1 mark]
clear attempt to give algorithm that makes use of table values to compute a minimum vertex cover, to justify the correctness of the algorithm, and to analyze its runtime
• Algorithm: [4 marks]
correct algorithm, making good use of table values
• Justification: [1 mark]
good justification of correctness
• Runtime: [1 mark]
correct analysis of algorithm’s runtime
Marker’s Comments: A lot of solutions did not even attept to justify the answer.
Question 3. [7 marks]
Use the Ford-Fulkerson algorithm to compute a maximum flow in the network below (where each edge has the indicated capacity). State precisely each augmenting path that you use—you must use the path given below the picture as your first augmenting path. Justify that your flow is maximum—for full marks, your justification should not be based on the non-existence of a larger flow or of an augmenting path.
a
3
s 8 b 10 c 8 t
3
33
0/8 0/10 0/8 Augmenting path P = s −→ b −→ c −→ t
Page 4 of 5
Residual capacity ∆f(P) = 8 (fill this in) cont’d. . .
d
10
10
5
5
Fall 2008
Term Test # 2 — Solutions
CSC 373 H1
Sample Solution:
0/10 0/5
P = s −→ a −→ t
0/5 0/10 P = s −→ d −→ t
∆ f ( P ) = 5 ∆ f ( P ) = 5
5/10 0/3
P =s−→a−→c←−b−→d−→t
8/10 0/3 5/10
Total flow |f | = f (s, a) + f (s, b) + f (s, d) = 8 + 8 + 5 = 21.
∆f(P)=3
This flow is maximum because the cut χ = (Vs,Vt) with Vs = {s,a}, Vt = {b,c,d,t} has capacity c(χ) = c(s,b)+c(s,d)+c(a,c)+c(a,t) = 8+5+3+5 = 21, and |f| c(χ) for all flows f and cuts χ.
Marking Scheme:
• Structure: [2 marks]
clear attempt to use augmenting paths to increase the flow until no more augmentation is possible, and to justify that the flow is maximum by giving an explicit minimum-capacity cut
• Augmentations: [3 marks]
correct augmenting paths and augmentation along those paths
• Cut: [2 marks]
correct minimum cut to justify that flow is maximum
Marker’s Comments:
• Some answers used minimum cuts implicitely in the answer. Those answers received full marks only if the justification was clear and correct; in the future you should state the minimum cut explicitely.
• “There is no path” is not a proof. The quesiton explicitely tells you not to use this kind of argument. But even if it didn’t, proving non-existence is very tricky: if you can’t find something, it doesn’t mean it’s not there. Justifications that simply stated that there is no path, without justfying it, received zero marks.
Page 5 of 5 Total Marks = 33 End of Solutions