For the abbreviation of recommended readings, see the Textbook section on the course page.
| Week | Date | Topic | Contents | Other Notes |
|---|---|---|---|---|
| 1 | Aug 24 (Mon) | Introduction | Course Syllabus | |
| Aug 26 (Wed) | Algorithm Pseudocode and Asymptotic Analysis (KT 2.2) | HW1 Released | ||
| Aug 28 (Fri) | Big O, Big Omega and Theta Notations, Running Times (KT 2.4) | |||
| 2 | Aug 31 (Mon) | Graph Basics | Graph Notations (KT 3.1, KT 3.2) | |
| Sep 02 (Wed) | Graph Types and Traversal (KT 3.4) | Task 1 Released | ||
| Sep 04 (Fri) | Bipartiteness Test and Topological Order (KT 3.4, KT 3.6) | |||
| 3 | Sep 07 (Mon) | Labor Day Observed, No Class | ||
| Sep 09 (Wed) | Greedy Algorithms | Box Packing (KT 4.1) | HW1 Deadline; HW2 Released | |
| Sep 11 (Fri) | Interval Scheduling (KT 4.1) | |||
| 4 | Sep 14 (Mon) | Interval Partition | ||
| Sep 16 (Wed) | Optimum Caching (KT 4.3) | Task 1 Deadline | ||
| Sep 18 (Fri) | Optimum Caching and Huffman Code (KT 4.8) | |||
| 5 | Sep 21 (Mon) | Huffman Code (KT 4.8) | ||
| Sep 23 (Wed) | More Greedy Algorithms | HW2 Deadline; P1 Released | ||
| Sep 25 (Fri) | Midterm Exam I Review | |||
| 6 | Sep 28 (Mon) | Divide and Conquer | Sorting Problem and Merge Sort (KT 5.1, KT 5.3) | |
| Sep 30 (Wed) | Counting Inversions (KT 5.3) | |||
| Oct 02 (Fri) | Midterm Exam I (In Class) | |||
| 7 | Oct 05 (Mon) | Quick Sort and Selection Problem (KT 13.5) | ||
| Oct 07 (Wed) | Polynomial Multiplication (KT 5.5) | HW3 Released | ||
| Oct 09 (Fri) | Solving Recurrences and Fibonacci Numbers (KT 5.2) | |||
| 8 | Oct 12 (Mon) | Fall Break, No Class | ||
| Oct 14 (Wed) | More Divide-and-Conquer Algorithm Exercise Problems | P1 Deadline; Task 2 Released | ||
| Oct 16 (Fri) | Dynamic Programming | Weighted Interval Scheduling (KT 6.1) | ||
| 9 | Oct 19 (Mon) | Subset Sum Problem (KT 6.4) | ||
| Oct 21 (Wed) | Knapsack Problem (KT 6.4) | HW3 Deadline | ||
| Oct 23 (Fri) | Sequence Alignment (KT 6.6) | |||
| 10 | Oct 26 (Mon) | Matrix-Chain Multiplication | ||
| Oct 28 (Wed) | Optimum Binary Search Tree | Task 2 Deadline; P2 Released | ||
| Oct 30 (Fri) | More Dynamic Programming Exercises and Midterm Exam II Review | |||
| 11 | Nov 02 (Mon) | Graph Algorithms | Kruskal's Algorithm and Reverse-Kruskal's Algorithm (KT 4.5) | |
| Nov 04 (Wed) | Prim's Algorithm for MST (KT 4.6) | |||
| Nov 06 (Fri) | Midterm Exam II (In Class) | |||
| 12 | Nov 09 (Mon) | Shortest Paths and Dijkstra's Algorithm (KT 4.4) | ||
| Nov 11 (Wed) | Dijkstra's Algorithm (KT 4.4) | Last Day to Resign | ||
| Nov 13 (Fri) | Shortest Paths with Negative Weights | |||
| 13 | Nov 16 (Mon) | Bellman–Ford Algorithm (KT 6.8) | ||
| Nov 18 (Wed) | Floyd–Warshall Algorithm | P2 Deadline; HW4 Released | ||
| Nov 20 (Fri) | More Graph Algorithm Exercise Problems | |||
| 14 | Nov 23 (Mon) | NPC | P, NP, co-NP (KT 8.1–KT 8.3) | |
| Nov 25 (Wed) | Thanksgiving Break, No Class | |||
| Nov 27 (Fri) | Thanksgiving Break, No Class | |||
| 15 | Nov 30 (Mon) | Polynomial-Time Reductions and NP (KT 8.4) | ||
| Dec 02 (Wed) | Circuit-SAT, 3-SAT (KT 8.5) | HW4 Deadline | ||
| Dec 04 (Fri) | Independent Set Problem (KT 8.5), Solving NP-Hard Problems | |||
| 16 | Dec 07 (Mon) | Last Day of Classes, Recap, Review, and Questions | ||
| Dec 09 (Wed) | Final Exam, 3:30 PM–6:30 PM, Knox 104 |
| HWs/Projects | Releasing Date | Deadline |
|---|---|---|
| HW1 | Wed, Aug 26 | Wed, Sep 09 |
| HW2 | Wed, Sep 09 | Wed, Sep 23 |
| HW3 | Wed, Oct 07 | Wed, Oct 21 |
| HW4 | Wed, Nov 18 | Wed, Dec 02 |
| Project 1 | Wed, Sep 23 | Wed, Oct 14 |
| Project 2 | Wed, Oct 28 | Wed, Nov 18 |
| Task 1 | Wed, Sep 02 | Wed, Sep 16 |
| Task 2 | Wed, Oct 14 | Wed, Oct 28 |
Deadlines: All assignment deadlines are on Wednesday at 11:59 PM EST. Expectations will be clearly stated when assignments are released, including the duration of each assignment. Please pay close attention to the allotted time and begin early.
Exams: Midterm Exam I is scheduled for Friday, October 2. Midterm Exam II is scheduled for Friday, November 6. The final exam is scheduled for Wednesday, December 9, from 3:30 PM to 6:30 PM in Knox 104.
Submission Format: Submit typed PDF files for homework. You may use any word processor of your choice; Microsoft Word and LaTeX are recommended. For web-based LaTeX editing, you may use platforms such as Overleaf.
Submission Platform: All assignments will be submitted and returned via UB Learns.