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 Thursday 11am - 12 pm CoRE 306 on zoom, 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 2pm – 3pm 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, Haoyu Li.
PTLs: Jeff Tang, Yue Yang.
Graders: Ismaeel Abdulghani, Harshankar Gudur.
Recitation
- (Jeff) Section 01: Wednesday 7:45pm - 8:40pm Busch SEC 202
- (Haoyu) 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. Solutions.
- Homework 3. Due
Sunday March 16Thursday March 27. - 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 | Wrapup Huffman Coding, Intro to Graphs | notes | Chapter 5 and Chapter 6 of Algorithms by Jeff Erickson |
| Feb 26 | BFS, Shortest Paths, DFS, Topological Sort | notes | |
| Mar 03 | Strongly Connected Components | notes | |
| Data Structures and Amortized Analysis | |||
| Mar 05 | Dijkstra’s Algorithm | notes | Chapter 8 of Algorithms by Jeff Erickson. Advanced reading: Kevin Wayne’s slides on binary & binomial heaps and on Fibonacci heaps |
| Mar 10 | Bellman-Ford, Floyd-Warshall, Amortized Analysis | note | Chapter 9 of Algorithms by Jeff Erickson. |
| Mar 12 | MIDTERM | Practice Midterm, and Solutions | |
| Mar 17 | Spring Break, No Class | ||
| Mar 19 | Spring Break, No Class | ||
| Mar 24 | Amortized Analysis | notes | Director’s Cut, Chapter 9 of Algorithms by Jeff Erickson |
| Mar 26 | Minimum Spanning Trees and Union Find | Chapter 7 of Algorithms by Jeff Erickson | |
| Randomized Algorithms | |||
| Mar 31 | Probability Review, Quicksort | Director’s Cut, Chapter 1 and Chapter 2 of Algorithms by Jeff Erickson | |
| Apr 02 | Hashing, Balls and Bins | Director’s Cut, Chapter 5 of Algorithms by Jeff Erickson | |
| Apr 07 | Perfect Hashing, Bloom Filters | ||
| Linear Programming and Optimization | |||
| Apr 09 | Flows and Matchings | ||
| Apr 14 | Linear Programming, Modeling, Intuition behind algorithms | ||
| Apr 16 | Linear Programming Duality | ||
| Apr 21 | Polytopes and Integrality | ||
| Limits of Computation | |||
| Apr 23 | Limits of Computation and the Complexity Hierarchy | ||
| Apr 28 | NP-Completeness, Cook-Levin Theorem, Reductions | ||
| Apr 30 | More Reductions | ||
| Advanced Topics | |||
| May 05 | Combatting Intractability, Approximation Algorithms | ||
| May 14 | 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.