|
|
Computer Science 211
Data Structures
Mount Holyoke College
Fall 2009
|
|
Lecture 11: Advanced Sorting Algorithms; Sorting Correctness and Complexity Proofs
Date: Monday, October 5, 2009
- Announcements
- Exam coming up next week
- In class, Wednesday 10/14
- Covers through today's class
- More details Wednesday
- Review on Friday (instead of a meeting in the lab)
- No new lab until after the exam
- Lecture Assignment Recap
- Merge sort details
- Quicksort details
- Correctness and Complexity Proofs
Due at the start of class, Wednesday, October 7.
Turn in short answers to these questions. Please turn in a hard
copy (typeset or handwritten are OK). We will discuss these problems
during class, so no late submissions are accepted.
- Bailey Problem 6.18, p. 146.
- Prove the complexity of the recursive insertion sort code in the
SortingComparisons example.
- Prove the correctness of the recursive insertion sort code in
the SortingComparisons example.