tentative schedule
| Date | DAY | Material | NOTES | ASSIGNMENT | DUE | |
| Aug 24 | 1 | Introduction, Web Page, Conventions | homepage and Ch. 1 | Read Preface, Ch1: 1.1 to 1.3 | ||
| Aug 26 | 2 | Recursion and Induction | Recursion examples and Induction review | Try recursion problems (not turnin), Read Ch1: 1.3 | ||
| Aug 31 | 3 | Recursion and Induction problems | Looking at these Start performance | Read handout: Analysis Techniques | ||
| Sept 2 | 4 | Performance Analysis | T(n), O(n), etc. | Homework 1 | before class 9 | |
| Sept 7 | Day 5 | Performance Analysis | T(n), O(n), recursive algorithms | Read handout: Analysis Techniques again | ||
| Sept 9 | 6 | Review of Data Structures | finish performance | Read Chapter 2! | ||
| Sept 14 | 7 | Data Structures | sets | Read Chapter 3 | ||
| Sept 16 | 8 | Divide and conquer | Divide and Conquer | Exercise 2 | ||
| Sept 21 | 9 | Greedy Method | Knapsack | Read Chapter 4 Exercise 3 | before class 13 | |
| Sept 23 | 10 | Greedy method | Minimum Spanning Trees and SS Shortest Path | |||
| Sept 28 | 11 | Dynamic Programming | Dynamic Programming | Read Chapter 5 | ||
| Sept 30 | 12 | Review Greedy look at exercise 2 solution and exercise 3 | Dynamic Programming | Exercise 4 | before class 15 | |
| Oct 5 | 13 | Dynamic programming | Dynamic Programming | |||
| Oct 7 | 14 | Exercises | Solutions | |||
| Oct 12 | 15 | Search and Traversal | Graphs | Note from class: CSCI 351 Chapter 1 and whole class | ||
| Oct 14 | 16 | examples | dynamic programming solution | Exercise 5 | ||
| Oct 19 | 17 | Backtracking; Branch-and-Bound Review | Backtracking and others | |||
| Oct 21 | 18 | MidTerm Exam | ||||
| Oct 26 | 19 | Lower Bound Theory, Oracles, Reductions | Comparison Trees, Lower Bound Theory Oracles, Reductions | before class 22 | ||
| Oct 28 | 20 | Non-Deterministic machines and Decision Problems | Decision Problems | hints | ||
| Nov 2 | 21 | No Class | ||||
| Nov 4 | 22 | No Class | ||||
| Nov 9 | 24 | Non-Deterministic machines and Decision Problems Hamiltonian Cycle example and proof | History and Decision Problems | Exercise 5 solution | ||
| Nov 11 | NO CLASS:Veterans' Day | |||||
| Nov 16 | 25 | Reducibility: Cook | Decision Problems and Reducibility | Exercise 6 | by class 29 | |
| Nov 18 | 26 | NP-hard and complete | Reducibility, poly equivalancy and SAT | |||
| Thanksgiving Break | ||||||
| Nov 30 | 27 | NP-hard and complete | Finish Reducibility, then NP-Complete reductions | |||
| Dec 2 | 28 | NP-Complete, DHC | NP-Complete reductions cont. | exercise 6: (hints) | ||
| Dec 7 | 29 | NP-Hard, Cook, Turing | NP-hard, Cook Proof, Halting Problem | |||
| Dec 9 | 30 | Cook, Review | Sources and Vocabulary | |||
| Dec 13 Dec 15 |
Final Week | Monday Wednesday |
Office Hours 1:00-2:00 Office Hours 9:00-9:50 |
|||
| Dec 14 | Final: in class | Final Tuesday 2:00-3:50 | FINAL Yes, 8.5x11 cheat sheet allowed again one side |
Course notes for these lectures are here