CSCI-GA.1170-001/002 Fundamental Algorithms, Lecture Summaries

# Fundamental Algorithms (CSCI-GA.1170) Lecture Summaries

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 4. 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 02: Tue, Sep 11. 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).
Read: CLRS, section 4.3-4.5 (skim 4.5).
Introductory Notes (.pdf)

• Lecture 03: Tue, Sep 18. "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.
Read: CLRS, sections 4.5-4.6 (4.6 optional), 4.1-2.

• Lecture 04: Tue, Sep 25. Quicksort. Randomized Quicksort. Heaps. Heapsort. Priority Queues.
Read: CLRS, section 7.1-7.3, optional 7.4, section 6.

• Lecture 05: Tue, Oct 2. 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, pre-order).
Read: CLRS, sections 8.1-8.3, 9, 12.1.

• Lecture 06: Tue, Oct 9. 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. Augmenting Data Structures. Maintaining number of nodes, application to dynamic order statistics (rank(T,node), select(T,k)).
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: Tue, Oct 23. MIDTERM.

• Lecture 08: Nov 6. Dynamic Programming. Rod Cutting, Longest Common Subsequence, Text Alignment.
Read: CLRS, sec 15.1, 15.4, Notes on Text Alignment (.pdf)

• Lecture 09: Tue, Nov 13. DP techniques (overlapping subproblems, memorization, smal->large ordering). Matrix chain multiplication. Introduction to Greedy Algorithms: DP for Activity Selection. Greedy always stay ahead technique.

• Lecture 10: Tue, Nov 20. Greedy algorithms. Activity selection. Greedy proof techniques: always stay ahead, local swap. Huffman Codes. On-Line algorithms: Prefix Free Codes (SOLE encoding).
Read: CLRS, sec 16.1-3. Notes on Greedy Algorithms (.pdf), Notes on PFEs (.pdf)

• Lecture 11: Tue, Nov 27. 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).