15-853: Algorithms in the Real World (Guy Blelloch and Bruce Maggs, Fall 02)

#
Readings, Notes and Slides

Note that we will not have slides from all the lectures. Some lectures will
be given on the board, and some slides will be hand done.
### Error Correcting Codes

#### Readings

#### Slides

- Error Correcting Codes 1: Linear Codes
(ppt
)
- Error Correcting Codes 2: Reed-Solomon Codes, Cyclic Codes
(ppt
)

### Graph Separators

#### Readings

Scribe notes:
Lecture 1, by Barbara Anthony (in ps)
Lecture 2, by Flavio Lerda (in pdf
or ps).
Lecture 3, by Ryan Williams (in pdf
or ps).
Lecture 4, by Hubert Chan (in ps).
A Fast And High Quality Multilevel Scheme For Partitioning Irregular Graphs.
George Karypis, Vipin Kumar
R.J. Lipton, D.J. Rose, and R.E. Tarjan.

Generalized Nested Dissection.

SIAM J. Numer. Anal., 16 (1979), 346--358.

(As far as I can tell, this is not available online.)
(Optional) Nested Dissection: A Survey and comparison of various nested dissection algorithms,
Khaira, Miller and Sheffler.
(Optional)
Spectral Partitioning Works: Planar graphs and finite element meshes,
Daniel Spielman and Shang-Hua Teng. In addition to proving properties
about spectral partitioning, this gives a very good history of spectral
partitioners and overview of the technique.
(Optional)
Compact Representations of Separable Graphs (Draft)
D. Blandford, G. Blelloch, and I. Kash.
Describes a version of the graph compression application of separators
discussed in class.
(Optional) Improving The Run Time And Quality Of Nested Dissection Ordering.
Bruce Hendrickson and Edward Rothberg. (Describes a multilevel vertex
separator.)
### Logistics

#### Readings

Scribe notes:
Lecture 1, by Krithika Venkataramani (DRAFT in ps)
Lecture 2, by Zhong Xiu (DRAFT in ps
or pdf)
Slides from a talk on Approximation Algorithms for Buy-at-bulk Network Design by R. Ravi. This talk covers much of what was covered in class.
The following two papers are also relevant:
On the Integrality Gap of a Natural Formulation of the Single-Sing Buy-at-bulk Network Design Problem (2001) and
Single-sing Buy-at-bulk LP had Constant Integrality Gap (2002).
Adam Meyerson's paper on Buy At Bulk. This pretty much covers the lecture of October 23.
### Content Delivery Networks

#### Readings

Paper on
"Consistent hashing and random trees: distributed caching protocols for
relieving hot spots on the World Wide Web", by Karger et. al.
#### Slides

- Content Delivery Networks 1: Static Content
(ppt)
- Content Delivery Networks 2: Streaming Content
(ppt)
- Content Delivery Networks 3: Tunneling
(ppt)

### Indexing and Searching

#### Readings

Chapters 3 and 4 from:
Ian H. Witten, Alistair Moffat, and Timothy C. Bell.
*Managing Gigabytes: Compressing and Indexing Documents and
Images*.

Only available in hardcopy. Handed out in class, and
available outside of Wean 7116.
Michael W. Berry, Zlatko Drmac, Elizabeth R. Jessup.
Matrices, Vector Spaces, and Information Retrieval.
SIAM Review, 41(2), 1999.
Jon M. Kleinberg,
Authoritative sources in a hyperlinked environment JACM, 1999.
The following two are for the lecture on Novermber 25.
Andrei Z. Broder, Steven C. Glassman, Mark S. Manasse, Geoffrey Zweig,
Syntactic Clustering of the Web,
SRC Technical Note 1997-015, July 25, 1997

Mostly discusses the systems aspects.
Andrei Broder, Moses Charikar, Alan Frieze, and Michael Mitzenmacher. Min-wise independent permutations.
In Proceedings of the 30th Annual
ACM Symposium on Theory of Computing, pages 327-336, May 1998.

Discusses the theory behind it.
#### Scribe Notes

#### Slides

- Indexing and Searching 1 (ps
and pdf)
- Indexing and Searching 2 (ps)

Back to the Algorithms in the Real World page (V. 2002).

Guy Blelloch,
guyb@cs.cmu.edu.