Homework 5

Download the corresponding ipynb file here: hw-5.ipynb.

Data Structures

Exercise 1 (5 + 3 + 2 points) Given an array arr[\ ] consisting of n integers, where each array element represents the height of a building situated on the x-axis, the task is to check if it is possible to select 3 buildings, such that the third selected building is taller than the first selected building and shorter than the second selected building. You are not allowed to reorder the buildings and your algorithm should run in O(n)-time.

  1. Describe the logic of your algorithm.

  2. Implement your algorithm in Python.

  3. Analyze the time-complexity of your algorithm.

Exercise 2 (7 points) Implement your own Queue (FIFO) class in Python using two stacks (LIFO). Note that the list data-type implements a stack in Python. Your Queue class must implement the following methods:

  • enQueue(x): appends x into the queue.

  • deQueue(): pops the head of the queue.

  • peek(): returns the head of the queue (without deleting).

Exercise 3 (3 points) For each of the above methods, describe its time and (extra)-space complexities in big O-notation. You may optionally add the amortized costs.