Syllabus for CS 512, Algorithm Design
Spring 2000
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.