Lecture 1 (Jan 9) 
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, web pages from 1997.
The Fibonacci example: introduce recursion, iteration,
and fast exponentiation.
Fast exponentiation.
Check here for some notes by David Eppstein.

Lecture 2 (Jan 11) 
Landau symbols: O, Omega, Theta, small o, small omega.
Examples of many complexity classes (linear, quadratic, polynomial, exponential).
We covered all of chapter 2 and part of chapter 3 of CLR.
Introduction to recurrences.
The divideandconquer solution to Problem 4.7 (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 Landau symbols.
Scribed notes on divideandconquer (part I).

Lecture 3 (Jan 16) 
Illustrate induction on the chip testing recurrence.
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).
The master theorem (statement only).
Recursion tree to explain the master theorem.
Strassen matrix multiplication.
Assignment 1 handed out. Due January 25, 2018, 8:30am.
Scribed notes on divideandconquer (part II).

Lecture 4 (Jan 18) 
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.
Linear time selection: finding the kth smallest
by the algorithm of Blum, Floyd, Pratt, Rivest and Tarjan.
We looked at the medianof3 version of this algorithm
and showed, by using recursion trees, that its complexity is
big theta of n log n.
Scribed notes on divideandconquer (part III).

Lecture 5 (Jan 23) 
The induction method illustrated on mergesort.
Linear expected time selection by Hoare's algorithm "FIND".
Dynamic programming.
Computing binomial coefficients and partition numbers.
Traveling salesman problem.

Lecture 6 (Jan 25) 
Dynamic programming, continued.
Knapsack problem.
Longest common subsequence problem. Exercise: from the nxm matrix of lengths of longest common subsequences, determine in time O(n+m) a longest matching.
Optimal binary search tree.
Scribed notes on dynamic programming (part II).
Assignment 2 handed out. Due February 6, 2018, 8:30am.

Lecture 7 (Jan 30) 
Assignment problem.
Job scheduling problem.
Oracles.
Lower bounds via decision trees.
Kraft's inequality.
Exercise: Prove Kraft's inequality by induction on the number of levels.
Exercise: Prove by induction on the height h that for any kary tree with L leaves, L <= 2^h (i.e., h >= log_k L).
Proof of lower bound for worstcase and averagecase
complexity based on decision trees.
Part of the material is in section 9.1,
and part is covered in
the 1997 lecture notes.
Examples include sorting and searching.

Lecture 8 (Feb 1) 
Lower bounds for board games.
Merging two sorted arrays using finger lists.
Lower bounds via witnesses: finding the maximum.
Lower bounds via adversaries.
Guessing a password.
Sorting via adversaries.
Finding maximum and minimum.
Finding the median.
Refer to the inclass handout on lower bounds.

Lecture 9 (Feb 6) 
Introductory remarks about ADTs (abstract data types).
Lists.
Chapter 11 of CLR: primitive ADTs
such as stacks, queues, deques, and lists.
We deviate only slightly from this chapter.
For another account, see the
1997 class notes,
or, for the notation for list operations, chapter 1 of
Data Structures and Network Algorithms
(R.E. Tarjan, SIAM, Philadelphia, 1983).
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:
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.
Assignment 3 handed out. Due February 15, 2018, 8:30am.

Lecture 10 (Feb 8) 
Continuing with 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.
1997 class notes.
Sections 11.3, 11.4, and 5.3 of CLR.
Preorder, postorder, inorder and level order listings and traversals.
Recursive and nonrecursive traversals.
Stackless traversal if parent pointers are available.
Complete trees: implicit storage.
Exercise: Generalize the navigation formulas seen in class for binary trees to kary trees.
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.

Lecture 11 (Feb 13) 
Introduction to the ADT Dictionary.
Definition of a binary search tree.
Binary search trees: chapter 13 of CLR.
Standard operations on binary search trees, all
taking time O(h), where h is the height.
Generic tree sort.
Redblack trees (chapter 14). See also
here.
Redblack trees as 234 trees.
Exercise: Show by induction on the rank r of the root,
that for a redblack tree with $n$ nodes (and thus $n+1$ external nodes), 2^r <= n+1 <= 4^r.

