tentative schedule
| Date | DAY | Material | NOTES | ASSIGNMENT | DUE | |
| Jan 24 | 1 | Introduction, Web Page, Conventions | homepage and Ch. 1 | Read Preface, Ch1: 1.1 to 1.3 | ||
| Jan 26 | 2 | Recursion and Induction | Recursion examples and Induction review | Try recursion problems (not turnin), Read Ch1: 1.3 | ||
| Jan 31 | 3 | Recursion and Induction problems | Looking at these Start performance: T(n), O(n), etc. | Read handout: Analysis Techniques | ||
| Feb 2 | 4 | Performance Analysis | T(n), O(n), recursive algorithms | Homework 1 | before class 8 | |
| Feb 7 | 5 | Performance Analysis | finish performance, recurrance relations | Read handout: Analysis Techniques again | ||
| Feb 9 | 6 | Data Structures | sets | Read Chapter 2! Exercise 2 | ||
| Feb 14 | 7 | Divide and conquer | Divide and Conquer | Read Chapter 3 | ||
| Feb 16 | 8 | Divide and conquer | Divide and Conquer | Exercise 3 | before class 12 | |
| Feb 21 | 9 | Greedy Method | Knapsack | Read Chapter 4 | ||
| Feb 23 | 10 | Greedy method | Minimum Spanning Trees and SS Shortest Path | |||
| Feb 28 | 11 | Dynamic Programming | Dynamic Programming | Exercise 4 Read Chapter 5 | before class 14 | |
| Mar 1 | 12 | Dynamic programming look at exercise 2 solution and exercise 3 | Dynamic Programming Coin Changing Homework | |||
| Mar 6 | 13 | Dynamic programming | Dynamic Programming | |||
| Mar 8 | 14 | Exercises | Solutions | |||
| Mar 13 | 15 | MidTerm Exam | ||||
| Mar 15 | 16 | Search and Traversal | Graphs | Exercise 5 | before class 19 | |
| Spring Break | ||||||
| Mar 27 | 17 | Search and Traversal Backtracking; Branch-and-Bound | Graphs Backtracking | Ex. 5 hints | ||
| Mar 29 | 18 | Backtracking; Branch-and-Bound | Backtracking and others | |||
| Apr 3 | 19 | Exercise 5 solutions | Exercise 5 | |||
| Apr 5 | 20 | Lower Bound Theory, Oracles, Reductions | Comparison Trees, Lower Bound Theory Oracles, Reductions | |||
| Apr 10 | 21 | Non-Deterministic machines and Decision Problems | History , NP and Decision Problems | |||
| Apr 12 | 22 | Non-Deterministic machines and Decision Problems Hamiltonian Cycle example and proof | Hamiltonian Cycle | |||
| Apr 17 | 23 | NP, Polynomially Equivalent, NP-Hard, NP-Complete | Clique, poly equiv and Satisfiability | |||
| Apr 19 | 24 | NP-Hard, NP-Complete, Cook, Halting Problem | Cook and Defs. Halting Prob. | |||
| Apr 24 | 25 | SAT, Clique, Node Cover | reductions | Exercise 6 | by class 29 | |
| Apr 26 | 26 | NP-hard and complete | NP-Complete reductions | |||
| May 1 | 27 | NP-hard and complete | NP-Complete reductions cont. | |||
| May 3 | 28 | NP-Complete, DHC | NP-hard Optimizations | exercise 6: (hints) | ||
| May 8 | 29 | NP-Hard, Cook, Turing | Cook Proof | solutions | ||
| May 10 | 30 | Cook, Review | Sources and Vocabulary | |||
| May 14 | Final Week | Monday | Office hour: 1-3 pm | |||
| May 15 | Final: in class | Final Tuesday 12:00-1:50 | FINAL Yes, 8.5x11 cheat sheet allowed again one side |
Course notes for these lectures are here