COSC 300: Advanced Data Structures

Describe how to implement a priority queue using a Binary Search Tree (BST). What are the asymptotic average case running times of the two main priority queue operations?
Show the results of performing the following operations on a binomial queue. A letter, i.e., 'A', means insert 'A' into the heap. An asterisk, '*' means to remove the largest item from the heap. Show your work at each step and indicate what the results of each remove operation are. Use the standard alphabetic ordering, so Z > A.
```
H E L * L O * W O R * * L D
```
Describe an efficient algorithm for converting a min heap to a max heap. What is the asymptotic worst case running time for your algorithm?
Give the definition for a greedy algorithm, a brute-force algorithm, a divide-and-conquer algorithm, and a dynamic programming algorithm. Give one example of each type of type of algorithm.

State what's wrong with the following recursive function:

int foo(int x) {
  return (x == 0 ? 1 : foo(x-2) + foo(x-1) + 1);
}

Bonus trivia question: Who created the Quicksort algorithm? In what journal was it first published and it what year?
Last modified: Oct. 12, 2009

Dr. Donald L. Simon, simon@mathcs.duq.edu