Finally, you will be given an exam question drawn randomly from the following list:

1. Class TreeMap
2. Class HashMap
3. Class PriorityQueue
4. Quicksort
5. Mergesort
6. Heapsort
7. Dijkstra’s algorithm
8. Huffman’s algorithm

You should be prepared to give a short presentation (maximum 5 minutes) on each of these subjects.

For subjects 1 to 3 you can structure your presentation as follows:

a) Name the most important operations of the class.
b) Name one or more examples of application.
c) Describe how the class has been implemented.
d) Specify the running time of its operations using Big-Oh notation.

For subjects 4 to 8 you can structure your presentation as follows:

a) Specify input and output for the algorithm.
b) Describe the main idea of the algorithm.
c) Specify its running time using Big-Oh notation.

Your presentations can be verbal and/or use overhead projector slides. You can also show material on a laptop computer, provided that it is ready to display without any delay.


November 2011 Keld Helsgaun