CS7260: Design and Analysis of Network/Router Algorithms and Hardware

  Fall 2011, College of Computing, Georgia Tech
class webpage:  http://www-static.cc.gatech.edu/classes/AY2012/cs7260_fall

Instructor: Prof. Jun (Jim) Xu

Class meeting times: MWF 1:05 to 1:55
Classroom: Architecture (East) 107

Office:  KACB 3350
Office phone:  404-385-2168
Office hours:  MW 2 to 3pm
Email:  jx@cc.gatech.edu

TA: Nan Hua (nanhua@cc.gatech.edu)
TA's office hours: M 2 to 4 pm
TA is located in KACB 3337

Table of Contents

Course Information and Objectives

Textbook and additional references

Approximately half of the course material will come from the following textbook:

Network Algorithmics

by George Varghese, Morgan Kaufmann, 2005 (available at Engineer's Bookstore).

The other half will come from research papers (many by myself). We will also cover parts of the following book (you don't need to purchase it):

Syllabus - Tentative schedule (subject to adjustments)

The reading list will be updated every week, before we cover the corresponding topic.  The schedule is approximate and subject to changes.

Streaming Algorithms for Counting Distinct Elements (Slides)

I could not find the "Walmart example" I covered in class.  This one is close enough or even better.

"A sketch algorithm for estimating two-way and multi-way associations"
Ping Li and Kenneth W. Church, Computational Linguistics 33(3), 305-354, 2007

Project (tentative)

Perhaps the most exciting part of this course will be the term project. In groups of 3-4 students, you will specify, design, and/or implement (if possible) something (an algorithm, hardware/software system, or protocol) that is novel and/or requires significant effort.  This project must be related to network algorithmics.  I suggest that you look at the recent (online) proceedings of conferences such as SIGMETRICS, SIGCOMM, ANCS, or IMC to get some ideas about novel network algorithmics.  So, start thinking about project partners and cool project ideas!

There are some constraints however:

Project milestones:

  1. Form groups, submit 1-page project proposal: TBD
  2. Final deadline - final project report submission:  TBD
  3. Demos: TBD
The project grade will be determined at the end of the semester taking into account all previous milestones.



Homework 1:

The part that you NEED NOT turn in:  (solution): p15 problem 1-1, p232 problem 10-1, p267 problems 11-1, 11-2, 11-3, 11-5, 11-14, p397 problems 16-2, 16-3, 16-4, p300 problems 12-1, 12-2, 12-3, 12-4, 12-6, 12-7

The part that you NEED to turn in.

Grading (tentative)

Course Policies