A range of fundamental theoretical concepts and tools are invaluable for researchers in systems and networking. This seminar course surveys several of those topics with lectures given by CS and ECE faculty who are experts on the respective topics. Each lecture or pair of lectures will act as a brief introduction to the topic and as a teaser for a full course. Lectures will generally cover
 basic definitions and principles,
 major results,
 example applications, and
 references to more complete material (courses, survey papers, or books).
We meet every Wednesday 4:00  4:50 p.m. in 1109 SC, beginning January 27. The seminar is organized by Klara Nahrstedt^{}, Indy Gupta^{}, and Brighten Godfrey^{}.
Student responsibilities include attendance and one of the following two options:
 Scribing: In a group of two, scribe a lecture and post the notes on the wiki. Notes should be posted by the day before the next lecture (i.e., you have six days to post the notes). The scribe notes should contain 23 pages of text based on the lecture. In addition, scribes should post external links, recommended books or papers on the topic (beyond the speaker's recommendations).
 Paper review and presentation: In a group of two or alone: For one lecture, find and read a systems or networking paper that applies the theory. Post on the wiki a short (at most one page) description of what the paper does and how it uses the theoretical concepts and results we studied. At the end of the course, give a very brief (24 minute) presentation describing the paper and how it applies the theory.
Signup: The sections below have a bullet for each scribed lecture or presentation slot. Please put your name after one of the bullets where there is a free slot (up to two people for scribes; one presenter for now, and we'll increase the number of presenters if necessary.)
In addition, we encourage students to contribute resources to this wikicomments, pointers to particularly good survey papers or other external resources, etc. The wiki will be a public resource for graduate students in systems & networking and other areas.
Schedule
Date  Speaker  Topic 

Jan 27  Indranil Gupta^{}  Course introduction and the scientific method 
Feb 3  Klara Nahrstedt^{}  Statistics 
Feb 10  David Nicol^{}  Simulation 
Feb 17  Tamer Basar^{}  Game Theory 
Feb 24  Tamer Basar^{}  Game Theory 
Mar 3  R. Srikant^{}  Optimization Theory in the Internet 
Mar 10  R. Srikant^{}  Optimization Theory in Wireless 
Mar 17  Seminar canceled  
Mar 31  Sean Meyn^{}  Control Theory 
Apr 7  Sean Meyn^{}  Control Theory 
Apr 14  Jeff Erickson^{}  Randomized Algorithms and Data Structures 
Apr 21  Jeff Erickson^{}  Randomized Algorithms and Data Structures 
Apr 28  Grigore Rosu^{}  Formal Methods 
May 5  Students  Student paper presentations 
Resources by topic
This section collects the course resources by topic, including lecture slides, scribe notes, and pointers to external resources.
General
 Indy Gupta slides: Course Introduction^{} and The Scientific Method^{}
 Jennifer Rexford: My Ten Favorite "Practical Theory" Papers^{}
 Matthias Grossglauser: 10 Papers on Network Models^{}
 Michael Mitzenmacher: Algorithms at the End of the Wire^{}
 Guy Blelloch: Algorithms in the Real World^{}
 S. Keshav: Mathematical Foundations of Computer Networking^{} or the book in PDF^{}
 John Byers: Algorithmic Aspects of Computer Networking^{}
Statistics
 Klara Nahrstedt slides: Statistics (PDF)^{} Statistics (PPT)^{}
 Lecture 1 scribe notes (Ashish Vulimiri, Brian Cho)
 Presenter(s):
Simulation
 David Nicol: Simulation slides^{} Bibliography (.bib)^{}
 Lecture scribe notes (Ravinder Shankesi, Jianqing Zhang)
 Presenter(s):
Game Theory
 Tamer Basar: Game theory slides^{}
 Lecture 1 scribe notes (Tanmay Khirwadkar, Steven Chieng)
 Lecture 2 scribe notes^{} (Virajith Jalaparti, Imranul Hoque)
 Presenter(s): Rachit Agarwal
 Noam Nisan, Eva Tardos, and Vijay Vazirani, eds. Algorithmic Game Theory^{}. Available free online^{} with username agt1user and password camb2agt .
 Noam Nisan. Algorithmic Game Theory^{} blog.
 Tim Roughgarden: An Algorithmic Game Theory Primer^{}
 Tim Roughgarden: Selfish Routing and the Price of Anarchy (Survey)^{}
 Chandra Chekuri: CS 573: Topics in Algorithms  Algorithmic Game Theory^{}
 Xi Chen and Alex Fabrikant: Intro to Algorithmic Game Theory MiniCourse^{}
Optimization Theory
 R. Srikant: Optimization theory slides^{}
 Lecture 1 scribe notes ^{} (Ahsan Arefin, Pooja Agarwal)
 Lecture 2 scribe notes ^{} (Thadpong Pongthawornkamol, Kurchi Subhra Hazra)
 Presenter(s): Tae Hyun Kim Optimization Theory in Practice^{} (Slides^{})
Analytic Modeling
 Lecture scribe notes (Shivaram Venkataraman, Abhishek Verma)
 Presenter(s):
Control Theory
 Lecture 1 scribe notes^{} (YingYi Liang, Mirko Montanari)
 Lecture 2 scribe notes^{} (Jung Eun Kim, Man Ki Yoon)
 Presenter(s): Yusuf Sarwar
Randomized Algorithms and Data Structures
 Lecture 1 scribe notes (Damion Mitchell, Naveen Cherukuri)
 Lecture 2 scribe notes (ChiYao Hong, ChiaChi Lin)
 Presenter(s): Zonouz
 Presenter(s): Rini Kaushik Bloom Filters^{}
Hash Tables
 Andrei Broder and Michael Mitzenmacher: Network Applications of Bloom Filters: A Survey^{} (2005)
 Adam Kirsch, Michael Mitzenmacher, and George Varghese: HashBased Techniques for HighSpeed Packet Processing^{} (2008)
 Michael Mitzenmacher, Andréa W. Richa, and Ramesh Sitaraman. The Power of Two Random Choices: A Survey: A Survey of Techniques and Results^{} (2001)
Datastream Algorithms
 Noga Alon, Yossi Matias, and Mario Szegedy: The space complexity of approximating the frequency moments^{} (1999)
 Daniel Kane*, Jelani Nelson*, and David Woodruff: An Optimal Algorithm for the Distinct Elements Problem^{} (2010)
 Muthu Muthukrishnan: Data Streams: Algorithms and Applications^{} (2005)
 Muthu Muthukrishnan: Notes from a streaming workshop^{} (2009)
 Andrew McGregor: Crash Course on Data Stream Algorithms Part 1^{}, Part 2^{}
Future Classes
 CS 598: Randomized Algorithms, to be offered by Sariel HarPeled in Fall 2010.
 CS 598: Data Structures, to be offered by Jeff Erickson in Spring 2011.
Formal Methods
 Grigore Rosu: PDF slides^{}, PPTX slides^{}
 Lecture scribe notes^{} (Raoul Rivas, Taylor Johnson)
 Presenter(s):
Additional topics
We can hardly cover (even briefly) all theoretical tools that are useful in systems & networking. In particular, we have not covered queueing theory, coding theory and network coding, machine learning, information theory, random graph theory, network flow, and many other topics. Below are a few survey papers and courses on topics not covered in this seminar.
 Michael Mitzenmacher: Digital Fountains: A Survey and Look Forward^{}
 David Aldous: Random Graphs and Complex Networks^{}
Recently Updated

Navigate space 
Labels
Page: Bloom Filters 2
Page: Control Theory 1
Page: Control Theory 2
Page: Distinct Elements in Data Streams
Page: Formal Methods
Page: Game Theory 1
Page: Game Theory 2
Page: HashBased Techniques
Page: Implications of Game Theoretic Results in Practice
Page: Optimization Theory
Page: Optimization Theory in Practice
Page: Optimization Theory in Wireless Networks
Page: Simulation