Structure
The exam will consist of autograded multiple choice, fill in the blank questions, 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.
The coding question will require you to use a multi-dimensional list to solve a creative problem, similar to those seen in mp_automata (but simpler).
Concepts
The exam will cover material up to and including 3/31/25. While you may see some review questions from previous content, the focus will be on new material which includes:
- Asymptotic Efficiency (Technically review content but applicable throughout the semester)
- Definition and what it means in practice
- Dominant term
- Determining the big O of a code block.
- Python Lists (A focus on 2D list indexing as seen in mp_automata)
- 1D and 2D list indexing
- Fundamentals of NumPy
- Python Sets
- Python built-in operations for the set ADT
- Jaccard Similarity
- 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
- Sorting Algorithms
- The conceptual differences and Big O for:
- SelectionSort
- InsertionSort
- quickSort
- mergeSort
- Fundamentals of recursion
- The ability to define or choose the appropriate:
- Base Case
- Recursive Step
- Combining Step
- The ability to read and interpret recursive code
You should be familiar with mp_automata as well as labs up to and including lab_recursion. The coding question will require you to be familiar with 2D Lists / Matrices at the level presented in mp_automata!