Cheng Xin

Cheng Xin

Postdoc Scholar @ Rutgers University [on Job Market].

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
  • Greedy algorithms
  • Dynamic Programming
  • NP and Intractability
  • Approximation Algorithms
  • Randomized Algorithms
  • Graph Algorithms
  • Other Topics…

The selection of topics may be adjusted based on class progress and interest.

Grading:

Roughly 6-7 written homework (30%), midterm (35%) and final (35%).

  • You may discuss problems with your classmates, but you must write up your solutions independently
  • All homework must be written in LaTeX and submitted as compiled PDF files
  • No late homework will be accepted
  • The lowest homework score will be dropped from the final grade calculation
  • Both midterm and final exams are closed book. The final exam is cumulative. You are allowed to bring a handwritten letter-size “cheat sheet”.
  • [PDV] Algorithms, Christos Papadimitriou, Sanjoy Dasgupta, 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, 2nd edition, 2001.
  • [Va] Approximation algorithms, Vijay V. Vazirani.

Good lecture notes:

  • Jeff Erickson: http://jeffe.cs.illinois.edu/teaching/algorithms/

Academic Integrity

All work submitted in this course must be your own. For homework assignments, collaboration on high-level ideas is permitted, but you must write your solutions independently and list the names of your collaborators. Any form of academic dishonesty will be taken seriously and handled according to the university’s academic integrity policy.