Lecture 05: Wed, Oct 5.
Lower Bound for Comparison based sorting.
Lower bound for Element Uniqueness.
Beating the lower bound:
counting sort, radix sort.
Medians and order statistics: randomized and worst-case selection.
Introduction to Binary Search Trees. Tree Walks (in-order, post-order,
Read: CLRS, sections 8.1-8.3, 9, 12.1.
Lecture 06: Wed, Oct 12.
Binary Search Trees. Basic Ops (Insert, Delete, Search, Max, Min,
Succ, Pred). BST Sorting. Connection with Quicksort.
Randomly Built Binary Search Trees. Balanced Search Trees with
O(log n) worst case Ops: 2-3-Trees. Insertion, deletion.
Augmenting Data Structures. Maintaining number
of nodes, application to dynamic order statistics (rank(T,node),
Read: CLRS, section 12.1-3, 12.4 (skip complicated parts),
2-3-Trees handout, CLRS,
skim 14.1-14.2 (replace RB-trees by 2-3-trees).
Lecture 07: Wed, Oct 19.
Dynamic Programming. Rod Cutting, Longest Common Subsequence, Text Alignment.
Read: CLRS, sec 15.1, 15.4, Notes
on Text Alignment (.pdf)
Lecture 08: Wed, Oct 26.
Read: everything so far (not including dynamic programming).
Lecture 10: Wed, Nov 9.
Activity Selection. Greedy algorithms and proof techniques: greedy always stay ahead,
local swap. Huffman Codes.
CLRS, sec 16.1-3.
Notes on Greedy Algorithms (.pdf).
Lecture 11: Wed, Nov 16.
Graphs, their representations. Breadth-first search: analysis,
properties, classification of edges. Depth-First Search:
analysis, parenthesis and white-path theorem, clasisfication of
edges. Test for acyclicity (no back edges).