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 11am - 1 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:

  1. Divide and conquer.
  2. Dynamic programming.
  3. Greedy Algorithms.
  4. Graph Algorithms
  5. NP-hardness and intractability.
  6. Linear Programming.
  7. Misc. Advanced Topics.

Homework

All homework is optional.


(Tentative) Schedule

Date Topic Lecture Notes Suggested Reading
Sep 03 Course Overview and Basics Review   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   Appendix I, Chapter 1 of Algorithms by Jeff Erickson
Sep 10 Karatsuba Multiplication, Master Theorem    
Sep 15 Strassen’s Algorithm, the word-RAM model, Median of Medians   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 Fibonacci, 0/1 Knapsack, Longest Increasing Subsequence   Chapter 3 of Algorithms by Jeff Erickson.
Sep 22 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.