The course is divided into seven two-week sections:

- Graphs
- Trees
- Heaps and Hash Tables
- Asymptotic Estimates and Computational Complexity
- Algorithm Design - Exhaustive Search and Approximation Algorithms
- Algorithm Design - Greed and Dynamic Programming
- Algorithm Design - Divide and Conquer and Recursion

I will try hard not to change the schedule during the semester, but I make no promises.

**Graphs**- 19 January to 2 February.-
**Readings**- Sections 23.1 through 23.4, Chapter 24, and Sections 25.1 through 25.3.
**Class notes**- Introduction

Graphs and graph algorithms

Graph traversals

Minimum spanning trees

Shortest path algorithms. **Homework**- Homework for graphs, due 2 February, answered, and the grade distribution.
**Test**- Test on graphs, 7 February, answered and the grade distribution.

**Trees**- 2 February to 16 February.-
**Readings**- Sections 13.1 through 13.3, Chapters 14 and 19.
**Class notes**- Binary search trees

Red-black trees

B-trees. **Homework**- Homework for trees, due 16 February, answered, and the grade distribution.
**Test**- Test on trees, 21 February, answered and the grade distribution.

**Heaps and Hash Tables**- 16 February to 1 March.-
**Readings**- Sections 7.1 through 7.3, Chapters 20 and 12.
**Class notes**- Binary heaps

Binomial heaps

Hashing. **Homework**- Homework for heaps and hashing, due 1 March, answered, and the grade distribution.
**Test**- Test on heaps and hashing, 13 March, answered and the grade distribution.

**Asymptotic Estimates and Computational Complexity**- 1 March to 22 March.-
**Readings**- Section 1.2, Chapter 2 and Sections 36.1 and 36.2, Section 36.3 up to but not including circuit satisfiability, Section 36.4 up to but not including formula satisfiability and after.
**Class notes**- Asymptotic estimates

Algorithm analysis

Tractable and intractable problems. **Homework**- Homework for asymptotics and complexity, due 22 March, answered, and the grade distribution.
**Test**- Test on asymptotics and complexity, 27 March, answered and the grade distribution.

**Algorithm Design - Exhaustive Search and Approximation Algorithms**- 22 March to 3 April.-
**Readings**- Chapter 37.
**Class notes**- Exhaustive search and heuristics

Bounded approximation algorithms

The traveling salesman problem

Subset sums. **Homework**- Homework for exhaustive search and approximation algorithms, due 3 April.
**Test**- Test on exhaustive search and approximation algorithms, 10 April.

**Algorithm Design - Greed and Dynamic Programming**- 5 April to 19 April.-
**Readings**- Chapter 16 and Sections 17.1 through 17.3.
**Class notes**- Dynamic programming

Some dynamic programming problems

Greed

Some problems solvable with greed. **Homework**- Homework for greed and dynamic programming, due 19 April, answered, and the grade distribution.
**Test**- Test on greed and dynamic programming, 24 April, answered and the grade distribution.

**Algorithm Design - Divide and Conquer and Recursion**- 19 April to 1 May.-
**Readings**- Section 1.3.
**Class notes**- Divide and conquer

Recursion. **Homework**- Homework for Divide and Conquer and Recursion, due 1 May, answered, and the grade distribution.
**Test**- Test on divide and conquer and recursion, 1 May, answered and the grade distribution.

**Open Lecture on Cryptography**- 3 May, 7:45 p.m. to 9:45, in Bey Hall 134, lecture notes.

This page last modified on 2 May 2000.