• The final exam will be cumulative. Be sure to review material from the first two exams.
• Also review all the lecture notes (linked at the bottom of the course web page).
• The final exam is Wednesday, 11 December, at 2:00 and 4:00. You can come at either time, regardless of which section you are enrolled in. (You must pick one time or the other, because I'll need a break between.)

1. Understand the formal definition of big-O and be able to explain why we use it instead f simply counting operations.
2. Under what conditions does the O(n log n) lower bound for sorting apply?
3. What is an iterator? Why do we use them?
4. How do C++ templates differ from Java generics?
5. What are the relative advantages and disadvantages of B trees as compared to binary search trees?
6. Under which conditions are B-trees better than binary search trees?
7. How do Linear Congruential Generators work? What are their strengths and weaknesses?
8. By definition, which algoritms are in P?
9. By definition, which algorithms are in NP?
10. Is matrix multiplication in NP?
11. What is an online algorithm? How does it differ from an offline algorithm?
12. Describe an online sorting algorithm.
13. Describe an O(n log n) algorithm for either the first-fit or best-fit bin packing problem.
14. Give examples of where the algorithm with the lowest big-O worst-case runtime is not the most commonly used algorithm.
15. Rod problem from www.cs.umb.edu/~henryzlo/cs310/problems1/problems.pdf
16. What data structure is typically used to implement a priority queue?
17. List several uses of a priority queue.
18. How does a d-Heap differ from a binary heap? When/Why is one used?
19. Give pseudocode for merging disjoint sets.
20. With respect to merging disjoint sets, what is "path compression"
21. What is the "halting" problem?
22. Give a sketch of the proof that the halting problem is undecidable.
23. What is a Huffman Code?
24. Give pseudocode for an algorithm to generate a Huffman code.
25. Why is there a greedy algorithm for generating a Huffman code, but no greedy algorithm for generating an optimal binary search tree?
26. What are the key aspects of a divide and conquer algorithm?
27. What are the key aspects of a dynamic programming algorithm?

Updated Saturday, 23 November 2019, 11:39 AM