Lecture 1 (Jan 8) 
General introduction. Definition of an algorithm.
Examples of simple computer models:
Turing model, RAM model, pointer based machines, oracles,
comparison model.
Uniformly bounded time, bit model of computation
(or: logarithmic model).
Definition and examples of an oracle.
Chapter 1 in CLR.
The Fibonacci example: introduce recursion, iteration,
and fast exponentiation.
Fast exponentiation.
Check here for some notes by David Eppstein.
Landau symbols: O, Omega, Theta, small o, small omega.
Examples of many complexity classes (linear, quadratic, polynomial, exponential).
Scribed notes on Landau symbols.

Lecture 2 (Jan 10) 
We covered all of chapter 2 and part of chapter 3 of CLR.
Introduction to recurrences.
The divideandconquer solution to Problem CLR 4.5 (chip testing).
Exercise: Show that our chip testing algorithm takes only O(n) time even if n is not a power of two.
Divideandconquer (Karatsuba) multiplication.
Mergesort, convex hulls in the plane.
Exercise: Describe in algorithmic form the linear time upper hull merge algorithm described in class.
Scribed notes on divideandconquer (part I).

Lecture 3 (Jan 15) 
The master theorem (statement only: CLR 4.5, but not CLR 4.6).
Recursion tree to explain the master theorem (CLR 4.4).
Brief mention of the substitution method (CLR 4.3).
Strassen matrix multiplication (CLR 4.2).
Euclid's algorithm.
(Hard) exercise: Show that the bit complexity of gcd(n,m)
is O(log n . log m).
Hamsandwich and pancake theorems and halfspace counting.
Scribed notes on divideandconquer (part II).

Lecture 4 (Jan 17) 
Linear time selection (chapter 9 of CLR): finding the kth smallest by the algorithm of Blum, Floyd, Pratt, Rivest and Tarjan (CLR 9.3).
We briefly looked at the medianof3 version of this algorithm and showed, by using recursion trees, that its complexity is big theta of n log n.
Linear expected time selection by Hoare's algorithm "FIND" (CLR 9.2).
Recurrence for binary search with binary and ternary oracles, and solution by induction for the ternary oracle.
Exercise: For binary search using a binary oracle, show that T(n) is not more than 2 + ceiling(log_2 n).
Scribed notes on divideandconquer (part III).

Lecture 5 (Jan 22) 
The induction method illustrated on mergesort (see scribed notes).
Ulam's problem (not included in the scribed notes or CLR).
Dynamic programming (chapter 15 of CLR).
The rodcutting example (CLR 15.1).
Computing binomial coefficients.
Note: All the material covered in class on
the topic of dynamic programming (three
lectures worth), the
rodcutting example excepted, has been
scribed.

Lecture 6 (Jan 24) 
Dynamic programming continued (and covered here).
Computing binomial coefficients.
The partition problem.
The traveling salesman problem.
The knapsack problem.

Lecture 7 (Jan 29) 
Dynamic programming continued (and covered here).
Assignment problem.
Longest common subsequence problem (CLR 15.4).
Optimal binary search tree (CLR 15.5).
Matrix chains (CLR 15.2).

Lecture 8 (Jan 31) 
Lower bounds (covered here).
Oracles.
Lower bounds via decision trees (CLR 8.1).
Examples include sorting and searching.
Lower bounds for board games.
Merging two sorted arrays using finger lists.

Lecture 10 (Feb 7) 
Introductory remarks about ADTs (abstract data types).
Elementary data structures such as lists, stacks and queues (CLR 10).
We deviate only slightly from this chapter.
For another account, see the
scribed notes on lists and stacks.
Classification and use of linked lists,
including representations of large integers and polynomials,
and free space lists.
Uses of stacks and queues in recursions and as
scratchpads for organizing future work.
Introduction to trees (CLR 10.4 and CLR Appendix B5):
free trees, ordered trees, position trees, binary trees, complete kary trees.
Height of complete kary tree.
Bijection between ordered trees (forests) and binary trees
via oldest child and next sibling pointers.

