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.

- Load balancing in content delivery networks
(ps 4up,
pdf 4up)

Slides by Michael Gomans. - Indexing and Searching 1 and 1/2 of 2
(ps 4up,
pdf 4up)

**Introduction:**model, query types, common techniques

**Indices:**posting lists, compression, storing the lexicon, union/intersection - Indexing and searching other half of 2
(ps 4up,
pdf 4up)

**Vector Models** - Indexing and searching 3
(ps 4up,
pdf 4up)

**Link Analysis:**Google's pagerank, Hubs and Authorities

**Near Duplicate Removal:**Minwise independent hash functions

- Linear/Integer Programming 1
(ps 4up,
pdf 4up)

**Introduction:**formulations, integer vs linear programming, max-flow as a linear program

**Simplex method:**geometric view, Tableau solution

**Duality:**Dual formulation and duality theorem - Linear/Integer Programming 2
(ps 4up,
pdf 4up)

**Ellipsoid Method**

**Interior Point Methods**

- Linear/Integer Programming 3 + 4
(ps 4up,
pdf 4up)

**Introduction to Integer Programming**

**Reductions:**Knapsack, Travelling salesman, set-cover

**Algorithms:**Rounding, branch-and-bound, cutting planes

- Linear/Integer Programming 5
(ps 4up,
pdf 4up)

**Airline Crew Scheduling**

- Separators 1 and 2
(ps 4up,
pdf 4up)

**Introduction:**edge vs vertex separators, separator trees, balance criteria, applications, separator theorems

**Kernighan-Lin:**algorithm and variants

**Multilevel Partitioning:**algorithm and variants

**Spectral Partitioning:**algorithm and variants

- Separators 3
(ps 4up,
pdf 4up)

Planar separators. - Separators 5 (Nested Dissection)
(pdf)

- Error Correcting Codes 1
(ps 4up,
pdf 4up)

**Introduction:**block codes, systematic codes

**Hamming Codes:**construction, lower bounds

**Linear Codes:**generator/parity check matrices, reed-muller codes - Error Correcting Codes 2
(ps 4up,
pdf 4up)

**Reed Solomon Codes:**construction, as cyclic codes, systematic version

**Cyclic Codes:**generator/parity check polynomials, hamming codes revisited - Error Correcting Codes 3
(ps 4up,
pdf 4up)

**Expander graphs and Tornado Codes**

- Cryptography A-Z : an online resource courtesy of SSH.
- Introduction to Cryptography (30 pages). This is still in rough shape, and here are some bug fixes.
- AES Proposal: Rijndael.

- Cryptography 1 and 2
(
ppt,
ps,
pdf
)

**Introduction:**one-way functions, basic protocols

**Number theory:**groups, fields, Galois fields

**Private key cryptosystems:**Block Ciphers, Rijdael

- Cryptography 3, 4 and 5
(
ppt,
ps,
pdf
)

**Public key cryptosystems:**Diffie-Hellman, Merkle-Hellman, RSA, ElGamal

**Applications:**Kerberos, electronic cash

- Introduction (ps 4up)

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

Guy Blelloch, guyb@cs.cmu.edu.