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.
- Lecture 01: Wed, Jan 21.
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: Mon, Jan 26.
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: Wed, Jan 28.
Methods for solving recureences: recursion tree, guess-and-verify
Read: CLRS, section 4 (skip complicated parts)
- Lecture 04: Mon, Feb 2.
Other methods: (domain/range) substitution, "master" theorem (for
common case when T(n) = aT(n/b) + f(n)).
Read: CLRS, section 4.1-4.3.
- Lecture 05: Wed, Feb 4.
More on master theorem (intuition for proof). Quicksort. Idea for
Read: CLRS, section 4.3-4.4, 7.1-7.2.
- Lecture 06: Mon, Feb 9.
Randomized Quicksort. Methods for computing sums: bounding terms
method, integral method.
Read: CLRS, section 7.3, Appendix A.
- Lecture 07: Wed, Feb 11.
Heaps. Heapsort. Priority Queues.
Read: CLRS, section 6.
- Lecture 08: Wed, Feb 18.
Lower Bound for Comparison based sorting. Beating the lower bound:
counting sort, radix sort.
Read: CLRS, section 8.1-8.3.
- Lecture 09: Mon, Feb 23.
Medians and order statistics: randomized and worst-case selection.
Read: CLRS, section 9.
- Lecture 10: Wed, Feb 25.
Hash Tables. Hashing by Chaining. Universal Hash Functions.
Read: CLRS, section 11.1-11.3.
- Lecture 11: Mon, Mar 2.
Constructing Universal Hash Functions.
Open Addressing. Linear, Quadratic, Double, Ideal hashing.
Analysis under Ideal Hashing.
Read: CLRS, section 11.3-11.4.
- Lecture 12: Wed, Mar 4.
Binary Search Trees. Tree Walks (in-order, post-order, pre-order).
Basic Ops (Insert, Delete, Search, Max, Min, Succ, Pred).
Read: CLRS, section 12.1-3.
- Lecture 13: Mon, Mar 9.
BST Sorting. Connection with Quicksort. Randomly Built Binary Search
Trees. Balanced Search Trees with O(log n) worst case Ops: 2-3-Trees
Read: 2-3-Trees handout, CLRS,
section 12.4 (skip complicated parts).
- Lecture 14: Wed, Mar 11.
Read: everything so far.
- Lecture 15: Mon, Mar 23.
Dynamic Programming, longest common subsequence.
Read: CLRS, sec 15.1,15.4.
- Lecture 16: Wed, Mar 25.
More dynamic programming (text allignment, matrix chain
CLRS, sec 15.2,15.3.
- Lecture 17: Mon, Mar 30.
Greedy algorithms. Activity selection.
CLRS, sec 16.1-16.2.
- Lecture 18: Wed, Apr 1.
CLRS, sec 16.3.
- Lecture 19: Mon, Apr 6.
More Huffman Codes. Fractional and 0-1 Knapsack. Aggregate analysis:
CLRS, sec. 16.3, 17.1, 17.2.
- Lecture 20: Wed, Apr 8.
Incrementing binary counter, dynamic tables (expand/contract).
CLRS, 17.1-2, 17.4.
- Lecture 21: Mon, Apr 13.
Graphs, their representations. Breadth-first search.
BFS: analysis, properties, classification of edges.
- Lecture 22: Wed, Apr 15.
Depth-First Search: analysis, parenthesis and white-path theorem,
clasisfication of edges.
- Lecture 23: Mon, Apr 20.
Minimal spanning trees.
CLRS, 22.3-4, 23.1
- Lecture 24: Wed, Apr 22.
Prim's and Kruskal's algorithms. Introduction to single-source
shortest paths. Dijkstra's algorithm (start).
CLRS, sec. 23, 24 (before 24.1).
- Lecture 25: Mon, Apr 27.
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 26: Wed, Apr 29.
All-pairs shortest paths. Matric multiplications approach,
CLRS, sec 25.1-2.
- Lecture 27: Mon, May 4.
Introduction to Number Theory and Cryptography. RSA encryption.
CLRS, sec 31.
Back to the course page