|Lecture 1 (Jan 8)
||General introduction. Definition of an algorithm.
Examples of simple computer models:
Turing model, RAM model, pointer based machines, oracles,
Uniformly bounded time, bit model of computation
(or: logarithmic model).
Definition and examples of an oracle.
Chapter 1 in CLR, web pages from 1997.
Landau symbols: O, Omega, Theta, small o, small omega.
Examples of many complexity classes (linear, quadratic, polynomial, exponential).
The Fibonacci example: introduce recursion, iteration,
and fast exponentiation.
Check here for some notes by David Eppstein.
|Lecture 2 (Jan 13)
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).
Divide-and-conquer (Karatsuba) multiplication.
Solution of the recurrence for binary search.
|Lecture 3 (Jan 15)
Recurrences for binary search, mergesort, convex hulls.
The master theorem (statement only).
Recursion tree to explain the master theorem.
Strassen matrix multiplication.
Assignment 1 handed out. Due January 27, 2016, 10am.
|Lecture 4 (Jan 20)
The induction method: Simple examples: Binary search with
two different oracles. Mergesort.
Linear time selection: finding the k-th smallest
by the algorithm of Blum, Floyd, Pratt, Rivest and Tarjan.
Linear expected time selection by Hoare's algorithm "FIND".
|Lecture 5 (Jan 22)
Computing binomial coefficients and partition numbers.
Traveling salesman problem.
|Lecture 6 (Jan 27)
Dynamic programming, continued.
Longest common subsequence problem.
Optimal binary search tree.
Assignment 2 handed out. Due February 5 2016, 10am.
|Lecture 7 (Jan 29)
Lower bounds via decision trees.
Proofs of lower bounds for worst-case
time 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, searching, and board games.
Merging two sorted arrays using finger lists.
|Lecture 8 (Feb 3)
Lower bounds via witnesses: finding the maximum.
Lower bounds via adversaries.
Finding maximum and minimum.
Introductory remarks about ADTs (abstract data types).
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).
|Lecture 9 (Feb 5)
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.
Bijection between ordered trees (forests) and binary trees
via oldest child and next sibling pointers.
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.
Assignment 3 handed out. Due February 17, 2016.
|Lecture 10 (Feb 10)
Preorder, postorder, inorder and level order listings and traversals.
Recursive and nonrecursive traversals.
Stackless traversal if parent pointers are available.
Complete trees: implicit storage, height.
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.
|Lecture 11 (Feb 12)
Introduction to balanced search trees
Red-black trees (chapter 14). See also
Deletion is not covered in class.
Definition of AVL and 2-3 trees.
Red-black trees as 2-3-4 trees.
Check also the 1997 class notes for this.
|Lecture 12 (Feb 17)
Assignment 3 due.
Split and join in red-black trees.
Application to list implementations (concatenate
and sublist in O(log n) time).
Definition of k-d trees, range search, partial match search.
The multidimensional search trees are
not in CLR, but there
are a few indicators near the end of
topic 10 of the 1997 class notes.
Definition of BSP (binary space partition) trees.
Ham-sandwich theorem and halfspace counting.
|Lecture 13 (Feb 19)
|Lecture 14 (Feb 24)
Brief discussion of the midterm.
Augmented data structures.
This is nicely described in CLR (chapter 15),
and to some extent in
topic 20 of the old class notes.
- (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.
|Lecture 15 (Feb 26)
Assignment 4 handed out. Due March 11, 2016.
Random binary search trees. Cartesian trees.
Analysis of the expected time of the main operations.
Priority queues (as abstract data types).
Uses, such as in
discrete event simulation
and operating systems.
|Lecture 16 (Mar 9)
Binary heaps (chapter 7 of CLR): superficial coverage.
k-ary heaps (determining best k).
Heapsort. Additional binary heap operations.
Introduction to compression and coding.
Fixed and variable width codes. Prefix codes.
Huffman trees. Huffman code.
Most of this lecture is covered by section 17.3 of CLR.
For a few additional applications, check
Definition of entropy and Shannon's result on best possible compression ratios.
Hu-Tucker algorithm for constructing the Huffman tree.
Definition of a greedy algorithm.
Merging sorted lists by the greedy method.
Optimal way of generating random integers.
|Lecture 17 (Mar 11)
Assignment 5 handed out. Due March 21, 2016.
Entropy of an input source.
Proof of Shannon's theorem.
1997 class notes on Lempel-Ziv coding.
Data structures for strings and for compression.
Digital search tree.
|Lecture 18 (Mar 16)
Tries, PATRICIA trees, digital search trees.
Suffix tries, suffix trees, suffix arrays.
String searching in a large file.
|Lecture 19 (Mar 18)
The Rabin-Karp method.
The Knuth-Morris-Pratt (KMP) method.
|Lecture 20 (Mar 21)
Assignment 6 handed out. Due March 30, 2016, 10am.
Hashing with chaining. Simple hash functions.
Hashing: Uses, examples.
Perfect hashing with two layers of hash functions.
Remarks on load balancing and the power of two.
Discussion of rehashing.
The material in this section roughly corresponds to chapter 11
of Cormen et al.
|Lecture 21 (Mar 23)
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 24)
Classification of edges.
Breadth first search (section 23.3 of CLR).
|Lecture 23 (Mar 30)
Detecting bipartite graphs.
Shortest path problem. Dijkstra's algorithm.
Shortest path properties.
Minimal spanning tree. Main properties.
Greedy approaches for the MST: Prim-Dijkstra,
Application in clustering.
|Lecture 24 (Apr 11)
Minimal spanning trees continued.
A two-approximation for the
traveling salesman problem (section 37.2).
The all-pairs shortest path algorithm of
Floyd and Warshall.
Transitive closure of a graph.
|Lecture 25 (Apr 13)
Directed acyclic graphs. Topological sorting.
Activity (PERT) networks.
Dags continued: NIM games.
Strongly connected components in directed graphs.
Introduction to matching.
The stable matching algorithm of Gale and Shapley.
|Lecture 26 (Apr 15)
Fast Fourier Transform.
Multiplying polynomials in time O(n log n).