Lecture 03: Tue, Sep 18.
"Master theorem" (MT) for common case when T(n) = aT(n/b) + f(n).
Intuition for proof of MT. Other examples of divide-and-conquer:
binary search, stock profit (same as maximum subarray), Karatsuba
multiplication, matrix multiplication, VLSI layouts.
Read: CLRS, sections 4.5-4.6 (4.6 optional), 4.1-2.
Lecture 05: Tue, Oct 2.
Lower Bound for Comparison based sorting. 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: Tue, Oct 9.
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: Tue, Oct 23.
Read: everything so far.
Lecture 08: Nov 6.
Dynamic Programming. Rod Cutting, Longest Common Subsequence, Text
Read: CLRS, sec 15.1, 15.4, Notes
on Text Alignment (.pdf)
Lecture 10: Tue, Nov 20.
Greedy algorithms. Activity selection.
Greedy proof techniques: always stay ahead, local swap. Huffman Codes.
On-Line algorithms: Prefix Free Codes (SOLE encoding).
CLRS, sec 16.1-3. Notes
on Greedy Algorithms (.pdf), Notes on PFEs (.pdf)
Lecture 11: Tue, Nov 27.
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).
CLRS. 22.1-3. Start 22.4.
Lecture 12: Tue, Nov 27.
Minimal spanning trees. Prim's and Kruskal's algorithms. Introduction
to single-source shortest paths. Dijkstra's algorithm (non-negative
weights), BFS revisited (simple queue in Dijkstra).
CLRS, 22.4, 23, 24 (before 24.1), 24.3, 24.5.