| Lecture 1 (Jan 4) |
General introduction. Definition of an algorithm.
Examples of simple computer models:
Turing model, RAM model, pointer based machines,
comparison model.
Uniformly bounded time, bit model of computation
(or: logarithmic model).
Landau symbols: O, Omega, Theta, small o, small omega.
Polynomial versus exponential time classes.
Chapter 1 in CLR, web pages from 1997.
The Fibonacci example: introduce recursion, dynamic programming,
and fast exponentiation (the Russian peasant method).
Check here for some notes by David Eppstein.
|
| Lecture 2 (Jan 6) |
We covered all of chapter 2
and part of chapter 3 of CLR.
Some discussion of complexity classes.
Introduction to recurrences.
The divide-and-conquer solution to Problem 4.7 (VLSI
chip testing) of Cormen, Leiserson and Rivest.
|
| Lecture 3 (Jan 11) |
Solutions of simple recurrences.
Binary search.
Mergesort.
Recursive solution for convex hulls in the plane.
Divide-and-conquer (Karatsuba) multiplication.
Strassen matrix multiplication.
Statement of the master theorem.
|
| Lecture 4 (Jan 13) |
Recursion tree.
The master theorem explained.
Solving recurrences by induction: binary search, mergesort.
Selection.
We covered the linear worst-case algorithm in its entirety.
Assignment 1 handed out: due January 25, 8:30am.
|
| Lecture 5 (Jan 18) |
Lower bounds via 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 Mastermind.
Lower bounds via witnesses and adversaries:
finding the maximum,
finding maximum and minimum.
|
| Lecture 6 (Jan 20) |
Brief remarks about binary search.
Introductory remarks about ADTs (abstract data types).
Lists.
Chapter 11 of CLR: primitive data structures
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.
Merging sorted sets by using finger lists (take notes).
|
| Lecture 7 (Jan 25) |
Assignment 1 due.
Assignment 2 handed out: due February 3, 8:30am.
Examples of list ADTs: polynomial ADT, large integer ADT,
free space list ADT,
triangulations.
Introduction to trees:
free trees, ordered trees, position trees, binary trees, complete k-ary trees.
Oldest child, next sibling pointers.
Complete trees: storage, height.
Counting binary trees (Catalan's formula--no proof).
1997 class notes.
Sections 11.3, 11.4, and 5.3 of CLR.
Representing and storing trees.
|
| Lecture 8 (Jan 27) |
Preorder, postorder, inorder, level order.
Traversals, and discussion.
Expression trees, postfix, infix and prefix expressions.
Relationship between number of leaves and number of internal nodes with two children in a binary tree.
Expression tree evaluation via recursion.
Postfix expression evaluation with a stack (non-recursively).
Introduction to the ADT Dictionary.
Definition of a binary search tree.
|
| Lecture 9 (Feb 1) |
Binary search trees: chapter 13 of CLR.
Introduction to balanced search trees
(see here).
Red-black trees (chapter 14). See also
here.
|
| Lecture 10 (Feb 3) |
Assignment 2 due.
Definition of AVL tree, 2-3 tree.
Check also the
1997 class notes for this.
View of a binary search tree as a 2-4 tree.
Treaps (or Cartesian search trees).
Definition of random binary search tree as a special kind of treap.
Treaps: handout.
Multidimensional search trees: quadtrees, k-d trees.
BSP (binary space partition) trees. Painter's algorithm.
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 11 (Feb 8) |
Hand out assignment 3, due Friday, February 18, 12 noon.
Augmented data structures.
This is nicely described in CLR (chapter 15),
and to some extent in
topic 20 of the 1997 class notes.
Examples:
- (1) Combining search trees and ordered linked lists.
- (2) Order statistics trees. Operations rank and selection.
- (3) Interval trees. VLSI chip layout application. Sweepline paradigm.
|
| Lecture 12 (Feb 8) |
Fixed and variable width codes. Prefix codes.
Definition of a "trie".
Coding, data compression, Huffman trees.
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.
Definition of the ADT "priority queue".
Hu-Tucker algorithm for constructing the Huffman tree.
Definition of a greedy algorithm.
|
| Lecture 13 (Feb 10) |
Merging sorted lists by the greedy method.
Lempel-Ziv compression.
1997 class notes on Lempel-Ziv coding.
Digital search trees.
Tries and related search trees adapted for strings.
Suffix trees.
See here.
|
| Midterm (Feb 15) |
As practice, attempt questions 1, 2, 3, 4, 6 and 7
here.
Don't immediately look at the
solutions.
Note: closed book, 90 minutes, no calculators,
cell phones or other electronic devices.
|
| Lecture 14 (Feb 17) |
Priority queues.
Uses, such as in
discrete
event simulation.
Binary heaps (chapter 7 of CLR).
Heapsort. Additional binary heap operations.
k-ary heaps (determining best k).
Pointer-based implementaion of binary heaps.
|
| Lecture 15 (Mar 1) |
Assignment 4 due.
Disjoint set structures: sections 22.1, 22.2, 22.3 of CLR.
|
| Lecture 16 (Mar 1) |
Amortization (chapter 18 of CLR). Potential functions.
Simple examples: stack with multipop,
dynamic tables,
lazy delete in red-black trees,
binary addition,
weight-balanced search trees.
|
| Lecture 17 (Mar 3) |
Hand out assignment 5, due March 15, 8:30am.
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 18 (Mar 15) |
Collect assignment 5.
Hand out the last assignment (6), which is due March 22, 8:30am.
Classification of edges.
Detecting cycles.
Euler tour.
|
| Lecture 19 (Mar 17) |
Breadth first search (section 23.3 of CLR).
Shortest path properties.
Detecting bipartite graphs.
Shortest path problem. Dijkstra's algorithm.
See here.
|
| Lecture 20 (Mar 22) |
Collect assignment 6.
Minimal spanning trees.
See also here.
We covered the Prim-Dijkstra algorithm, but not Kruskal's.
A two-approximation for the
traveling salesman problem (section 37.2).
Applications in clustering.
Strongly connected components in directed graphs.
|
| Lecture 21 (Mar 24) |
Directed acyclic graphs. Topological sorting.
NIM games. PERT networks.
See here.
|
| Lecture 22 (Mar 28) |
Dynamic programming.
Computing binomial coefficients and partition numbers.
Traveling salesman problem.
Optimal binary search trees.
|
| Lecture 23 (Mar 30) |
Dynamic programming: more examples.
Longest common subsequence problem.
Knapsack problem.
Job scheduling.
Matrix multiplication: parenthesization.
|
| Lecture 24 (Apr 4) |
All-pairs shortest path problem.
Transitive closure of a graph.
Floyd-Warshall algorithm.
Solutions via dynamic programming.
|
| Lecture 25 (Apr 6) |
Fast Fourier Transform.
Multiplying polynomials in time O(n log n).
|
| Final (Apr 12: 2-5pm) |
Location: Rutherford Physics 114.
It is a 3-hour closed book examination.
No calculators, cell phones, Blackberries,
spy cameras, or other electronic devices are allowed.
Paper airplanes, palm writing, whispering,
and sign language are not allowed.
Permanent tattooages of the material will be
permitted but must be checked by the TA beforehand.
|