Comp 251: Mid-term examination #3
Instructor: Jérôme Waldispühl November 24th, 2020.
• Answer the questions on Crowdmark.
• You have 3 hours to complete this exam and 30 extra minutes to account for any technical issue.
You must initiate your submission within 3 hours from the start. If you meet any difficulty while uploading your solution 15 minutes before the end of the submission timeframe (3h + 30min), email us at cs251@cs.mcgill.ca with you solution. We will NOT proceed to any manual upload or address any request beyond this time-point.
• You can update your submission on Crowdmark during the timeframe of the exam.
• The clarity and presentation of your answers is part of the grading. Answers poorly presented may not be graded. This includes the clarity of the writing or the quality of the image you uploaded. It is
your responsibility to ensure that the image has the good resolution and contrast.
• Keep the size of any file you upload on Crowdmark as small as possible to avoid technical issues.
• Unless specified, all answers must be explained.
• Partial answers will receive credits.
• The conciseness of your answer is part of the grading. An answer that is unnecessarily long or poorly
structured will be penalized.
• This is an open book examination.
• It is strictly forbidden to use any external help, including online tutoring systems, or to provide aid to
someone else. You are not allowed to communicate to anyone during the exam.
• It is strictly forbidden to share or disseminate this exam or any information related to this exam.
• This exam contains a mandatory academic integrity statement that you should agree with and sign.
We will not grade the exam otherwise.
• This exam contains 11 pages.
Question:
1
2
3
4
5
6
Total
Points:
8
16
20
24
12
20
100
Score:
1
Statement of Academic Integrity
In submitting this exam, I confirm that my conduct during this exam adheres to the Code of conduct and academic integrity (https://www.mcgill.ca/students/srr/academicrights). I confirm that I did NOT act in such a way that would constitute cheating, misrepresentation, or unfairness, includ- ing but not limited to, using unauthorized aids and assistance, personating another person, and committing plagiarism. I will not share or disseminate this exam on any platform or through personal communication.
Write your name and date to sign this statement. We will not grade your exam if you do not agree with and sign this statement.
COMP 251 – Midterm #3 Page 2 of 11 Fall 2020
Short answers
1. True or False? Circle your answers. No justification. Wrong answers will receive a penalty of -1.
(a) (2 points) When a graph G has no negative weight cycles, the Bellman-Ford algorithm and Di- jkstra’s algorithm always produce the same output (i.e. same shortest path estimates d[v] and predecessors π[v] for all vertices v of G).
A. True B. False
(b) (2points) Thetotalamortizedcostofasequenceofnoperations(i.e.thesumoveralloperations, of the amortized cost per operation) gives a lower bound on the actual cost of the sequence of operations.
A. True B. False
(c) (2 points) All dynamic programming algorithms satisfy an optimal substructure property. A. True B. False
(d) (2 points) We apply the dynamic programming algorithm we have seen in class to solve the weighted activity scheduling problem. An instance of this problem is show below (Figure A). The weight of an activity ai is noted Vi and is equal to the length (or duration) of the activity. The predecessor of an activity ai is noted pred(ai). We filled the dynamic programming table M below (Figure B). Has this dynamic programming table (Figure B) been correctly filled?
A. True B. False
a1
a2
0123456
(A) Instance of the weighted activity scheduling problem.
activity (ai)
a1
a2
a3
a4
pred
–
–
a1
a2
M[ai]
2
2
4
5
Vi + M[pred(ai)] M[ai−1]
2 0
2 2
4 2
5 4
a3
a4
(B) Dynamic programming table M
COMP 251 – Midterm #3 Page 3 of 11
Fall 2020
Master theorem
2. Recall the master theorem.
Theorem 1 (Master theorem) Let a ≥ 1 and b ≥ 1 be two constants, and f (n) a function. ∀n ∈ N+ we define T (n) as:
T(n)=aTn+f(n),where n isinterpretedas⌊n⌋or⌈n⌉. bbbb
Then, we can find asymptotical bounds for T (n) such that:
1. If f(n) = O(nlogb a−ε) with ε > 0, then T(n) = Θ(nlogb a).
2. If f(n) = Θ(nlogb a · logp n), then T(n) = Θ(nlogb a logp+1 n).
3. Iff(n)=Ω(nlogba+ε)withε>0,anda·fn≤cf(n),∀n>n0 withc<1andn0 >0.Then b
T(n) = Θ(f(n)).
When possible, apply the master theorem to find the asymptotic behaviour of T (n) below. Indicate which case has been applied (no justification needed), or alternatively explain why you cannot apply it. √n
(a) (4points) T(n)= 2·T(2)+logn
(b) (4points) T(n)=4·T(n)+n2 2
(c) (4points) T(n)=6·T(n)+n2 ·log(n) 3
(d) (4points) T(n)=T(n)+n·(2−cosn) 2
COMP 251 – Midterm #3
Page 4 of 11
Fall 2020
Flow networks
3. We consider the flow network G below. Each edge is annotated with its flow followed by the capacity of the edge.
u 3/3 v
s 1/3 1/4 0/3 t
1/3 2/2 3/4
xy
(a) (5 points) Compute the residual graph.
5/5
3/3
(b) (5 points) Find an augmenting path in the residual graph. Write its sequence of vertices below and indicate the bottleneck β (i.e. the maximum value of the flow that can be augmented on that path).
COMP 251 – Midterm #3 Page 5 of 11 Fall 2020
(c) (5 points) Add the flow of the augmenting path to G, and show the values of the flow . u/3v
/5 /3 s/3/4/3t
/3/2/4
xy
(d) (5 points) The flow is now maximal. Compute the minimum cut and give its capacity.
COMP 251 – Midterm #3 Page 6 of 11 Fall 2020
Stable matching
4. Recall the Gale-Shapley algorithm for solving the stable matching problem. Let G = (V,E) be a bipartite graph whose vertices are divided between two disjoint sets A and B. Each vertex α ∈ A has a full list of preferences of vertices β ∈ B and, each vertex β ∈ B has a full list of preferences of verticesα∈A.WecallS⊂Eaperfectmatchingif∀α∈A, ∃!β∈Bsuchthat(α,β)∈S,and ∀β∈B, ∃!α∈Asuchthat(α,β)∈S.WesayamatchingSisstableif(α,β)and(α′,β′)∈S such that α and β′ would prefer to be matched together rather than with their current assignment in S.
Algorithm 1 Gale-Shapley
S←∅
while ∃ α ∈ A not yet matched do
β ← first β ∈ B to which α has not yet proposed. if β is not matched then
S ← S ∪ (α, β)
else if β prefers α to its current match α′ then
S ← S \ (α′, β) ∪ (α, β) end if
end while return S
We say that α ∈ A is a valid match of β ∈ B if it exists a stable matching S in which they are matched. We showed in class that the Gale-Shapley algorithm returns a stable matching that is optimal (or A- optimal) from the point-of-view of A (i.e. all α ∈ A receive their best valid assignment).
Here, we want to show that the matching computed with this algorithm produces the worst valid assignment for all the β ∈ B. You will demonstrate this claim with a contradiction. Let β ∈ B be the first element of B that is not receiving its worst valid assignment in a matching S∗ computed by the Gale-Shapley algorithm. We call α the partner of β in S∗ (i.e. (α, β) ∈ S∗).
Since α is not the worst valid assignment for β, it exists another stable matching S in which β is matched with its worst valid assignment, say α′.
Note: Unnecessary long answers may not be graded. Respect the limit of words.
(a) (6 points) Justify why α must have a different partner β′ than β in S. In other words, show that (α,β′) ∈ S and (α′,β) ∈ S with α ̸= α′ and β ̸= β′(max 50 words).
COMP 251 – Midterm #3 Page 7 of 11 Fall 2020
(b) (5 points) Argue that β prefers α to α′ (max 50 words).
(c) (5 points) Show that α prefers β to β′ (max 50 words).
(d) (8 points) Conclude (max 50 words).
COMP 251 – Midterm #3 Page 8 of 11 Fall 2020
Amortized analysis
5. Consider the implementation of a queue with two stacks S1 and S2. The method enqueue pushes a new element in S1. The method dequeue pops an element from S2 if the latter is not empty. Otherwise (if S2 is empty), it pops all elements from S1, pushes them into S2, and then returns the last element inserted in S2. We want to determine the amortized complexity the operations enqueue and dequeue.
(a) (4 points) Let n be the number of elements in the queue. What is the individual worst-case running time complexity of the functions enqueue and dequeue? No justification needed.
(b) (8 points) Using the accounting method, calculate the amortized cost per operation of any se- quence of m enqueue and dequeue operations. In particular, demonstrate that the credit can never be negative.
Note: Make a concise answer (4-6 sentences). Unnecessary long answers may not be graded.
COMP 251 – Midterm #3 Page 9 of 11 Fall 2020
Divide-and-Conquer
6. Consider 2D arrays of integers b such that each row and column is sorted by increasing order. We show below an example of such array with 4 rows and 4 columns.
2 142530 3 152830 7 153243
20 28 36 58
The objective of this problem is to design an efficient algorithm to find an element with value v in such array. Here, we assume that the array b has the same number n of rows and columns. Moreover, thisnumbernofrowsandcolumnsisapowerof2(i.e.n=2k withn≥0).
(a) (5 points) Let x = b(n, n) (i.e. the value stored in b at index (n, n)). We want to show that if 22 22
v > x we can safely eliminate a region (to be determined by yourself) of the array b from the search. Indicate which region of the array (i.e. which indices) remains to be explored.
Note: Briefly justify your answer in (2-3 sentences). You can also illustrate your answer with a drawing of the array if it helps.
(b) (5 points) Let y = b(n + 1, n + 1). We want to show that if v < y we can safely eliminate a 22
region (to be determined) of the array b from the search. Indicate which region of the array (i.e. which indices) remains to be explored.
Note: Briefly justify your answer (2-3 sentences).
COMP 251 - Midterm #3 Page 10 of 11 Fall 2020
In the following, we denote a sub-matrix b[i, i′][j, j′] of b including rows i to i′ and columns j to j′ as follow. We also note the coordinates of x and y as (x1, x2) and (y1, y2).
bi,j . . . bi,x2 bi,y2 . . . bi,j′ . .. . . .. .
. . . . . .
′ ′ bx1,j ... bx1,x2 bx1,y2 ... bx1,j′
b[i,i][j,j]=by1,j ... by1,x2 by1,y2 ... by1,j′
...... . .. . . .. .
bi′,j . . . bi′,x2 bi′,y2 . . . bi′,j′
(c) (10 points) Deduce from your previous observations a divide-and-conquer method to search a value v in a sorted 2D array of integers. Using the notations above, write a pseudo-code describ- ing your algorithm. Your algorithm must use as an input the array b, the value v to be searched for, and the indices (i, i′) and (j, j′) of the region to explore. Here, (i, i′) are the indices of the first and last rows and (j, j′) the indices of the first and last columns to explore. It will return the index of the row and column if the value is found, and the pair (−1, −1) otherwise.
COMP 251 - Midterm #3 Page 11 of 11 Fall 2020