CSCI-GA.1170-003/004 Fundamental Algorithms, Lecture Summaries
Fundamental Algorithms (CSCI-GA.1170)
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
running time. Asymptotic notation (O, o, Omega, omega,
Theta). Divide-and-conquer (recursion). Introduction to Recurrences.
Better sorting: merge sort. Analysis of its running time (recursion tree).
Lecture 01: Mon, Sep 12
Read: CLRS, skim section 1, read sections 2-3 (skim 3.2).
Analysis of merge sort (recursion tree).Methods for solving
recureences: recursion tree, guess-and-verify (induction),
(domain/range) substitution, intro to "master theorem" (MT) for common
case when T(n) = aT(n/b) + f(n).
Lecture 02: Mon, Sep 19
Read: CLRS, section 4.3-4.5 (skim 4.5).
"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.
Lecture 03: Wed, Sep 21
Read: CLRS, sections 4.5-4.6 (4.6 optional), 4.1-2.
Quicksort. Randomized Quicksort. Heaps. Heapsort. Priority Queues.
Lecture 04: Mon, Oct 3
Read: CLRS, section 7.1-7.3, optional 7.4, section 6.
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,
Lecture 05: Mon, Oct 17
Read: CLRS, sections 8.1-8.3, 9, 12.1.
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. Connection
with Red-Black Trees. Augmenting Data Structures. Maintaining number
of nodes, application to dynamic order statistics (rank(T,k), myrank(T,node)).
Lecture 06: Wed, Oct 26
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: Mon, Oct 31
Read: everything so far.
Dynamic Programming. Rod Cutting, Longest Common Subsequence, Text
Lecture 8: Nov 7
Read: CLRS, sec 15.1, 15.4, Notes
on Text Alignment (.pdf)
DP techniques (overlapping subproblems, memorization, smal->large
ordering). Matrix chain multiplication. Introduction to Greedy
Algorithms: DP for Activity Selection.
Lecture 9: Wed, Nov 14
CLRS, sec 15.2-3, 16.1.
Greedy algorithms. Activity selection.
Greedy proof techniques: always stay ahead, local swap. Huffman Codes.
Lecture 10: Wed, Nov 21
CLRS, sec 16.1-3.
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).
Lecture 11: Mon, Nov 28
CLRS. 22.1-3. Start 22.4.
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).
Lecture 12: Mon, Dec 5
CLRS, 22.4, 23, 24 (before 24.1), 24.3, 24.5.
Bellman-Ford algorithm (no negative cycles), acyclic graphs.
Solving difference constraints.
All-pairs shortest paths. Matric multiplications approach.
Floyd-Warshall. Transitive Closure. Johnson's algorithm.
Lecture 13: Mon, Dec 12
CLRS, sec 24.1-2, 25.1-3.
Introduction to Number Theory and Cryptography. RSA encryption.
Lecture 14: Mon, Dec 14
CLRS, sec 31.
Back to the course page