This assignment is due on March 17 and should be submitted on Gradescope. All submitted work must be done individually without consulting someone else’s so- lutions in accordance with the University’s “Academic Dishonesty and Plagiarism” policies.

As a first step go to the last page and read the section: Advice on how to do the assignment.

Problem 1. (10 points)

Using O-notation, upperbound the running time of the following algorithm, where A is an array containing n integers. You can assume that mod is a basic mathemat- ical operation that takes O(1) time.

Problem 2. (25 points)

We want to build a stack for integer elements that in addition to the operations we saw during the lecture (push(e), pop(), top(), size(), and isEmpty()), also supports a getMinimum() operation that returns the minimum value of all elements stored in the stack.  All operations should run in O(1) time.  Your data structure should take O(n) space, where n is the number of elements currently stored in the data structure.

Example execution:

push(23)

push(4)

getMinimum()   returns 4   pop()                   returns 4   getMinimum()   returns 23

Your task is to:

[23]

[23, 4]

[23, 4]

[23]

[23]

a) Design a data structure that supports the required operations in the required time and space.

b) Briefly argue the correctness of your data structure and operations.

c) Analyse the running time of your operations and space of your data structure. 

Problem 3. (25 points)

We have n ≥ 1 lighthouses of distinct positive integer height on a line and these lighthouses need to communicate with each other.  We are given the heights of these lighthouses in an array A, where A[i] stores the height of lighthouse i.  Un- fortunately, the area these lighthouses are in is so remote that it doesn’t have phone lines and cell phone coverage is spotty at best. So the lighthouse keepers have found a different way to talk to each other: paper airplanes.

Assume all lighthouse keepers are (former) olympic champions in paper air- plane throwing, meaning that they can reach any lighthouse as long as there’s no lighthouse higher than the thrower’s lighthouse between them (the lighthouses are equipped with paper airplane catchers, so hitting the wall of the lighthouse counts as reaching it). Of course, because of the wind coming from the ocean, lighthouse keepers can only send their paper planes to the left (towards the land). More for- mally, lighthouse k can send a paper airplane to lighthouse i (i < k), if there is no lighthouse j such that i < j < k and A[k] < A[j]. Note that lighthouse i itself can be higher than lighthouse k because of the paper airplane catchers. We are interested in determining the leftmost lighthouse that each of the lighthouse keepers can reach. To distinguish between a paper airplane stopping at lighthouse 0 and passing over all lighthouses to the left of its starting point, we record the latter as −1 (imagining

an infinitely high lighthouse preceding all others where the airplane stops).

Example:

0          1         2         3         4

A : [5, 3, 1, 6, 4]: return [ −1, 0, 1, −1, 3]. A paper airplane thrown by the lighthouse keeper of lighthouse 0 passes over all lighthouses to its left and is thus recorded as  −1.   Lighthouse 1 can send their airplanes to lighthouse 0, but not beyond. Lighthouse 2 can communicate with lighthouse 1, but not with lighthouse 0, since lighthouse 1 stops any airplanes throw from lighthouse 2.  Lighthouse 3 is higher than any of the previous lighthouses and thus its airplanes pass over them. Finally, lighthouse 4 can send airplanes to lighthouse 3, but no further.

Your task is to design an algorithm that computes for each lighthouse the left- most lighthouse that its keeper can reach.  For full marks, your algorithm should

run in O(n) time.

a) Describe your algorithm in plain English.

b) Prove the correctness of your algorithm.

c) Analyze the time complexity of your algorithm.