CS 222 -- Algorithms at the End of the Wire
Handouts and Class Materials
- [7/30] We'll have a Piazza page and such up before class begins.
We may use Canvas to turn in assignments.
Similarly, we'll have a link to online lectures as soon as possible.
Basic Class Information
All reading dates are tentative and will be confirmed in class.
We may go faster, we may go slower.
You should consider this a minimum of what you should be
reading for this class. Feel free to explore on the Web or otherwise
(additional suggested readings will be listed as well). We are just
touching the surface of these topics; there's much more out there.
Unit 1: Search Engines and the Importance of Links
- 9/1 Background: Review Markov chains.
- Start with
wikipedia. The first external link is to a useful book chapter
on Markov chains.
Additional useful papers for Unit 1:
- Graph Structure in the Web
by Broder et al.
- The Link Database: Fast Access to Graphs of the Web
by Randall et al.
The Eigentrust Algorithm for Reputation Management in P2P Networks
by Kamvar, Schlosser, and Garcia-Molina.
Trust-Based Recommendation Systems
by Andersen et al.
PicASHOW: Pictorial Authority Search by Hyperlinks on the Web. by Lempel
The Stochastic Approach for Link-Structure Analysis (SALSA) and the TKC Effect
by Lempel and Moran.
Power Laws, Pareto Distributions, and Zipf's Law.
by Mark Newman.
On Power-Law Relationships of the Internet Topology.
by Faloutsos, Faloutsos, and Faloutsos.
Power-Law Distributions in Empirical Data.
by Clauset, Shalizi, and Newman.
The Anatomy of the Long Tail.
by Goel, Broder, Gabrilovich, and Pang.
- Aggregating Inconsistent Information.
by Ailon, Charikar, Newman.
- Editorial: The Future of Power Law Research.
Unit 2: Compression and Basic Information Theory
- 9/15, and ongoing: We will be covering the basics of compression and
information theory, including Huffman coding, arithmetic coding, LZ-style coding, etc.
Some good online introductions to the material include:
Information Theory, Inference, and Learning Algorithms, specifically part 1 (Data Compression) of Mackay's Book. (Though the whole book is good.)
Introduction to Data Compression,
notes by Guy Blelloch.