CS860 Advanced Topics in Theoretical Computer Science

Topic: Algorithmic Problems of the Internet

Instructor: Alex Lopez-Ortiz

The Internet has grown from a network connecting selected computer science departments in North America merely fifteen years ago to a network connecting 150 million computers and 600 million people across the entire world. To this date, growth remains unabated at a rate of hundreds of thousands of new users per day.

As such, the Internet is a hotbed of algorithmic challenges. In this setting linear time algorithms are often impractical, and for settings such as routing even log log n time solutions are considered too slow. Other theoretical problems occurring are secure protocols, distributed computing and approximate measuring. In particular this course will cover the following topics:

For each topic, we will go over an introduction to the main problem and an overview of selected results in the area.

Prerequisites: A solid undergraduate knowledge of algorithm analysis and data structures is required. An "algorithms course" like CS 666 would be helpful, but is certainly not necessary.

Organization: The first part of the course will consist of lectures primarily given by the instructor. Later classes will be seminars presented by one or more members of the class. Credit for the course will be based on the two presentations, a problem set and the course project. The project will involve reading several recent papers in a topic, presenting an overview of the paper(s) to class, attempting to improve upon or to apply the results of the papers, and reporting on this work both in class and in a written report. These projects may involve implementations or not, depending on the interests of the individual student(s).

References: There is no formal text, most of the material covered will come from the recent literature in the field of algorithms and data structures.

Class time: Organization meeting on Tuesday, May 2, at 10:00 in DCXXXX. The tentative schedule is to meet Tuesdays and Thursdays from 10:00 to 11:30 in DCXXXX. Classes are scheduled for 3 hours per week to accommodate any necessary cancellations.