What the final will cover

The final exam will be comprehensive, and will cover everything we have covered in this course. You should start by reviewing the topics listed in the reviews for the first two midterms.

Here is a list of topics we have covered since the second midterm:

• Section 7.1: Basics of BTrees. You should know how to handle search, insertion, and deletion in BTrees.
• Section 7.1.8: V-H Trees. You should know how to make a V-H tree from a BTree of arity 4, and how to handle insertions into a V-H tree.
• Section 11.2: The Huffman algorithm. You should know how to build a Huffman tree from a frequency table, and how to use that tree to both encode and decode text.
• Sections 10.1 and 10.2: Basics of hash tables. You should know what a hash function is, and you should understand basic strategies for managing collisions: chaining, open addressing with linear probing and open addressing with quadratic probing.