Computer Science 431
Algorithms

Spring 2015, The College of Saint Rose

Home     Syllabus     Schedule

You may work alone or in groups of size 2 or 3 on this assignment. Only one submission per group is needed.

Textbook Problem

Binary Search Trees

Consider three-node integer-valued binary trees whose nodes contain the elements "1", "2", and "3".

Binary Min Heaps

Consider a binary min-heap like the ones we have discussed in class.

Generalized Heaps

The heaps we have discussed in class, where the heap is represented by a binary tree stored in an array, are one specific case of a more general structure called a d-heap. In a d-heap, each node has up to d children. So the binary heaps we have been considering would be 2-heaps. For the questions below, assume that the minimum value is stored at the root node (i.e., that it is a min-heap). Note: for the parts below where you are to draw a heap, you may submit a hand drawing if you do not wish to use a drawing program.

Note: for each of the question below, keep in mind that the values are inserted in the order shown, i.e., the first number is fully inserted into the structure before the second (and subsequent) numbers are considered at all.

Generalized Heapsort

You learned about d-heaps as you completed the questions in our previous lab. You also have learned about heapsort, which uses a 2-heap as an intermediate representation to sort the contents of an array. Let's consider a generalization of the heapsort idea:

• First, insert the elements to be sorted into a priority queue (PQ).
• Then, remove the elements one by one from the PQ and place them, in that order, into the sorted array.

For heapsort, the PQ is a 2-heap, but any PQ implementation would work (naive array- or list-based with contents either sorted or unsorted, a d-heap, or even a binary search tree). Depending on which underlying PQ is used, the sorting procedure will proceed in a manner similar, in terms of the order in which comparisons occur, to one of the other sorting algorithms we have studied (e.g., selection sort, quicksort, etc.).

Submitting

Before 11:59 PM, Monday, March 30, 2015, submit your problem set for grading. To complete the submission, upload an archive (a .7z or .zip) file containing all required files using Submission Box under assignment "PS6".

Grading

This assignment is worth 40 points, which are distributed as follows: