Structure and content to be determined.
Structure
The exam will consist of a combination of autograded multiple choice, fill in the blank, and a single coding question. Most multiple choice questions will allow you to submit twice, first for full credit and the second for a moderate amount of points.
Concepts
The exam will cover material up to and including Wednesday April 10th. You should be familiar with everything covered in class or as part of an assignment. That said, to help you identify core topics that you should definitely prepare for:
- Trees
- Implementation details, how to use, and Big O for:
- Binary Trees
- Binary Search Trees
- Balanced Binary Search Trees (AVL Trees)
- Huffman Trees
- Algorithm details including correct output order and Big O for:
- Pre-Order Traversal
- In-Order Traversal
- Post-Order traveral
- Depth-First Traversal (Note: Can be implemented using pre, in, or post)
- Breadth-First Traversal
- Nearest Neighbor Search
- AVL Rotations (When to use, how to use, and what the rotations do)
- Graphs
- Implementation details, how to use, and Big O for:
- Edge Lists
- Adjacency Matrices
- Adjacency Lists
- Algorithm details including correct output order and Big O for:
- Depth-First Traversal
- Breadth-First Traversal
- Hash Tables
- Necessary properties of a hash function
- Necessary components for a hash table
- Methods for addressing hash collisions:
- Separate Chaining
- Linear Probing
- Quadratic Probing
- Double Hashing
- The Simple Uniform Hashing Assumption
- The performance of the hash table under SUHA
The coding question for exam 3 will be implementing one of the Binary Search Tree ADT functions. This includes:
- Find
- Insert
- Remove
- Traversals