Course archived Fall 2005
Dates left on so student can compare with dates of archives
| Archived Date | Lecture | Material | NOTES | ASSIGNMENT | DUE |
| Aug 23 | 1 | Introduction, Web Page, Conventions | homepage and Ch. 1 Important | Read Preface, Ch1: 1.1 to 1.3 | |
| Aug 25 | 2 | Recursion and Induction | Recursion examples and Induction review | Try recursion problems (not turnin), Read Ch1: 1.3 | |
| Aug 30 | 3 | Recursion and Induction problems | Looking at exercises solutions Start performance | Read handout: Analysis Techniques | |
| Sept 1 | 4 | Performance Analysis | T(n), O(n), etc. | Homework 1 | before class 9 |
| Sept 6 | 5 | Performance Analysis | T(n), O(n), recursive algorithms | Read handout: Analysis Techniques again | |
| Sept 8 | 6 | Review of Data Structures | finish performance: timing, Handout | Read Chapter 2! | |
| Sept 13 | 7 | Data Structures | Sets, No Guess recurrance | Read Chapter 3 | |
| Sept 15 | 8 | Divide and conquer | Divide and Conquer | Exercise 2 | |
| Sept 20 | 9 | Divide and conquer | grade homework 1 | Read Chapter 4 Exercise 3 | before class 13 |
| Sept 22 | 10 | Greedy method | Knapsack | ||
| Sept 27 | 11 | Greedy method | Minimum Spanning Trees and SS Shortest Path | Read Chapter 5 | |
| Sept 29 | 12 | Dynamic programming | Dynamic Programming | Exercise 4 | before class 15 |
| Oct 4 | 13 | Dynamic programming | Dynamic Programming | ||
| Oct 6 | 14 | Exercises | Solutions . | ||
| Oct 11 | 15 | Exercises | greedy solutions Homework 4 | ||
| Oct 13 | 16 | Questions and Review | Study and Read Chapter 6 | ||
| Oct 18 | MidTerm Exam | how it is done | |||
| Oct 20 | 17 | Search and Traversal | Graphs | Exercise 5 | before class 21 |
| Oct 25 | 18 | Backtracking; Branch-and-Bound | Backtrackingand others | Chapter 7 | |
| Oct 27 | 19 | Backtracking; Branch-and-Bound | Backtracking: N-Queens and AI games | Chapter 8 | |
| Nov 1 | 20 | Lower Bound Theory | Exercise5 Sol. | Chapter 10 | |
| Nov 3 | 21 | Lower Bound Theory | Comparison Trees Oracles, Reductions | ||
| Nov 8 | 22 | Non-Deterministic machines | History and Decision Problems | Chapter 11 | |
| Nov 10 | 23 | Non-Deterministic machines and Hamiltonian Circuits | Decision Problems | ||
| Nov 15 | 24 | Reducibility: Cook | Reducibility | Exercise 6 | by class 29 |
| Nov 17 | 25 | NP-hard and complete | NP-Complete reductions | Exer 6 Hints | |
| Thanksgiving Break | |||||
| Nov 29 | 26 | NP-hard and complete | NP-Complete reductions | ||
| Dec 1 | 27 | NP-Complete, DHC | NP-Complete reductions cont. | ||
| Dec 6 | 28 | NP-Hard, Cook, Turing | NP-hard, Cook Proof, Halting Problem | Exercise 6 Sol.(Ch. 11) | |
| Dec 8 | 29 | Cook, Review | Sources and Vocabulary | ||
| Dec 13 | Final Exam | how it is done |
Course notes for these lectures are here