10.2. Midterm 2¶
10.2.1. Midterm 2 Structure¶
Monday/Tuesday, April 13/14
100 points
Format
Similar to Midterm 1
The questions of of types that we can autograde: Multiple Choice, True/False, fill-in-the-blank, etc.
Anything from Chapter 1-7 is fair to ask about, but focus is on chapters 8 and 10. (Chapters 9 and 11-14 will be covered on the final.)
10.2.2. Topics (1)¶
Chapter 8: Sorting
How each of the algorithms work
Know the Best/Avg/Worst cost for each
Know the key proofs:
Lower bound for Exchange Sorts;
Why the worst case analysis for Radix Sort is \(\Theta(n \log n)\)
Lower bound for sorting
10.2.3. Topics (2)¶
Know how these sorting algorithms work, and their analysis.
Insertion Sort
Bubble Sort
Selection Sort
Shellsort
Mergesort
Quicksort
Heapsort
Radix Sort
10.2.4. Topics (3)¶
Chapter 10: Hashing
Solves exact match queries exceptionally well
What makes a hash function good or bad
Hash functions: Mod, Binning, mid-square, strings
What makes a collision resolution good or bad
linear probing (possibly by steps)
pseudo-random probing
quadratic probing
double hashing
How full the table ought to be for good performance (tradeoff of space vs. time)
Expected cost analysis for hashing (when properly implemented)
