CPSC 320: Intermediate Algorithm Design and Analysis
Assignment #6, due Wednesday, March 26th, 2014 at 16:00
[6] 1. Vancouver’s Georgia street has many tall buildings, but only some of them have a clear view
of Stanle
...
CPSC 320: Intermediate Algorithm Design and Analysis
Assignment #6, due Wednesday, March 26th, 2014 at 16:00
[6] 1. Vancouver’s Georgia street has many tall buildings, but only some of them have a clear view
of Stanley Park. Auppose we are given an array A[1 : : : n] that stores the height of the n
buildings on Georgia street, indexed from Granville Street to Chilco Street. Building i has
a good view of Stanley Park if and only if every building to the west of i (those with higher
index) is shorter than i. Here is an algorithm that computes which buildings have a good
view of Stanley Park.
Algorithm GoodView(A)
initialize a stack S
for i 1 to n do
while S is not empty and A[i] > A[Top(S)] do
pop(S)
endwhile
push(S, i)
endfor
return S
What is the worst-case running time of algorithm GoodView as a function of n? Hint: use
amortized analysis.
Solution : Following the hint, let us define the potential function Φ(i) to be the size of
the stack at the end of the ith iteration of the for loop. We consider each iteration of the
for loop as an operation.
• Its real cost is in Θ(1) + k where k is the number of times the body of the while loop
is executed.
• Its potential difference Φ(i) − Φ(i − 1) = 1 − k since we perform 1 push and k pop
operations.
Hence the amortized cost of one loop iteration is Θ(1) + k + 1−k 2 Θ(1), which means that
the running time of the for loop (and hence of the function) is in Θ(n).
[12] 2. In this problem we consider a monotone priority queue that initially contains the n elements
1, 2, . . . , n, and operations Init, Delete and DeleteMin (note that there is no Insert
operation). Consider the following implementation using a boolean array A:
Init(n)
[Show More]