Syllabus for CS 512, Algorithm Design

Spring 2000


The course is divided into seven two-week sections:

  1. Graphs

  2. Trees

  3. Heaps and Hash Tables

  4. Asymptotic Estimates and Computational Complexity

  5. Algorithm Design - Exhaustive Search and Approximation Algorithms

  6. Algorithm Design - Greed and Dynamic Programming

  7. 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.