Lecture 11 (Feb 12) 
Continuing with trees (CLR 10.4 and CLR Appendix B5).
Complete trees: implicit storage.
Exercise: Generalize the navigation formulas seen in class for binary trees to kary trees.
Depth, height, external nodes, leaves, preorder
numbers, postorder numbers.
Relationship between number of leaves and number of internal nodes with two children in a binary tree.
Counting binary trees (Catalan's formulano proof).
Representing and storing trees: binary trees require about 2n bits.
Preorder, postorder, inorder and level order listings and traversals.
Recursive and nonrecursive traversals.
Stackless traversal if parent pointers are available.
Expression trees, infix, postfix (reverse Polish), and prefix (Polish) representation.
Exercises: Write linear time algorithms to go between any of the linear representations of binary trees, and a binary tree.
Scribed scribbles by Henri Mertens.

Lecture 12 (Feb 14) 
Introduction to the ADT Dictionary.
Binary search trees (CLR 12).
Standard operations on binary search trees (CLR 12.2, CLR 12.3), all
taking time O(h), where h is the height.
Generic tree sort.
Redblack trees (CLR 13). See also
here.
Redblack trees as 234 trees.

Lecture 13 (Feb 19) 
Insert operation on redblack trees.
Standard deletion is not covered in class.
Lazy delete.
Split and join in redblack trees.
Application to list implementations (concatenate
and sublist in O(log n) time).
Exercise: Convince yourself that the split
operation can be implemented in O(log n) time.
Scribed notes on redblack trees are available.
Augmented data structures (CLR 14).
Examples:
 (1) Data that participate in several data structures.
 (2) Combining search trees and ordered linked lists.

Lecture 14 (Feb 21) 
Augmented data structures (CLR 14).
Examples:
 (3) Order statistics trees. Operations rank and selection. CLR 14.1.
 (4) Interval trees. VLSI chip layout application. Sweepline paradigm. CLR 14.3.
 (5) kdtrees. Range search, partial match search. Quadtrees.
 (6) Binary space partition trees.

Lecture 15 (Feb 26) 
Random binary search trees (CLR 12.4). Cartesian trees.
Treaps.
Analysis of the expected time of the main operations.
Quicksort.
Lecture notes in PDF format
courtesy of students
Kaylee Kutschera, Pavel Kondratyev and Ralph Sarkis.

Lecture 16 (Feb 28) 
Priority queues (as abstract data types). CLR 6.
Uses, such as in discrete event simulation and operating systems.
Binary heaps (CLR 6).
Tournament trees. Tournament sort.

Lecture 18 (Mar 14) 
Introduction to compression and coding.
Fixed and variable width codes. Prefix codes.
Most of this lecture is covered by CLR 16.3.
Huffman trees. Huffman code.
Huffman tree.
Definition of a greedy algorithm.
Data structures for Huffman coding.
Merging sorted lists by the greedy method.

Lecture 19 (Mar 19) 
Entropy of an input source.
Definition of entropy and Shannon's result on best possible compression ratios.
Proof of Shannon's theorem. The ShannonFano code.
Kraft's inequality.
Lecture notes in PDF format
courtesy of 2017 students
Adel Magra, Emma Gouné and Irène Woo.
LempelZiv compression.
Data structures for LempelZiv compression.
Digital search tree.

Lecture 20 (Mar 21) 
Data structures for strings and compression.
Tries, PATRICIA trees, digital search trees.
Suffix tries, suffix trees, suffix arrays.
The RabinKarp pattern matching algorithm and introductory notions on pattern matching.

Lecture 21 (Mar 26) 
Introduction to graphs: notation, definitions,
adjacency matrix, adjacency lists.
Graph traversals as the fundamental
procedures for most graph algorithms:
depth first search (CLR 22.1, CLR 22.3).
DFS forest and DFS properties.

Lecture 22 (Mar 28) 
Classification of edges.
Detecting cycles.
Euler tour.
Breadth first search (CLR 22.2).
BFS tree.
Detecting bipartite graphs.

Lecture 23 (Apr 2) 
Shortest path problem. CLR 24. Dijkstra's algorithm.
Shortest path properties.
Minimal spanning tree. CLR 23. Main properties.

Lecture 24 (Apr 4) 
Minimal spanning trees continued. CLR 23.
Greedy approach for the MST: the PrimDijkstra algorithm.
A twoapproximation for the
traveling salesman problem (CLR 35.2).
Kruskal's algorithm.
Application in clustering.
The allpairs shortest path algorithm of
Floyd and Warshall. CLR 25.1, 25.2.

Lecture 25 (Apr 9) 
Flow networks (CLR 26.1).
The FordFulkerson method (CLR 26.2),
including the EdmondsKarp algorithm.

Lecture 26 (Apr 11) 
Directed acyclic graphs. Topological sorting. CLR 22.4.
Activity (PERT) networks.
Dags continued: NIM games.
Strongly connected components in directed graphs. CLR 22.5.
