Exam Preparation

The CS 240 final exam will cover material in the textbook, labs, and PAs that is related to the following topics:

• Runtime and space complexity. Be able to reason about the differences between worse case, average case, and amortized case analysis. Be able to compare and contrast two implementations of an algorithm.
• Hashing, including sizing and probing strategies for dealing with collisions.
• Deriving cost function T(n) from Java or pseudocode.
• Binary trees, including their properties (full, complete, perfect), height, leaf count, etc, and traversal orderings (pre-, in-, and post-order).
• Binary search Trees, including insert, find, and remove operations as described in the textbook.
• AVL trees, including computing balance factors and depths.
• Priority queues, including their array-based implementation using heaps.
• Huffman trees, including their construction and encoding and decoding.
• Graphs, including their properties (directed, undirected, weighted, cycles, paths), representations (adjacency matrix and adjacency lists), traversals (depth-first, breadth-first), and topological sort.

A practice exam is available.