Data Structures and Algorithms Assignment #2 Solution

This assignment covers Chapters 6 (Heaps),  7 (Quicksort), and 9 (Medians  and Order  Statistics) of the text

[100 marks  total].

Submit  electronically,  before midnight on Friday,  using the submission link on Blackboard for Assignment #2, a file named yourFirstName-yourLastName.pdf containing  your solution to this assignment (a .doc or .docx file is also acceptable, but  .pdf is preferred).

 

1.  Heaps. [10 marks  total]

 

(a)  What  are the minimum  and maximum  number  of elements  in a heap of height h?  [2 marks] (b)  Show that an n-element heap has height blog nc.  [2 marks]

(c)  Show that in any subtree of a max-heap,  the root of the subtree contains the largest value occurring anywhere  in that subtree.  [4 marks]

(d)  Is the sequence h23, 17, 14, 6, 13, 10, 1, 5, 7, 12i a max-heap? Why or why not?  [2 marks]

 

2.  Heaps. [10 marks  total]

 

(a)  Illustrate the operation  of Max-Heapify(A, 3) on the array A = h27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 10i. [2 marks]

(b)  Illustrate the  operation  of Build-Max-Heap(A) on the  array  A = h5, 3, 17, 10, 84, 19, 6, 22, 9i. [3 marks]

(c)  You are given a list of numbers  for which you need to construct a min-heap.  How would you use an algorithm for constructing a max-heap  to construct a min-heap?  [5 marks]

 

3.  Heapsort. [10 marks]

Argue the correctness  of Heapsort using the following loop invariant.

 

At the start of each iteration of the for  loop, the subarray A[1 . . . i] is a max-heap  containing the i smallest  elements of A[1 . . . n], and the subarray A[i + 1 . . . n] contains  the n − i largest elements  of A[1 . . . n].

 

4.  Quicksort. [20 marks  total]

The Quicksort algorithm contains  two recursive calls to itself.  After Quicksort calls Partition, it recursively  sorts  the left sugary  and then  it recursively  sorts  the right subarray. The second recursive call in Quicksort is not really necessary; we can avoid it by using an iterative control structure. This technique, called tail  recursion, is provided  automatically by good compilers.  Consider  the  following version of Quicksort, which simulates  tail recursion:

 

Algorithm 1 function  Tail-Recursive-Quicksort(A, p, r)

1:  while p < r do

2:       q = Partition(A, p, r)

3:       Tail-Recursive-Quicksort(A, p, q − 1)

4:       p = q + 1

5:  end while

 

 

(a)  Argue that Tail-Recursive-Quicksort(A, 1, n), where n is the number  of elements in array  A, correctly  sorts  the array  A. [10 marks]

(b)  Compilers  usually execute  recursive procedures  by using a stack that contains  pertinent informa- tion,  including  the parameter values, for each recursive call.  The information for the most recent call is at  the  top  of the  stack,  and  the  information for the  initial  call is at  the  bottom.  Upon calling a procedure,  its information is pushed  onto the stack;  when it terminates, its information is popped.   If we assume  that array  parameters are represented by pointers,  the  information for each  procedure  call on the  stack  requires  O(1)  stack  space.   The  stack  depth  is the  maximum amount of stack  space used at any time during  a computation.

Describe a scenario in which Tail-Recursive-Quicksort’s stack depth  is Θ(n)  on an n element input  array.  [10 marks]

 

5.  Partition. [10 marks]

The colours of the Dutch  national flag are red (R),  white (W),  and blue (B). The Dutch  national flag problem  is to rearrange an array  of n characters R, W, and  B so that all the  Rs come first,  the  Ws come next,  and  the  Bs come last.  Design a linear  in-place algorithm for this  problem  and  show that your algorithm is O(n).  Hint:  Use the idea of the Partition algorithm of Quicksort.

 

6.  Select. [10 marks]

In the  algorithm Select,  the  input  elements  are divided  into  groups  of 5.  Will the  algorithm work in linear  time  if they  are divided  into  groups of 7?  Argue that Select does not  run  in linear  time  if groups of 3 are used.

 

7.  Largest i numbers in  sorted order. [30 marks  total]

Given  a  set  of n  numbers,   we wish to  find  the  i  largest  in  sorted  order  using  a  comparison-based algorithm. Find the algorithm  that implements each of the following methods  with the best asymptotic worst-case  running  time,  and analyze  the running  times of the algorithms  in terms  of n and i.

 

(a)  Sort the numbers,  and list the i largest.  [10 marks]

(b)  Build a max-priority-queue from the numbers,  and call Extract-Max i times.  [10 marks]

(c)  Use an  order-statistic algorithm to  find the  ith  largest  number,  partition around  that number, and sort the i largest  numbers.  [10 marks]