Lecture 12 (Feb 20) 
Assignment 4 handed out. Due March 1, 2018, 8:30am.
Hand out course notes on lower bounds.
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 will soon be available.

Lecture 14 (Feb 22) 
Augmented data structures.
This is nicely described in CLR (chapter 15),
and to some extent in
topic 20 of the old class notes.
Examples:
 (1) Data that participate in several data structures.
 (2) Combining search trees and ordered linked lists.
 (3) Order statistics trees. Operations rank and selection.
 (4) Interval trees. VLSI chip layout application. Sweepline paradigm.
 (5) Level linking in redblack trees. Exercise: Explain how to maintain the level links during a rotation operation.

Lecture 15 (Feb 27) 
Random binary search trees. 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 (Mar 1) 
Priority queues (as abstract data types).
Uses, such as in
discrete event simulation
and operating systems.
Binary heaps (chapter 7 of CLR): superficial coverage.
Tournament trees (handout). Tournament sort.
Assignment 5 handed out. Due March 15, 2018.

Lecture 17 (Mar 13) 
Introduction to compression and coding.
Fixed and variable width codes. Prefix codes.
Most of this lecture is covered by section 17.3 of CLR.
For a few additional applications, check
here
and
here.
Definition of entropy and Shannon's result on best possible compression ratios.
Huffman trees. Huffman code.
Huffman tree.
HuTucker algorithm for finding the Huffman tree.
Definition of a greedy algorithm.
Data structures for Huffman coding.
Merging sorted lists by the greedy method.

Lecture 18 (Mar 15) 
Entropy of an input source.
Proof of Shannon's theorem. The ShannonFano code.
Kraft's inequality recalled.
Lecture notes in PDF format
courtesy of 2017 students
Adel Magra, Emma Gouné and Irène Woo.
LempelZiv compression.
1997 class notes on LempelZiv coding.
Data structures for LempelZiv compression.
Digital search tree.
Assignment 6 handed out. Due March 23, 2018, 8:30am.

Lecture 19 (Mar 16) 
Data structures for strings and compression.
Tries, PATRICIA trees, digital search trees.
Suffix tries, suffix trees, suffix arrays.
String searching in a large file via the KnuthMorrisPratt algorithm.
See here.
Exercises: (1) Show that for a $k$ary PATRICIA tree on $n$ strings, and for a suffix tree on a text of $n$ symbols, the number of the nodes in the tree is at most $2n1$. (2) Give an algorithm for insertion into a trie. (3) Add one line to the KMP algorithm to make it return all pattern matches, not just one.

Lecture 20 (Mar 20) 
Simple hash functions.
Direct hashing.
Hashing with chaining.
Open addressing.
KarpRabin pattern matching.
The material in this section roughly corresponds to chapter 12
of Cormen et al.
Lecture notes in PDF format
courtesy of fellow students
Aram Pooladian and Alex Iannantuono.
Exercises: Write "insert" for open addressing.
Write "delete" for the direct chaining example that
avoids table initialization.

Lecture 21 (Mar 22) 
Hashing: Uses, examples. Radix and bucket sort.
Dynamic hashing.
Introduction to graphs: notation, definitions,
adjacency matrix, adjacency lists.
Graph traversals as the fundamental
procedures for most graph algorithms:
depth first search (sections 23.1, 23.2 of CLR).
DFS forest and DFS properties.

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

Lecture 23 (Mar 27) 
Assignment 6 due by 8:30am.
Shortest path problem. Dijkstra's algorithm.
Shortest path properties.
See here.
Minimal spanning tree. Main properties.
Greedy approach for the MST: the PrimDijkstra algorithm.
Application in hierarchical clustering.

Lecture 24 (Mar 29) 
Minimal spanning trees continued.
Kruskal's algorithm.
See here.
A twoapproximation for the
traveling salesman problem (section 37.2 of Cormen).
The allpairs shortest path algorithm of
Floyd and Warshall.
Transitive closure of a graph.

Lecture 25 (Apr 10) 
Directed acyclic graphs. Topological sorting.
Activity (PERT) networks.
See here.
Dags continued: NIM games.
Strongly connected components in directed graphs.

Lecture 26 (Apr 12) 
Fast Fourier Transform.
Multiplying polynomials in time O(n log n).
This is in chapter 30 of Cormen et al.
