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

Network Processes

- Random walks and Markov chains
- Small-world phenomena
- Consensus networks
- Information spreading protocols

- Processing of large-scale networks
- Graph clustering
- Graph sparsification
- Graph streams

- Approximation algorithms for network design
- Multicommodity flow
- Steiner network design

- Linear programming (LP) based methods: rounding, primal-dual
- Semidefinite programming (SDP) methods
- Multiplicative weights method

- Analysis of large-scale graph and network data
- Diffusion in social networks
- Epidemics
- Design of graph structures in networking
- Routing in communication networks
- Distributed systems

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

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

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.

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.