CS E-210 -- Algorithms at The Ends of the Wire

Preliminary Syllabus

Instructor: Michael Mitzenmacher
E-mail: michaelm AT eecs.harvard.edu
Office: Maxwell Dworkin 331
Office Hours: Tuesday/Thursday 1:00 -2:00 (subject to change, depending on conflicts). Or, better, by appointment.

Teaching Assistant: TBD
E-mail: TBD
Office Hours: TBD

Syllabus: www.eecs.harvard.edu/~michaelm/CS222/syllabus.html

Handouts: www.eecs.harvard.edu/~michaelm/CS222/class.html

Objectives

This course is loosely based on the theme of how to deal with really big data, especially over networks. The topics change from year to year, and the professor is traveling this summer, so the below is subject to change. The course will consist of multiple independent units, covering the major themes of information retrieval (search engines), compression, data summarization algorithms, and coding. Although the course will emphasize theoretical foundations, it will definitely be a mix of both theory and practice, and current issues will be emphasized. The main work of the course will require reading a number of current and classic research papers.

During the semester, you will be reading essentially 2 research papers to prepare for each class. This is more work than it sounds like! You must come to class prepared consistently; if your schedule will not permit that, you should not take the class.

A major component of the class will be a final project, which you will work on for approximately the last 2 months of the course. The hope is that this project may form the foundation of either a research paper or, for undergraduates, a senior thesis. Although you will need to obtain approval for your project choice, the topic of the final project will primarily be up to you. This project can either be theoretical or implementation based in nature. Generally people work in pairs for the final project, but this is not required.

Prerequisites

Students should have taken at least CS 124 or its equivalent. Students should be able to program in a standard programming language; C or C++ is preferred. Knowledge of probability will be extremely helpful but not required. Generally, mathematics will be fundamental to the course, so you should expect to spend time learning some additional mathematics on your own if necessary. Similarly, some knowledge of networks and network issues will be very helpful. For students wishing to review important aspects of probability, Sheldon Ross has written several excellent introductory books which are available in the library. My personal favorite is "Introduction to Probability Models." A more advanced book for those with more background is "Elements of Information Theory" by Cover and Thomas. Another good book is "Information Theory, Inference, and Learning Algorithms" by David Mackay. Of course, my completely biased opinion is that the best book for a computer scientist to buy is by Mitzenmacher and Upfal, "Randomized Algorithms and Probabilistic Analysis." I'd recommend most students get one (or more) of these books as a reference.

Assessment

Your performance will be measured in four ways. (The percentage contributions to your grade given below are approximate and subject to change.)

Problem sets (25%): There will be 3-4 short problem sets. Generally they are meant to ensure that introductory material and the major ideas are being absorbed. They will generally be due one to two weeks after they are given out. These sets will primarily be mathematical and/or theoretical in nature, although some implementation may be required. These assignments are governed by the collaboration policy, given below.
Paper summaries (10%): You will also have to regularly turn in paper summaries in a form to be discussed for papers that we read during the semester. The point of the summaries is really to ensure that you come to class prepared. You will be allowed to skip two summaries of your choice during the course of the semester. Summaries will be due before the class in which the paper is discussed.
Summaries are to be approximately 250 words (about 1 page). Longer is not better. Summaries should be typed or handwritten extremely neatly. Summaries will generally be sent in by e-mail before the corresponding class time.
Class participation (15%): You will be expected to come to class prepared to discuss the readings, and solve problems based on the reading. I will be calling on people randomly throughout the semester. At times you will have to work together in groups in class to answer questions posed.
Final Project (50%): The final project will be your major output in the course. The goal of the final project is to develop a full understanding of an important open research area, and, to the extent possible, to work on an open research problem. The final project will include a major final paper, and (depending on the class size) may also include an oral presentation.

At this time there is no intention to hold a final or midterm exam.

All assignments will be due at the beginning of class on the appropriate day. Late assignments are not acceptable without the prior consent of the instructor. Consent will generally only be given for major emergencies.

Collaboration policy

I would like to emphasize the rules on working with others on homework assignments. For problem sets, limited collaboration in planning and thinking through solutions to homework problems is allowed, but no collaboration is allowed in writing up solutions. You are allowed to work with a few other students currently taking the class in discussing, brainstorming, and verbally walking through solutions to homework problems. But when you are through talking, you must write up your solutions independently and may not check them against each other. There may be no passing of homework papers between collaborators; nor is it permissible for one person simply to tell another the answer. Paper summaries are meant to be done almost entirely on your own. Brief discussions with other students after you have all read the paper are permissible, but the paper summary should be entirely your own work.

If you collaborate with one or two other students in the course in the planning and design of solutions to homework problems, then you should give their names on your homework papers.

Under no circumstances may you use solution sets to problems that may have been distributed by the course in past years, or the homework papers of students who have taken the course past years. Nor should you look up solution sets from other similar courses.

Violation of these rules may be grounds for giving no credit for a homework paper and also for serious disciplinary action.

Required Text

Generally papers will be made available either in class or at the class Web site. No text is required.

Class Information/Notes

Class notes, homework assignments, and other information will be made available on the Web when possible. For access go to the class web site. Generally this information will be available in Postscript, so you will want to find a Postscript viewer. In many cases, the class web site may be the only location where information is posted or available, so look in from time to time!

Incomplete List of Possible Topics

The following is a list of topics from the last time the class was offered. Again, the topics may change somewhat for the coming year.

Information retrieval and the Web
- Ranking documents: PageRank, Kleinberg's algorithm
- Other uses of link information
- Link prediction
Compression
- Basics of information theory
- Huffman compression (non-adaptive, adaptive)
- Arithmetic coding
- Lempel-Ziv compression and its variants
- Burrows-Wheeler compression
- SEQUITUR
- Entropy of English
- JPEG/MPEG/Audio
Summarization algorithms
- Bloom filters and variants
- Data streams and streaming algorithms
- Similarity metrics and toolkits
Coding
- Basics of Shannon
- Reed-Solomon codes
- LDPC codes and Belief Propagation
- Network coding and gossiping
- Forward Error Correction in practice