CS7880: Special Topics in Theoretical Computer Science

Network Algorithms

Spring 2016

Instructor: Rajmohan Rajaraman
Class Meeting Times:
TuF 9:50-11:30 AM
                                     Ryder Hall 155
Office Hours:
Tu 5:00-6:00 PM 240 WVH
                        and after class

Tentative Course Schedule

Piazza LinkPiazza LinkPiazza LinkPiazza Link

Course Description   Textbook  Prerequisites   Grading   Final Project

Course Description

This course covers advanced topics in network algorithms.  The topics covered in the course can be broadly classified into three categories listed below.  This may be an amibitious list, and the actual topics covered will vary depending on time constraints and the interests of the students taking the course.

Network Processes
Network Analysis
Network Optimization
While the course will have a theoretical focus, we will draw from several applications involving networks, including the following. Also, the final projects can span the theory-experiments spectrum.


There is no required textbook for the course.  We will draw material from research papers and books listed in the schedule page.  Here are some books and course notes that will be referenced for the course.

Jon Kelner, An Algorithmist's Toolkit, MIT
Dan Spielman, Spectral Graph Theory, Yale
David Easley and Jon Kleinberg, Networks, Crowds, and Markets, Cambridge U. Press, 2010
Williamson and Shmoys, The Design of Approximation Algorithms, Cambridge U. Press
Noga Alon and Joel Spencer, The Probabilistic Method, Wiley
Luca Trevisan, Graph Partitioning and Expanders, Stanford
Michael Mitzenmacher and Eli Upfal, Probability and Computing


The prerequisite for this course is a graduate course or senior undergraduate course in algorithms.  The student must be familiar with asymptotic notation, greedy algorithms, dynamic programming, graph algorithms (e.g., minimum spanning trees, shortest paths), NP-completeness.


Since this is an advanced course, we will generally avoid stress-inducing activities such as tests. The course grade will be based on 2-3 problem sets (worth 30\%), class participation (20\%), and a project (50\%).

Since this is expected to be a small class, I am hoping that the lectures are interactive, with discussions leading toward improved understanding of technical material, and identification of research directions. Every student is expected to scribe one week's worth of lectures. The grade for class participation will be determined by the extent and impact of the student's participation in class discussions and their contributions to the scribe notes.


Students will be required to do a research project in the second half of the course.  The research project should focus on an algorithmic problem, either a fundamental theoretical problem or one well-motivated by an application. If the student is already working on a research problem relevant to the course, then a well-defined piece of the problem
with specific goals can be chosen as a research project.

Students pursuing research (or interested in pursuing research) in algorithmic application areas are strongly encouraged to formulate problems on their own for the research project. Problem and model formulation is as important a component of research as problem-solving and will be emphasized throughout the course. The research
project could also involve a substantial implementation component.

The project topics will be decided by the halfway point of the semester (by the end of February). The completion of the project will have two deliverables -- a paper and a presentation in the last 2 weeks of the semester.