Typical Final Questions
CMPS 102 - W05

1. List the operations that can be done efficiently
on some data structure we covered.

2. What is the relationship between building
a binary search tree and quick sort?
Ditto about the average case analysis of
building a binary search tree and quick sort?

3. Dynamic programming:
solve some problem;
determine recurrence, order of evaluation and running time;
retrieve the solution.

4. Build a Huffman code from a frequency table of
a set of symbols. Analysis of running time.

5. Aggregate method for amortized analysis.

6. What is an amortized analysis?

7. Insert and Delete an a B-tree or RB-tree.
What ops.. can be done efficiently.

8. What operations can be done efficiently on
a binomial heap? What is the advantage over a standard
heap based on an almost complete binary tree.

9. Execute some operation on a given binomial heap.

10. What are basic examples of dynamic programming and
divide and conquer algs?

11. Give a high level description of Strassen's matrix
multiplication. What is its recurrence?

12. What is the Discrete Fourier Transform?

13. Give a high level description of the FFT alg.
Why is it a big deal? 

14. We might give you some operations
and you have to find efficient implementations
by augmenting a data structure we covered in class.

Strategy for learning:
- Go over all homeworks and solutions.
- Go over class notes and read text.
- Study in groups.