| 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 divide-and-conquer 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.
Divide-and-conquer (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 divide-and-conquer (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 divide-and-conquer (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).
Ham-sandwich and pancake theorems and halfspace counting.
Linear time selection: finding the k-th smallest
by the algorithm of Blum, Floyd, Pratt, Rivest and Tarjan.
We looked at the median-of-3 version of this algorithm
and showed, by using recursion trees, that its complexity is
big theta of n log n.
Scribed notes on divide-and-conquer (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 k-ary tree with L leaves, L <= 2^h (i.e., h >= log_k L).
Proof of lower bound for worst-case and average-case
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 in-class 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 k-ary trees.
Height of complete k-ary 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 formula--no 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 k-ary 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.
Red-black trees (chapter 14). See also
here.
Red-black trees as 2-3-4 trees.
Exercise: Show by induction on the rank r of the root,
that for a red-black 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 red-black trees.
Standard deletion is not covered in class.
Lazy delete.
Split and join in red-black 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 red-black 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 red-black 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.
Hu-Tucker 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 Shannon-Fano code.
Kraft's inequality recalled.
Lecture notes in PDF format
courtesy of 2017 students
Adel Magra, Emma Gouné and Irène Woo.
Lempel-Ziv compression.
1997 class notes on Lempel-Ziv coding.
Data structures for Lempel-Ziv 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 Knuth-Morris-Pratt 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 $2n-1$. (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.
Karp-Rabin 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 Prim-Dijkstra algorithm.
Application in hierarchical clustering.
|
| Lecture 24 (Mar 29) |
Minimal spanning trees continued.
Kruskal's algorithm.
See here.
A two-approximation for the
traveling salesman problem (section 37.2 of Cormen).
The all-pairs 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.
|