CS 344: Design and Analysis of Computer Algorithms
Spring 2025, Rutgers University
Time and Location
Monday, Wednesday, 3:50pm – 5:10pm, Busch PHY 001
Instructor
Roie Levin, CoRE 306
Office Hours
Roie: Monday 11am - 12 pm CoRE 306, Friday 12pm - 1pm on zoom.
Sam: Wednesday 12:30pm – 1:30pm CoRE 329, Friday 8pm – 9pm on zoom.
Doğa: Monday 12pm – 2pm CoRE 342.
Yue: Wednesday 12:30pm – 1:30pm Hill 417, Thursday 4pm – 5pm on zoom.
Jeff: Tuesday 4pm – 6pm Hill 415.
Haoyu: Thursday 4pm – 5pm on zoom, Friday 4pm – 5pm CoRE 334.
(See Canvas for zoom links).
Staff
Graduate TAs: Doğa Diren, Lin Guo.
PTLs: Jeff Tang, Yue Yang.
Graders: Ismaeel Abdulghani, Harshankar Gudur.
Recitation
- (Jeff) Section 01: Wednesday 7:45pm - 8:40pm Busch SEC 202
- (Doğa) Section 02: Wednesday 5:55pm - 6:50pm Busch SEC 202
- (Sam) Section 03: Monday 7:45pm - 8:40pm Busch SEC 203
- (Yue) Section 04: Monday 5:55pm - 6:50pm Busch SEC 203
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 due at 11:59 pm on the specified day. The lowest homework grade will be dropped.
- Homework 0. Due Wednesday Jan 29. Solutions.
- Homework 1. Due Thursday Feb 13. Solutions.
- Homework 2. Due Thursday Feb 27.
- Homework 3
- Homework 4
- Homework 5
(Tentative) Schedule
| Date | Topic | Lecture Notes | Suggested Reading |
|---|---|---|---|
| Jan 22 | Course Overview and Basics Review | notes | Handout on Big-O notation and recurrences from Anupam Gupta, Chapter 0 of Algorithms by Jeff Erickson |
| Divide and Conquer | |||
| Jan 27 | Proof by Induction, Recursion, Tower of Hanoi, Divide and Conquer, Mergesort | notes | Appendix I, Chapter 1 of Algorithms by Jeff Erickson |
| Jan 29 | Karatsuba Multiplication, Master Theorem | notes | |
| Feb 03 | Strassen’s Algorithm, the word-RAM model, 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 | |||
| Feb 05 | Fibonacci, 0/1 Knapsack, Longest Increasing Subsequence | notes | Chapter 3 of Algorithms by Jeff Erickson. |
| Feb 10 | Edit Distance | notes | |
| Feb 12 | Optimal BST, 1d K-clustering | notes | |
| Greedy Algorithms | |||
| Feb 17 | Wrap-up 1d K-clustering, Interval Scheduling | notes | Chapter 4 of Algorithms by Jeff Erickson. |
| Feb 19 | Fractional Knapsack, Huffman Coding | notes | Notes on fractional knapsack from Rong Ge’s class |
| Graph Algorithms | |||
| Feb 24 | Graphs, BFS, DFS, Topological Sort | ||
| Feb 26 | Strongly Connected Components, Shortest Path, Dijkstra | ||
| Mar 03 | Bellman-Ford, Floyd-Warshall | ||
| Data Structures and Amortized Analysis | |||
| Mar 05 | Amortized Analysis Techniques | ||
| Mar 10 | Minimum Spanning Trees and Union Find | ||
| Mar 12 | MIDTERM | ||
| Mar 17 | Spring Break, No Class | ||
| Mar 19 | Spring Break, No Class | ||
| Randomized Algorithms | |||
| Mar 24 | Probability Review, Quicksort | ||
| Mar 26 | Hashing, Balls and Bins | ||
| Mar 31 | Perfect Hashing, Bloom Filters | ||
| Linear Programming and Optimization | |||
| Apr 02 | Flows and Matchings | ||
| Apr 07 | Linear Programming, Modeling, Intuition behind algorithms | ||
| Apr 09 | Linear Programming Duality | ||
| Apr 14 | Game Theory, Von Newmann Minimax Theorem, Yao’s Lemma | ||
| Apr 16 | Polytopes and Integrality | ||
| Limits of Computation | |||
| Apr 21 | Limits of Computation and the Complexity Hierarchy | ||
| Apr 23 | NP-Completeness, Cook-Levin Theorem, Reductions | ||
| Apr 28 | More Reductions | ||
| Advanced Topics | |||
| Apr 30 | Combatting Intractability, Approximation Algorithms | ||
| May 05 | TBD |
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.