Syllabus for CS 512, Algorithm Design
Fall 1999
The course is divided into seven two-week sections:
- Algorithms
- Data structures
- Asymptotic Notation
- Complexity
- Algorithm Design
- Algorithm and data correctness
- Correctness, continued
I will try hard not to change the schedule during the semester, but I make no
promises.
- Algorithms - Thursday, 2 September to Tuesday, 14 September.
-
- Readings
- Sections 7.1 through 7.8, Chapter 8.
- Class notes
- Introduction, 2 September.
Basic Graph Algorithms, 7-9 September.
Geometric Algorithms, 9-14 September.
- Homework
- Homework for algorithms, answered, due 14 September,
and the grade distribution.
- Test
- Test on algorithms, answered, Thursday, 16 September,
and the grade distribution.
- Data structures - Thursday, 16 September to Tuesday, 28 September.
-
- Readings
- Chapter 4 (Section 4.5 optional) and Sections 6.1 to 6.5 and 6.10.
- Class notes
- Data Structures, 21 September.
Searching, Sorting, Statistics, 25 September.
- Homework
- Homework for data structures and sequences, answered, due
28 September, and the grade distribution.
- Test
- Test on data structures, answered, Thursday, 30
September, and and the grade distribution.
- Asymptotic Notation - Thursday, 30 September to Tuesday, 12 October.
-
- Readings
- Chapter 3 and Section 6.4.6.
- Class notes
- Asymptotic notation, 5 October.
Analyzing algorithms, 7 October.
- Homework
- Homework for asymptotic notation, answered, due
12 October, and the grade distribution.
- Test
- Test on asymptotic notation, answered, Thursday, 14
October, and the grade distribution.
- Complexity - Thursday, 14 October to Tuesday, 26 October.
-
- Readings
- Chapter 11.
- Class notes
- Tractable and intractable problems, 19 October.
Heuristic Algorithms, 21 October.
- Homework
- Homework for complexity, answered, due 26 October,
and the grade distribution.
- Test
- Test on complexity, answered, Thursday, 28 October,
and the grade distribution.
- Algorithm Design - Thursday, 28 October to Tuesday, 9 November.
-
- Readings
- Chapters 2 and 5.
- Class notes
- Mathematical induction, 19 October.
Inductive algorithm design, 2 November.
- Homework
- Homework for algorithm design, answered, due 9 November, and the grade distribution.
- Test
- Test on inductive algorithm design, answered, Thursday,
11 November, and the grade distribution.
- Algorithm and data correctness - Thursday, 11 November to Tuesday, 23 November.
-
- Readings
- Chapter 10 (Section 10.4 optional).
- Class notes
- Reductions, 16 November
Algorithms and states, 23 November.
- Homework
- Homework for correctness, answered, due 30 November, and the grade distribution.
- Test
- Test on correctness, answered, Thursday, 2 December, and the grade distribution.
- Correctness, continued - Thursday, 30 November to Tuesday, 9 December.
-
- Readings
- Class notes.
- Class notes
- Statements, 30 November.
- Homework
- Optional homework for correctness, due 7 December.
- Test
- Optional test on correctness, Thursday, 9 December.
- emph(Open Lecture) on cryptography - Thursday, 16
December, 5:30 p.m. to 7:30 p.m; lecture notes.
This page last modified on 16 December 1999.