Midterm Exam: Fundamental Algorithms
The midterm exam will take place in the second hour (8:00-9:00) of class
on Monday March 5. It will be closed book and closed notes.
The topics covered will include:
- Order of magnitude comparisons.
- Solving recurrence equations.
- Worst-case analysis of simple algorithms
- n^2 sorts: Selection sort and Insertion Sorts
- n log n sorts: Heapsort, Mergesort, Quicksort
- Lower bounds on comparison sort.
- Linear time sorts: Bin sort, bucket sort.
- Binary search trees.
I will only ask about material that has been covered in lecture.
I will not ask about the derivation of the average-case running time of
quicksort, though I may ask about the result. I will not ask about any
material that is presented in the lecture in the first hour of class on