University of British Columbia - CPSC 320Assignment 6 solution

Document Content and Description Below

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]

Last updated: 1 year ago

Preview 1 out of 5 pages