V22.0310-001/002 Basic Algorithms (Regular and Honors), Lecture Summaries
Basic Algorithms (Regular and Honors, V22.0310)
These lecture summaries can be viewed as the "past tense" course
syllabus. They are intended for people who missed the class, or would
like to briefly recall what was going on. Occasionally, I will include
brief plan for future lectures, but do not count on it. Suggested
reading from CLRS will be given after each summary.
Administrivia, introduction. Sorting. Insertion Sort. Analysis of its
Lecture 01: Wed, Jan 20
Read: CLRS, skim section 1, read section 2.1, 2.2.
Asymptotic notation (O, o, Omega, omega, Theta). Divide-and-conquer
(recursion). Introduction to Recurrences.
Better sorting: merge sort.
Lecture 02: Mon, Jan 25
Read: CLRS, 3 (skip 3.2 for now), start 2.3, 4 (before 4.1).
Analysis of merge sort (recursion tree + substitution methods). Comparison.
Methods for solving recureences: recursion tree, guess-and-verify
Lecture 03: Wed, Jan 27
Read: CLRS, section 2.3, 4.3-4.4.
Other methods: (domain/range) substitution, "master theorem" (MT) for
common case when T(n) = aT(n/b) + f(n). Intuition for proof of MT.
Lecture 04: Mon, Feb 1
Read: CLRS, section 4.3, 4.5, optional 4.6
Other examples of divide-and-conquer: binary search, stock profit
(same as maximum subarray), Karatsuba multiplication, matrix
multiplication, VLSI layouts.
Lecture 05: Wed, Feb 3
Read: CLRS, section 4.1, optional 4.2.
Quicksort. Randomized Quicksort.
Lecture 06: Mon, Feb 8
Read: CLRS, section 7.1-7.3, optional 7.4.
Heaps. Heapsort. Priority Queues.
Lecture 07: Wed, Feb 10
Read: CLRS, section 6.
Lower Bound for Comparison based sorting. Beating the lower bound:
counting sort, radix sort.
Lecture 08: Wed, Feb 17
Read: CLRS, section 8.1-8.3.
Medians and order statistics: randomized and worst-case selection.
Lecture 09: Mon, Feb 22
Read: CLRS, section 9.
Binary Search Trees. Tree Walks (in-order, post-order, pre-order).
Basic Ops (Insert, Delete, Search, Max, Min, Succ, Pred).
Lecture 10: Wed, Feb 24
Read: CLRS, section 12.1-3.
BST Sorting. Connection with Quicksort. Randomly Built Binary Search
Trees. Balanced Search Trees with O(log n) worst case Ops: 2-3-Trees
Lecture 11: Mon, Mar 1
Read: 2-3-Trees handout, CLRS,
section 12.4 (skip complicated parts).
2-3-trees: insertion, deletion. Connection with Red-Black Trees.
Augmenting Data Structures. Maintaining number of nodes, application
to dynamic order statistics (rank(T,k), myrank(T,node)).
Lecture 12: Wed, Mar 3
Read: 2-3-Trees handout, CLRS,
skim 14.1-14.2 (replace RB-trees by 2-3-trees).
Lecture 13: Mon, Mar 8
Read: everything so far.
Dynamic Programming, Rod Cutting.
Lecture 14: Wed, Mar 10
Read: CLRS, sec 15.1.
Rod cutting (top down and bottom-up), longest common subsequence.
Lecture 15: Mon, Mar 22
Read: CLRS, sec 15.1,15.4.
More DP: Longest common subsequence, text allignment.
Lecture 16: Wed, Mar 24
CLRS, sec 15.4, Notes on Text
Greedy algorithms. Activity selection.
Lecture 17: Mon, Mar 29
CLRS, sec 16.1-16.2.
Lecture 18: Wed, Mar 31
CLRS, sec 16.3.
More Huffman Codes. One-line prefix-free encodings.
Lecture 19: Mon, Apr 5
CLRS, sec. 16.3. Notes on PFEs (.pdf)
On-Line Prefix Free Codes (SOLE encoding).
Lecture 20: Wed, Apr 7
Notes on PFEs (.pdf)
Recap of SOLE. Graphs, their representations. Breadth-first search.
Lecture 21: Mon, Apr 12
BFS: analysis, properties, classification of edges.
Lecture 22: Wed, Apr 14
DFS analysis, parenthesis and white-path theorem, clasisfication of
edges. Topological Sort.
Lecture 23: Mon, Apr 19
Minimal spanning trees. Prim's and Kruskal's algorithms. Introduction
to single-source shortest paths. Dijkstra's algorithm (start).
Lecture 24: Wed, Apr 21
CLRS, sec. 23, 24 (before 24.1).
Dijkstra's algorithm (non-negative weights), Bellman-Ford algorithm
(no negative cycles), BFS revisted (simple queue in Dijkstra), acyclic
Lecture 25: Mon, Apr 26
CLRS, sec. 24.1-3.
All-pairs shortest paths. Matric multiplications approach,
Floyd-Warshall. Transitive Closure. Johnson's algorithm.
Lecture 26: Wed, Apr 28
CLRS, sec 25.1-2, 25.3.
Introduction to Number Theory and Cryptography. RSA encryption.
Lecture 27: Mon, May 3
CLRS, sec 31.
Back to the course page