| Lecture 1 (Jan 5) |
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 10) |
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).
Divide-and-conquer (Karatsuba) multiplication.
Recurrence for binary search.
Exercise: For binary search using
a binary oracle, show that T(n) is not more than 2 + ceiling(log_2 n).
|
| Lecture 3 (Jan 12) |
Mergesort, convex hulls.
The master theorem (statement only).
Recursion tree to explain the master theorem.
Exercise: Analyze T(n) = T(n/3) + T(2n/3) + n using the recursion tree.
Strassen matrix multiplication.
Euclid's algorithm.
Exercise: Bit complexity of gcd(n,m) is O(log n . log m).
Assignment 1 handed out. Due January 24, 2017, 8:30am.
|
| Lecture 4 (Jan 17) |
Ham-sandwich and pancake theorems and halfspace counting.
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.
Exercise: Look at the median-of-3 version of this algorithm
and show, by using recursion trees, that its complexity is
big theta of n log n.
|
| Lecture 5 (Jan 19) |
Linear expected time selection by Hoare's algorithm "FIND".
Ulam's problem.
Dynamic programming.
Computing binomial coefficients and partition numbers.
Traveling salesman problem.
|
| Lecture 6 (Jan 24) |
Dynamic programming, continued.
Longest common subsequence problem. Exercise: from the nxm matrix of lengths of longest common subsequences, determine in time O(n+m) a longest matching.
Knapsack problem.
Assignment problem.
Matrix chains.
Assignment 2 handed out. Due February 2, 2017, 8:30am. Question 2 of the assignment has been canceled.
|
| Lecture 7 (Jan 26) |
Remarks about an algorithm needed in assignment 1.
Oracles.
Lower bounds via decision trees.
Kraft's inequality.
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 (Jan 31) |
Merging two sorted arrays using finger lists.
Lower bounds for board games.
Lower bounds via witnesses: finding the maximum.
Lower bounds via adversaries.
Guessing a password.
Finding maximum and minimum.
Finding the median.
|
| Lecture 9 (Feb 2) |
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.
Bijection between ordered trees (forests) and binary trees
via oldest child and next sibling pointers.
Counting binary trees (Catalan's formula--no proof).
Assignment 3 handed out. Due February 14, 2017, 8:30am.
|
| Lecture 10 (Feb 7) |
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, height.
Practice exercise: Reconstruct an ordered tree in linear time from its preorder and postorder listings. Reconstruct the shape of a binary tree in linear time from its 2n-bit preorder listing.
|
| Lecture 11 (Feb 9) |
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.
Introduction to balanced search trees
(see here).
Red-black trees (chapter 14). See also
here.
Deletion is not covered in class.
|
| Lecture 12 (Feb 14) |
Assignment 3 due.
Insert operation on red-black trees.
Definition of HB-k, AVL and 2-3 trees.
Inductive proof for height of AVL tree.
Red-black trees as 2-3-4 trees.
Check also the 1997 class notes for this.
Split and join in red-black trees.
Application to list implementations (concatenate
and sublist in O(log n) time).
|
| Lecture 13 (Feb 16) |
Midterm.
|
| Lecture 14 (Feb 21) |
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.
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) 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.
|
| Lecture 15 (Feb 23) |
Assignment 4 handed out. Due March 9, 2017.
Random binary search trees. Cartesian trees.
Treaps.
Analysis of the expected time of the main operations.
Quicksort.
Lecture notes in PDF format
courtesy of fellow students
Kaylee Kutschera, Pavel Kondratyev and Ralph Sarkis.
|
| Lecture 16 (Mar 7) |
Priority queues (as abstract data types).
Uses, such as in
discrete event simulation
and operating systems.
Binary heaps (chapter 7 of CLR): superficial coverage.
k-ary heaps (determining best k).
Pointer-based implementation of binary heaps.
Heapsort. Additional binary heap operations.
Huffman tree.
Hu-Tucker algorithm for finding the Huffman tree.
Definition of a greedy algorithm.
|
| Lecture 17 (Mar 9) |
Assignment 5 handed out. Due March 17, 2017.
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
here
and
here.
Definition of entropy and Shannon's result on best possible compression ratios.
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 fellow students
Adel Magra, Emma Gouné and Irène Woo.
|
| Lecture 18 (Mar 14) |
Data structures for Huffman coding.
Merging sorted lists by the greedy method.
Optimal way of generating random integers.
Lempel-Ziv compression.
1997 class notes on Lempel-Ziv coding.
Data structures for Huffman coding
and Lempel-Ziv compression.
Digital search tree.
|
| Lecture 19 (Mar 16) |
Data structures for strings and for compression.
Tries, PATRICIA trees, digital search trees.
Suffix tries, suffix trees, suffix arrays.
String searching in a large file.
See here.
|
| Lecture 20 (Mar 17) |
Assignment 6 handed out. Due March 29, 2017, 8:30am.
Hashing: Uses, examples.
Simple hash functions.
Direct hashing.
Hashing with chaining.
Discussion of rehashing.
Open addressing.
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.
|
| Lecture 21 (Mar 21) |
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 24) |
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.
A two-approximation for the
traveling salesman problem (section 37.2 of Cormen).
|
| Lecture 24 (Mar 28) |
Assignment 6 due by Wednesday March 29 at 8:30am, under my door.
Minimal spanning trees continued.
Kruskal's algorithm.
Application in clustering.
See here.
The all-pairs shortest path algorithm of
Floyd and Warshall.
Transitive closure of a graph.
|
| Lecture 25 (Mar 30) |
Directed acyclic graphs. Topological sorting.
Activity (PERT) networks.
See here.
Dags continued: NIM games.
Strongly connected components in directed graphs.
Introduction to matching.
The stable matching algorithm of Gale and Shapley.
|
| Lecture 26 (Apr 11) |
Fast Fourier Transform.
Multiplying polynomials in time O(n log n).
This is in chapter 30 of Cormen et al.
|