Assignment 3
Objective: Understanding of sorting algorithm, algorithmic analysis and design
Assignment from Book:
6.5-6 - Show how to implement a first-in, first-out queue with a priority queue. Then, show how to implement a stack with a priority queue (we covered these in intermediate programming).
6.1-1 - What are the minimum and maximum numbers of elements in a heap of height h?
6-2 (only part of the question)
- A d-ary heap is like a binary heap, where each node has d
children (instead of 2).
a) how would you represent a d-ary heap in an array
(how would you find the children?)
b) what is the height of the of a d-ary heap in terms
of n and d? (hint: why is the height of a normal heap log2n?)
c) discuss what needs to occur when you call EXTRACT-MAX
in a d-ary heap.
7.1-1 - Using Figure 7.1 as a model, illustrate the operation of PARTITION on the array A= <13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21>
8.2-4 - Describe an algorithm, that, given n integers in the range of 0-k, preprocesses its input and the answers any query about how many of the n integers fall into a range [a..b] in O(1) time. Your algorithm should run in Q(n+k) time. Hint: look at counting sort!
Program Description: In this assignment, you will create a sorter(s), which graphically demonstrates how a sorting algorithm works. Generally, after any change to the internal data structure, the graphical image should be updated. Students using O(n2) sorts are required to implement two algorithms (to make it fair to the ones implementing harder sorts). Here is a site that may help you:
http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
| Name | Sort |
| Askew, Ashley | BubbleSort/Insertion |
| Attaway, John | ShakerSort/Insertion |
| Carroll, James | QuickSort |
| Flandez, Jose | Shell/Lucky |
| Frederick, Chad | CountingSort |
| Holak, James | Insertion/Shell |
| Jones, Jonathan | Selection/Bubble |
| Kirtley, Richard | MergeSort |
| Klausner, Eric | Insertion/Selection |
| Ou, LySreng | CountingSort |
| Tolbert, Nadira | Bubble/Selection |
| Wilson, David | RadixSort |
| Zolja, Peter | Lucky/Selection |
Program Requirements: For this program, you can choose your favorite sorting algorithm, implement it, then graphically represent it. The example below uses bars, which is generally effective, but could be just about anything so long as it makes sense (you may want to run this by the instructor first).
Example:
Program Turnin: Use WebSubmit to submit the written assignment. You will show your code demo your program in class.