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, Sep 8
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, Sep 13
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, Sep 15
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, Sep 20
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, Sep 22
Read: CLRS, section 4.1, optional 4.2.
Quicksort. Randomized Quicksort.
Lecture 06: Mon, Sep 27
Read: CLRS, section 7.1-7.3, optional 7.4.
Heaps. Heapsort. Priority Queues.
Lecture 07: Wed, Sep 29
Read: CLRS, section 6.
Lower Bound for Comparison based sorting. Beating the lower bound:
counting sort, radix sort.
Lecture 08: Mon, Oct 4
Read: CLRS, section 8.1-8.3.
Medians and order statistics: randomized and worst-case selection.
Lecture 09: Wed, Oct 6
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, Oct 13
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, Oct 18
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, Oct 20
Read: 2-3-Trees handout, CLRS,
skim 14.1-14.2 (replace RB-trees by 2-3-trees).
Lecture 13: Mon, Oct 25
Read: everything so far.
Dynamic Programming, Rod Cutting.
Lecture 14: Wed, Oct 27
Read: CLRS, sec 15.1.
Longest common subsequence.
Lecture 15: Mon, Nov 1
Read: CLRS, 15.4.
More DP: matrix chain multiplication, text allignment.
Lecture 16: Wed, Nov 3
CLRS, sec 15.4, Notes on Text
Greedy algorithms. Activity selection.
Lecture 17: Wed, Nov 10
CLRS, sec 16.1.
Greedy proof techniques: always stay ahead, local swap. Intro to Huffman Codes.
Lecture 18: Thu, Nov 11
CLRS, sec 16.2-16.3.
Lecture 19: Mon, Nov 15
CLRS, sec. 16.3.
On-Line Prefix Free Codes (SOLE encoding).
Lecture 20: Wed, Nov 17
Notes on PFEs (.pdf)
Demo of SOLE. Graphs, their representations. Breadth-first search.
Lecture 21: Mon, Nov 22
BFS: analysis, properties, classification of edges.
Lecture 22: Tue, Nov 23
DFS analysis, parenthesis and white-path theorem, clasisfication of
edges. Topological Sort.
Lecture 23: Mon, Nov 29
Minimal spanning trees. Prim's and Kruskal's algorithms. Introduction
to single-source shortest paths. Dijkstra's algorithm (start).
Lecture 24: Wed, Dec 1
CLRS, sec. 23, 24 (before 24.1).
Dijkstra's algorithm (non-negative weights), BFS revisited (simple
queue in Dijkstra).
Lecture 25: Mon, Dec 6
CLRS, sec. 24.3, 24-5.
Bellman-Ford algorithm (no negative cycles), acyclic graphs.
All-pairs shortest paths. Matric multiplications approach.
Lecture 26: Wed, Dec 8
CLRS, sec 24.1-2, 25.1.
Floyd-Warshall. Transitive Closure. Johnson's algorithm.
Lecture 27: Mon, Dec 13
CLRS, sec 25.2-3.
Introduction to Number Theory and Cryptography. RSA encryption.
Lecture 28: Wed, Dec 15
CLRS, sec 31.
Back to the course page