*Last changed:
Tuesday, September 3, 2002
*

__Lecture
1 ____:__

- Introduction
- Administrativia
- Algorithms
- History/origins
- "Why do I need it today?"

**Sorting**- Why?
- Selection sort
__Lecture 2__- Performance: best (
`O(n`), worst (^{^2})`O(n`), average (^{^2})`O(n^`)^{2})

- Performance: best (
- Insertion sort
- Performance: best (
`O(n)`), worst (`O(n`), average (^{^2})`O(n`)^{^2}) - data structures: array or link-list?

- Performance: best (
- MergeSort
__Lecture 3__- Performance:
**best**,**worst**,**average**--? - Recurrence

- Performance:

- "Intermission": Analysis
__Lecture 4__ **Big-O, little-o, Theta, Big-Omega, little-omega**- a good summary is on pg.4

- Probability review
__Lecture 5__ - Hiring problem & analysis
- Randomly permuting arrays
- Back to
**Sorting**...__Lecture 6__- QuickSort
- same technique but for median and other stats:
__Lecture 7__

(average case O(n)): do "binary search" on quicksort, skipping one of the halves of the partition (the one that does*not*contain the i-th element we are searching for). - while we're there: Max&Min:

"sort pairs", then search two "half-arrays": 1st places in the pairs - for min, 2nd places for max.

- same technique but for median and other stats:
- HeapSort
__Lecture 8____(+9)__- priority queues (PQ)
- PQ-sort
- heap - an PQ implementation

- Lower bounds. Counting, Radix, andBucket sorts

- QuickSort
- Max, Min, Median, other statistics
__Lecture 11__ - Median and other statistics
**Mergeable Priority Queues**: Leftist Heaps__Lecture 12__**Dictionaries:**- Search trees:
__Lecture 13__- General - unballanced: performance problems, but can wor for random case
- 2-3-4 trees --> implement as red-black trees
- a 2-3-4 node <==> a subtree with a black node root and
red non-roots
- trace correspondance of all 2-3-4 trees changes and red-black rotations for insert.

- a 2-3-4 node <==> a subtree with a black node root and
red non-roots

- Hash tables
__Lecture 14__

- Search trees:
- Dynamic statistics data structure:
__Lecture 15__- maintain Red-Black tree + subtree size for each node
- binary search for i-th element