V22.0310-001 Basic Algorithms (Honors), Lecture Summaries
Basic Algorithms (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.
- Lecture 01: Tue, Sep 2.
Administrivia, introduction. Sorting. Insertion Sort. Analysis of its
running time. Asymptotic notation (O, o, Omega, omega, Theta).
Read: CLRS, skim section 1, read section 2.1, 2.2.
- Lecture 02: Thu, Sep 4.
Better sorting: merge sort. Analysis of its running time (recursion
tree + substitution methods). Comparison. Back to asymptotics
notation. Introduction to Recurrences.
Read: CLRS, section 2.3, 3 (skip 3.2 for now), 4.1, 4.2.
- Lecture 03: Tue, Sep 9.
4 methods for solving recureences: guess-and-verify (induction),
recursion tree, (domain/range) substitution, "master" theorem (for
common case when T(n) = aT(n/b) + f(n)).
Read: CLRS, section 4 (skip complicated parts)
- Lecture 04: Thu, Sep 11.
More on Master Theorem (including its proof). Methods for computing
sums: bounding terms method, integral method. Some examples of
Read: CLRS, section 4.3, 4.4.
- Lecture 05: Tue, Sep 16.
Quicksort. Randomized Quicksort.
Read: CLRS, section 7.
- Lecture 06: Thu, Sep 18.
Heaps. Heapsort. Priority Queues.
Read: CLRS, section 6.
- Lecture 07: Tue, Sep 23.
Lower Bound for Comparison based sorting. Beating the lower bound:
counting sort, radix sort.
Read: CLRS, section 8.
- Lecture 08: Thu, Sep. 25.
Lower bound for Element Uniqueness. Medians and order statistics:
randomized and worst-case selection.
Read: CLRS, section 9.
- Lecture 09: Tue, Sep. 30.
Hash Tables. Hashing by Chaining. Universal Hash Functions.
Read: CLRS, section 11.
- Lecture 10: Thu, Oct. 2.
Constructing Universal Hash Functions. Perfect hashing. Open
Addressing. Analysis under Ideal Hashing.
Read: CLRS, section 11.
- Lecture 11: Tue, Oct. 7.
Binary Search Trees. Tree Walks (in-order, post-order, pre-order).
Basic Ops (Insert, Delete, Search, Max, Min, Succ, Pred). Application
to Sorting. Randomly Built Binary Search Trees.
Read: CLRS, section 12 (skip analysis of random binary tree).
- Lecture 12: Thu, Oct. 9.
Balanced Search Trees with O(log n) worst case Ops. 2-3-Trees,
Red-Black Trees. Rotations.
Read: 2-3-Trees handout, CLRS, section 13.
- Lecture 13: Tue, Oct. 14.
Read: everything so far.
- Lecture 14: Thu, Oct. 16.
Dynamic Programming, longest common subsequence.
Read: CLRS, sec 15.
- Lecture 15: Tue, Oct. 21.
More dynamic programming (text allignment, matrix chain multiplication,
optimal search trees).
CLRS, sec 15.
- Lecture 16: Thu, Oct 23.
Greedy algorithms. Activity selection. Huffman Codes.
CLRS, sec 16.
- Lecture 17: Tue, Oct 28.
Huffman Codes, fractional and 0-1 Knapsack. Aggregate analysis:
CLRS, sec 16.2, 16.3, 17.1, 17.2.
- Lecture 18: Thu, Oct 30.
Incrementing binary counter, dynamic tables. Graphs, their
representations. Breadth-first search.
CLRS, sec. 17.1-2, 22.1-2.
- Lecture 19: Tue, Nov 4.
BFS: analysis, properties, classification of edges. Depth-First Search.
- Lecture 20: Thu, Nov 6.
DFS: analysis, parenthesis theorem, clasisfication of edges.
- Lecture 21: Tue, Nov 11.
Strongly Connected Components, minimal spanning trees.
CLRS, 22.4, 23.1
- Lecture 22: Thu, Nov 13.
Prim's and Kruskal's algorithms. Introduction to single-source
shortest paths. Properties of shortests path.
CLRS, sec. 23, 24 (before 24.1).
- Lecture 23: Tue, Nov 18.
Dijkstra's algorithm (non-negative weights), Bellman-Ford algorithm
(no negative cycles), BFS revisted (simple queue in Dijkstra), acyclic
CLRS, sec. 24.1-3.
- Lecture 24: Thu, Nov 20.
All-pairs shortest paths. Matric multiplications approach,
CLRS, sec 25.
- Lecture 25: Tue, Nov 25.
More on all-pairs shortest paths. Examples. Transitive Closure.
CLRS, sec 25.
- Lecture 26: Tue, Dec 2.
Maximum Flow. Definition, examples, basic properties. Residual Graphs,
augmenting paths. Cuts, mincut=maxflow theorem.
CLRS, sec. 26.1-2.
- Lecture 27: Thu, Dec 4.
More on mincut=maxflow. Ford-Fulkerson algorithm. Edmonds-Karp
CLRS, sec. 26.2.
- Lecture 28: Tue, Dec 9.
Application to maximum matching. Hall's marriage theorem. A telepathic
Read: CLRS 26-3.
Back to the course page