Test Fall 2019 Question 1. Divide-and-Conquer [20 marks]
Write a divide-and-conquer algorithm that finds the maximum difference between any two elements of a given array of n numbers (not necessarily distinct) in O(n) time. For example, on input A = [4.5,10,−2,π,−7.115], your algorithm should return 17.115.
Justify briefly that your algorithm is correct and runs within the required time bound. (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 logn) if a = bd, and Θ(nlogb a) if a > bd.)
Note: For full marks, your answer must make use of the divide-and-conquer method. Partial marks will be given for an O(nlogn) divide-and-conquer method.
Sample Solution:
The maximum difference is simply the difference between the maximum and the minimum elements. We find the pair (minimum element, maximum element) recursively (using divide- and-conquer), then return their difference.
MaxDiff(A):
min,max ← MinMax(A) return max − min
MinMax(A):
if n = 1: // n = size of A
return A[1],A[1] else:
m ← ⌊n/2⌋
n1,m1 ← MinMax(A[1…m]) n2,m2 ←MinMax(A[(m+1)…n]) return min(n1,n2),max(m1,m2)
Procedure MinMax runs in time Θ(n) because its worst-case running time satisfies the recur- rence T (n) = 2T (n/2) + Θ(1), so MaxDiff also runs in time Θ(n).
Question 2. Greedy [20 marks]
Consider the following Art Gallery Guarding problem. We are given a set {p1,p2,…,pn} of positive numbers that specify the positions of paintings in a long hallway in an art gallery. We want to position guards in the hallway to protect every painting, using as few guards as possible. Suppose that a guard at location x can protect all paintings within 1 distance (i.e. in interval [x − 1, x + 1]), and any painting protected by at least one guard is considered protected.
We propose to solve this problem using the following greedy algorithm.
Sort the positions so p1 p2 ··· pn.
G ← ∅ # current set of guards’ locations
g ← −∞ # position of rightmost guard in G = maximum number in G for i ← n,…,1: # start at the rightmost painting and move to the left
if pi − g > 1: # pi is unprotected by the guards currently in G # Place a guard 1 unit to the right of pi.
g ← pi + 1
G = G ∪ {g}
return G page 1 of 3
over…
CSC373H1 Midterm (a) (2.5 marks) The above algorithm does not quite work. Provide a counterexample of painting positions
where the above algorithm would use more guards than required. No justification is needed.
(b) (2.5 marks) The above algorithm can be fixed by changing a single line. What is the change needed to make the algorithm always find a solution with the minimum number of guards? For partial marks, you can propose any other greedy algorithm which always finds a solution with the minimum number of guards.
(c) (2.5 mark) What is the time complexity of your algorithm from part (b)?
(d) (10 marks) Prove that your fix to the algorithm (or any other greedy algorithm you proposed) in (b) is correct.
(e) (2.5 marks) The exhibition is then moved to another gallery where the art is put up on easels in a wide open space, i.e., each painting is placed at a 2D point pi = (xi , yi ). Suppose we use a variant of your fixed greedy algorithm from part (b), where you sort the paintings by x-coordinate, check if a painting pi is greater than a unit Euclidean distance from the current guard (i.e., ∥pi − g∥ > 1), and if so, place a new guard at g ← pi + (1, 0). Either prove that this algorithm will always return a solution with the minimum number of guards or provide a counterexample.
Note: The Euclidean distance is given by ∥(x,y) − (x′,y′)∥ = (x − x′)2 + (y − y′)2. Sample Solution:
Let G0,G1,…,Gn be the partial solutions generated by the algorithm. Say Gi is “promising” iff there is some solution Gi∗ such that:
• Gi ⊆ Gi∗ (Gi∗ contains every guard position in Gi );
• ∀g ∈ Gi∗ − Gi , g > gi = max{g ′ ∈ Gi } (every additional guard in Gi∗ is positioned further right
than the last guard in Gi)—we say Gi∗ “extenda” Gi if it satisfies the first two properties;
• |Gi∗| is minimum (Gi∗ is optimum).
Claim: ∀i 0, Gi is promising. Proof: By induction on i.
BaseCase: G0=∅.LetG∗beanyoptimumsolution.ThenG0⊆G∗and∀g∈G∗,g>g0=−∞. Ind. Hyp.: Suppose i 0 and Gi∗ extends Gi .
Ind. Step: Either Gi+1 = Gi or Gi+1 = Gi ∪ {pi+1 + 1}.
Case 1: If Gi+1 = Gi, then Gi+1 = Gi ⊆ Gi∗ and ∀g ∈ Gi∗ −Gi+1,g ∈ Gi∗ −Gi ⇒ g > gi = gi+1. So Gi∗ already extends Gi+1.
Case2: IfGi+1=Gi∪{pi+1+1},theneitherpi+1+1∈Gi∗orpi+1+1Gi∗.
Subcase A: If pi+1 + 1 ∈ Gi∗ then Gi∗ already extends Gi+1: Gi+1 = Gi ∪ {pi+1 + 1} ⊆ Gi∗
and ∀g ∈ Gi∗ − Gi +1 , g > gi ∧ g pi +1 + 1 ⇒ g > gi +1 = pi +1 + 1.
Subcase B: If pi+1 + 1 Gi∗ then pi+1 > gi + 1 (from the algorithm) so pi+1 is unpro-
tected by any guard in Gi. This means there is some g ∈ Gi∗ −Gi with g > gi (by the
I.H.) and g pi+1 +1 (else pi+1 would be unprotected by Gi∗). Then, every painting
protected only by g is also protected by pi+1 +1. So G∗ = G∗ −{g}∪{pi +1+1}
i+1 i
Hence, Gi is promising for i = 0,1,…,n. In particular, Gn is promising: Gn ⊆ Gn∗ and
is an optimum solution that extends Gi+1.
∀g∈Gn∗ −Gn,g>gn,forsomeoptimumGn∗.ButthismeansGn=Gn∗,asdesired.
page 2 of 3 cont’d. . .
Test Fall 2019
Question 3. Dynamic Programming [20 marks]
A new country Oddistan has a currency oddollar with coins of denomination 3, 5 and 7.
(a) (2.5 marks) Can you always purchase an item worth n oddollars, where n >= 5, with exact change in coins. If so, explain why; otherwise, provide the smallest counterexample n 5 (no justification is needed).
(b) (2.5 marks) For all n that you can pay for exactly, is the combination of coins unique? If so, explain why; otherwise, provide a example n and two ways to make up n using the coin denominations.
(c) (15 marks) A new government wants to the change the coin denominations to 3, 11 and 13. Write a dynamic programming algorithm that returns (true/false) whether an exact change can be made for n oddollars, given any integer n > 0. Clearly define the quantity that your dynamic programming algorithm computes, write a Bellman equation, briefly argue that your Bellman equation is correct, identify the initial conditions, and analyze the time and space complexity of your algorithm.
Sample Solution:
RecursiveStructure: IfN =3x+11y+13zforsomex,y,z∈N,theneitherx>0andN = 3 + 3(x − 1) + 11y + 13z, or y > 0 and N = 11 + 3x + 11(y − 1) + 13z, or z > 0 and N = 13+3x+11y+13(z−1).
Array: For i = −24,−23,…,−1,0,1,…,N, A[i] = True if i nuggets can be purchased exactly (False otherwise).
Recurrence: A[−24]=···=A[−1]=False
A[0] = True (0 = 3 · 0 + 11 · 0 + 13 · 0) A[i]=A[i−3]∨A[i−11]∨A[i−13],fori=1,…,N (fromargumentabove)
page 3 of 3
over…
Algorithm:
for i = −24,…,−1: A[i] ← False
A[0] ← True for i = 1,…,N:
A[i]=A[i−3]∨A[i−11]∨A[i−13] return A[N ]
Runtime is Θ(N ).