CSC300: Homework (Heap Problems)

Contents [0/1]

Homework (Heap Problems) [1/1]

(Click here for one slide per page)


Homework (Heap Problems) [1/1]

No video for this week.

+ Read Algorithms through the end of 2.5 (you can skip 2.2,2.3).

+ Do the following eight problems on paper.  Be sure to do the starred ones.

  + 2.4.2 Criticize the following idea: To implement find the maximum in
    constant time, why not use a stack or a queue, but keep track of the
    maximum value inserted so far, then return that value for find the maximum?
    (Don't confuse find-the-max and remove-the-max)
  
  + 2.4.4 Is an array that is sorted in decreasing order a max-oriented heap?

  + 2.4.5 Give the heap that results when the keys E A S Y Q U E S T I O N
    are inserted in that order into an initially empty max-oriented heap.

  + 2.4.9* Draw all of the different heaps that can be made from the five
    keys A B C D E, then draw all of the different heaps that can be made from
    the five keys A A A B B.  (Draw min heaps.)

  + 2.4.11 Suppose that your application will have a huge number of insert
    operations, but only a few remove the maximum operations. Which
    priority-queue implementation do you think would be most effective: heap,
    unordered array, or ordered array?  (Also say why.  Don't confuse
    find-the-max and remove-the-max)

  + 2.4.12 Suppose that your application will have a huge number of find the
    maximum operations, but a relatively small number of insert and remove the
    maximum operations. Which priority-queue implementation do you think would
    be most effective: heap, unordered array, or ordered array?  (Also say why.
    Don't confuse find-the-max and remove-the-max)
  
  + 2.4.15* Design a linear-time certification algorithm to check whether an
    array pq[] is a min-oriented heap.  (The method MinPQ.isMinHeap does this
    recursively.  What would an iterative solution be?  You should make sure
    you understand this and can do it without looking at MinPQ.isMinHeap.)

  + 2.4.27* Find the minimum. Add a min() method to MaxPQ. Your implementation
    should use constant time and constant extra space.  (Argue that your
    solution is constant time/space.) 


Revised: 2008/03/17 13:01