ESO207A -Homework 2 Solved

DataStructures and Algorithms
: Heaps,
 
 

1.   Solutions have to be submitted on Gradescope. For this, each problem should start on a newsheet. If this is not followed then it may not be possible to grade your answers.

2.   For each problem, write your name, Roll No., problem number, the date and the names ofany students with whom you collaborated. Remember that you must write the answer and the algorithm in your own words.

3.   For questions in which algorithms are asked for, your answer should provide the following: (a) A clear description of the algorithm in English and/or pseudo-code, where, helpful, (b) A proof/argument of the correctness of the algorithm, and, (c) an analysis of the running time of the algorithm.

Full marks will be given only to correct solutions which are described clearly. Convoluted and unclear descriptions will receive low marks.



Problem 1. Heap. The following is an alternative routine to build a max-heap by permuting the elements of an array. It uses the subroutine Max-Heap-Insert(A,v). Here A is a max-heap where the elements are stored in the array A[1...N], where, N is the maximum capacity of the array, and (ii) the field A.heapsize that counts the number of items in the heap A. This routine takes the heap A and inserts v into the max-heap. It also increments A.heapsize by 1.

1.   Consider the following procedure for building a heap.

procedure Build-Max-Heap(A,n) // Build Max Heap for the elements in A[1,...,n]

1.                   A.heapsize = 1

2.                   for i = 2 to n

3.                   Max-Heap-Insert(A,A[i])

           Show that this procedure takes O(nlogn) time.                                                                                                   (10)

2.   Show a worst case input and analyze it to show that on that input the procedure takesΩ(nlogn) time. Hence this algorithm takes Θ(nlogn) time worst-case. (15)

Problem 2. Young tableau.                                                                                                                                         (12.5 × 4 = 50)

An m × n Young tableau is an m × n matrix such that the entries of each row are in sorted order from left to right and the entries of each column are in sorted order from top to bottom. Some of the entries may be ∞ that are treated as non-existent items. Thus a Young tableau can be used to hold r ≤ mn finite numbers. Note that an m × n tableau Y is empty if Y [1,1] = ∞ and is full if Y [m,n] < ∞. An example Young tableau is  

1

1.   Give an algorithm for Extract-Min on a non-empty m×n Young tableau that runs in time O(m + n). (Hint: Follow Min-Heapify.)

2.   Show how to insert a new element into a non-full m × n Young tableau in O(m + n) time.

3.   Using no other sorting method as a subroutine, show how to use an n × n Young tableau to sort n2 numbers in O(n3) time.

4.   Given an O(m+n)-time algorithm to determine whether a given number is stored in a given m × n tableau.

Problem 3. Stack: a span problem. You are given an array P[1,...,n] giving the daily price quotes for a stock for n consecutive days. The span of the stock’s price on a given day i is the maximum number of consecutive days that the stock’s price is less than or equal to its price on day i. (This includes day i, so span is at least 1). For example, suppose P is the array {50,45,35,40,60,50,55}. Then, the span array for these 7 consecutive days is {1,1,1,2,5,1,2}. An O(n2) algorithm follows in a straightforward way from the definition. Design an O(n) (linear-time) algorithm and provide an analysis.              (20+5)

2