Tuesday, September 3, 2002
- course /instructor info
- reading - you really must!
- hws -
- please make sure they are easy to read
(type if needed)
- be concise, to the point and structured in your solutions
- no "garbage", please
- web page
- "Why do I need it today?"
- Selection sort
- Performance: best (O(n^2)), worst (O(n^2)),
- Insertion sort
- Performance: best (O(n)), worst (O(n^2)),
- data structures: array or link-list?
- Performance: best, worst, average --?
- "Intermission": Analysis
Back to Sorting... Lecture
- Big-O, little-o, Theta, Big-Omega, little-omega
- a good summary is on pg.4
- Probability review Lecture
- Hiring problem & analysis
- Randomly permuting arrays
Max, Min, Median, other statistics Lecture
- same technique but for median and other stats: Lecture
(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.
- HeapSort Lecture
- priority queues (PQ)
- heap - an PQ implementation
- Lower bounds. Counting, Radix, andBucket sorts
Mergeable Priority Queues: Leftist Heaps
- Median and other statistics
Dynamic statistics data structure: Lecture
- Search trees: Lecture
- General - unballanced: performance problems, but can wor for random
- 2-3-4 trees --> implement as red-black trees
- a 2-3-4 node <==> a subtree with a black node root and
- trace correspondance of all 2-3-4 trees changes and red-black
rotations for insert.
- Hash tables Lecture
- maintain Red-Black tree + subtree size for each node
- binary search for i-th element