CS 344: Design and Analysis of Computer Algorithms
Fall 2025, Rutgers University
Time and Location
Monday, Wednesday, 5:40pm – 7:00pm, Livingston TIL 232
Instructor
Roie Levin, CoRE 306
Office Hours
TBD
Roie: Monday 2pm - 4 pm CoRE 306.
Jiawei: TBD.
Puheng: TBD.
Jeff: TBD.
(See Canvas for zoom links).
Staff
Graduate TAs: Jiawei Yu, Puheng Weng.
PTLs: Jeff Tang.
Recitation
- Section 09: Monday 9:35pm - 10:30pm Livingston BE 253
- Section 10: Wednesday 7:45pm - 8:40pm Livingston BE 252
- Section 11: Monday 7:45pm - 8:40pm Livingston BE 253
Course Description
The course covers a broad set of topics in algorithms design and analysis. The goal is to cover tools and algorithms that give students the ability to (a) recognize which tool or method to apply to problems, (b) become reasonably proficient at using these tools, (c) be able to reason about the correctness and performance of the resulting algorithms.
There will be a Homework 0: if you plan to take this course, please make sure you are comfortable with the material therein.
Topics I plan to cover include:
- Divide and conquer.
- Dynamic programming.
- Greedy Algorithms.
- Graph Algorithms
- NP-hardness and intractability.
- Linear Programming.
- Misc. Advanced Topics.
Homework
All homework is optional.
-
Homework 0. Due Wednesday Sep 10. Solutions.
-
Homework 1. Due Wednesday Sep 24.
(Tentative) Schedule
| Date | Topic | Lecture Notes | Suggested Reading |
|---|---|---|---|
| Sep 03 | Course Overview and Basics Review | Syllabus, notes | Handout on Big-O notation and recurrences from Anupam Gupta, Chapter 0 of Algorithms by Jeff Erickson |
| Divide and Conquer | |||
| Sep 08 | Proofs, Induction, Recursion, Tower of Hanoi, Divide and Conquer, Mergesort | notes | What is a proof by Boaz Barak, Appendix I, Chapter 1 of Algorithms by Jeff Erickson |
| Sep 10 | Karatsuba Multiplication, Master Theorem | notes | |
| Sep 15 | Strassen’s Algorithm, Median of Medians | notes | Handout about the word-RAM model by Bo Waggoner, Notes about word-RAM (and models of computation more generally) by Boaz Barak, Chapter 3.4 of John Savage’s textbook gives a fully formal description. |
| Dynamic Programming | |||
| Sep 17 | Linear time lower bounds, Fibonacci, 0/1 Knapsack | notes | Chapter 3 of Algorithms by Jeff Erickson. |
| Sep 22 | Longest Increasing Subsequence, Edit Distance | ||
| Sep 24 | Optimal BST, 1d K-clustering | ||
| Greedy Algorithms | |||
| Sep 29 | Wrap-up 1d K-clustering, Interval Scheduling | Chapter 4 of Algorithms by Jeff Erickson. | |
| Oct 01 | Fractional Knapsack, Huffman Coding | Notes on fractional knapsack from Rong Ge’s class | |
| Oct 06 | MIDTERM I | ||
| Graph Algorithms | |||
| Oct 08 | Wrapup Huffman Coding, Intro to Graphs | Chapter 5 and Chapter 6 of Algorithms by Jeff Erickson | |
| Oct 13 | BFS, Shortest Paths, DFS, Topological Sort | ||
| Oct 15 | Strongly Connected Components | ||
| Data Structures and Amortized Analysis | |||
| Oct 20 | Dijkstra’s Algorithm | Chapter 8 of Algorithms by Jeff Erickson. Advanced reading: Kevin Wayne’s slides on binary & binomial heaps and on Fibonacci heaps | |
| Oct 22 | Bellman-Ford, Floyd-Warshall, Amortized Analysis | Chapter 9 of Algorithms by Jeff Erickson. | |
| Oct 27 | Amortized Analysis | Director’s Cut, Chapter 9 of Algorithms by Jeff Erickson | |
| Oct 29 | Minimum Spanning Trees and Union Find | Chapter 7 of Algorithms by Jeff Erickson | |
| Randomized Algorithms | |||
| Nov 03 | Probability Review, Quicksort | Director’s Cut, Chapter 1 and Chapter 2 of Algorithms by Jeff Erickson | |
| Nov 05 | Hashing | Director’s Cut, Chapter 5 of Algorithms by Jeff Erickson | |
| Nov 10 | Hashing Wrap-up, Balls and Bins | ||
| Linear Programming and Optimization | |||
| Nov 12 | Flows and Matchings | Chapter 10 of Algorithms by Jeff Erickson | |
| Nov 17 | Ford Fulkerson | ||
| Nov 19 | MIDTERM II | ||
| Nov 24 | Thanksgiving Recess, No Class | ||
| Nov 26 | Thanksgiving Recess, No Class | ||
| Dec 01 | Linear Programming, Modeling, Intuition behind algorithms | Chapter H of Algorithms by Jeff Erickson | |
| Dec 03 | Polytopes and Integrality | ||
| Limits of Computation | |||
| Dec 08 | Limits of Computation and the Complexity Hierarchy | Chapter 12 of Algorithms by Jeff Erickson | |
| Dec 10 | NP-Completeness, Cook-Levin Theorem, Reductions | ||
| TBD | FINAL |
Resources
LaTeX: Short and Long guide to latex. For the purpose of this course, you do not even need to install LaTeX and can instead use an online LaTeX editor such as Overleaf.