CS 513: Design and Analysis of Algorithms
Graduate course, Rutgers University, Computer Science Department, 2025
This is a graduate-level course on the design and analysis of algorithms. We will explore fundamental techniques for designing and analyzing efficient algorithms for computationally challenging problems. The course will cover classic paradigms as well as modern algorithmic techniques. The goal is to provide students with a robust theoretical foundation and an understanding of the mathematical tools needed to tackle complex algorithmic problems in their own research.
This course expects students with undergraduate algorithm knowledge. If you plan to take this course, I expect that you know what the following words mean: Big-O notion, Time/Space Complexity, Run-time analysis, Asynmpotic Upper and Lower bounds.
Course Information
- Instructor: Cheng Xin
- Office Hours: Fridays, 5pm - 6pm
- Location: Busch SEC-209
- Time: Fridays, 2pm - 5pm
- Credits: 3
- Prerequisites: Undergraduate algorithms course or equivalent
Course Topics
The list of topics we plan to cover includes, but is not limited to:
- Divide and Conquer: [CLRS] Ch 4, 30; [DPV] Ch 2; [Homework1]; [Sample Solutions]
- Greedy algorithms: [CLRS] Ch 16, 23, 24; [DPV] Ch 4,5;
- Dynamic Programming: [CLRS] Ch 24, 25, 15; [DPV] Ch 4,6; [Homework2]; [Sample Solutions (update)]
- NP and Intractability [CLRS] Ch 34; [DPV] Ch 8; [KT] Ch 8; [Homework3];
- Approximation Algorithms
- Randomized Algorithms
- Graph Algorithms
- Other Topics…
The selection of topics may be adjusted based on class progress and interest.
Some specific references:
- Proof of the Master Theorem: [CLRS] Chapter 4, Section 4.6,
- QuickSort: Nice lecture notes and slides from Dr. Michael Dinitz
- 3DM: Nice slides from Dr. Carl Kingsford
- FPTAS algorithm for 0-1 Knapsack Problem: [Lecture Note]; [Paper];
Grading: Midterm (50%) + Final (50%).
- Both midterm and final exams are closed book. The final exam is cumulative. You are allowed to bring a handwritten letter-size “cheat sheet”.
(Optional) Homework
- All homework assignments are optional for self-practice. Feel free to ask questions on Piazza.
Recommended Textbooks:
- [DPV] Algorithms, Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh Vazirani, McGraw-Hill, 2006.
- [KT] Algorithm design, by Jon Kleinberg, Eva Tardos, Addison-Wesley, 2005.
- [CLRS] Introduction to algorithms, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, The MIT Press, 3nd edition, 2009.
- [Va] Approximation algorithms, Vijay V. Vazirani.
Good lecture notes:
- Jeff Erickson: http://jeffe.cs.illinois.edu/teaching/algorithms/
Academic Integrity
Any form of academic dishonesty will be taken seriously and handled according to the university’s academic integrity policy.