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
a3
0123456
(A) Instance of the weighted activity scheduling problem.
Vi + M[pred(ai)] M[ai 1]
(B) Dynamic programming table M
pred
–
2
2
a1
4
a2
2 0
2 2
4 2
5
M[ai]
5 4
a4
COMP 251 – Midterm #3 Page 3 of 11
Fall 2020
activity (ai)
a1
–
a2
a3
a4
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. 8n 2 N+ we define T (n) as:
T(n)=aT n +f(n),where n isinterpretedasbncordne.
b
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·f n cf(n),8n>n0 withc<1andn0 >0.Then T(n) = ⇥(f(n)). b
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
bbb
it. p (a) (4points) T(n)=
2·T(n)+logn 2
(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 ↵ 2 A has a full list of preferences of vertices 2 B and, each vertex 2 B has a full list of preferences of vertices↵2A.WecallS⇢Eaperfectmatchingif8↵2A, 9! 2Bsuchthat(↵, )2S,and 8 2B, 9!↵2Asuchthat(↵, )2S.WesayamatchingSisstableif@(↵, )and(↵0, 0)2S such that ↵ and 0 would prefer to be matched together rather than with their current assignment in S.
Algorithm 1 Gale-Shapley
S;
while 9 ↵ 2 A not yet matched do
first 2 B to which ↵ has not yet proposed. if is not matched then
S S [ (↵, )
else if prefers ↵ to its current match ↵0 then
S S \ (↵0, ) [ (↵, ) end if
end while return S
We say that ↵ 2 A is a valid match of 2 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 ↵ 2 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 2 B. You will demonstrate this claim with a contradiction. Let 2 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. (↵, ) 2 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 ↵0.
Note: Unnecessary long answers may not be graded. Respect the limit of words.
(a) (6 points) Justify why ↵ must have a different partner 0 than in S. In other words, show that (↵, 0) 2 S and (↵0, ) 2 S with ↵ 6= ↵0 and 6= 0(max 50 words).
COMP 251 – Midterm #3 Page 7 of 11 Fall 2020
(b) (5 points) Argue that prefers ↵ to ↵0 (max 50 words).
(c) (5 points) Show that ↵ prefers to 0 (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, i0][j, j0] of b including rows i to i0 and columns j to j0 as follow. We also note the coordinates of x and y as (x1, x2) and (y1, y2).
b[i, i0][j, j0] = 6bx1,j 6by1,j
. . .
...
. . .
bi,x2 .
bx1,x2
bi,y2 . . . . ...
bx1,y2 . . .
2 bi,j 6 .
bi,j0 3 . 7
bx1,j0 7
(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, i0) and (j, j0) of the region to explore. Here, (i, i0) are the indices of the first and last rows and (j, j0) 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.
. . .
by1,x2
4..... .....5
by1,y2 . . .
bi0,j . . . bi0,x2 bi0,y2 . . . bi0,j0
by1,j0 7
COMP 251 - Midterm #3 Page 11 of 11 Fall 2020