# CS-330: Algorithms

## Lectures outline

Last changed: Tuesday, September 3, 2002

Lecture 1 :

1. Introduction
• 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
• web page
• misc
• Algorithms
• History/origins
• "Why do I need it today?"
2. Sorting
• Why?
• Selection sort Lecture 2:
• Performance: best (O(n^2)), worst (O(n^2)), average (O(n^2))
• Insertion sort
• Performance: best (O(n)), worst (O(n^2)), average (O(n^2))
• data structures: array or link-list?
• MergeSort Lecture 3:
• Performance: best, worst, average --?
• Recurrence
3. "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
4. 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.
• HeapSort Lecture 8(+9)
• priority queues (PQ)
• PQ-sort
• heap - an PQ implementation
• Lower bounds. Counting, Radix, andBucket sorts
5. Max, Min, Median, other statistics Lecture 11
• Median and other statistics
6. Mergeable Priority Queues: Leftist Heaps Lecture 12
7. 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.
• Hash tables Lecture 14
8. Dynamic statistics data structure: Lecture 15
• maintain Red-Black tree + subtree size for each node
• binary search for i-th element