CS 513: Design and Analysis of Algorithms

Course Information

• Instructor: Dr. Xin
• Office Hours: TBD
• Location: TBD
• Time: Fridays, TBD
• Credits: 3
• Prerequisites: Undergraduate algorithms course or equivalent

Course Description

This is a graduate-level course on the design and analysis of algorithms, intended for PhD students. 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 motivated by applications in large-scale data analysis, graph theory, and machine learning. 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.

Course Topics

The list of topics we plan to cover includes, but is not limited to:

• Divide and Conquer: (e.g., Strassen's Algorithm, Closest Pair)
• Dynamic Programming: (e.g., Knapsack, Sequence Alignment)
• NP and Intractability: (e.g., Reductions, Cook-Levin Theorem)
• Approximation Algorithms: (e.g., Set Cover, Vertex Cover, Max-Cut)
• Randomized Algorithms: (e.g., Hashing, LSH, Bloom Filters, Karger's Min-Cut)
• Spectral Graph Theory: (e.g., Graph Laplacian, Spectral Clustering)
• Dimensionality Reduction: (e.g., PCA, Johnson-Lindenstrauss Lemma)
• Other Topics: (e.g., Gradient Descent, Quantum Algorithms)

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

Evaluation (Tentative)

• Homework Assignments (50%): There will be 3-4 problem sets throughout the semester. You may discuss problems with your classmates, but you must write up your solutions independently.
• Final Project (50%): A research-oriented final project on a topic of your choice, related to the course material. This could be a literature survey, an implementation of a recent algorithm, or an exploration of an open problem. A project proposal, presentation, and final report will be required.

Textbooks and Resources

The main textbook for this course is:

• Christos Papadimitriou, Sanjoy Dasgupta, and Umesh Vazirani: Algorithms [PDV]

The following additional books are excellent references for the topics covered in this course:

• Jon Kleinberg and Éva Tardos: Algorithm Design [KT]
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein: Introduction to Algorithms [CLRS]
• Vijay V. Vazirani: Approximation Algorithms [V]
• Michael Mitzenmacher and Eli Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis [MU]

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.

Contact Information

For questions about the course, please contact Dr. Xin during office hours or via email. Course announcements and materials will be posted on the course website.