Hypersearching the Web: Or How Algebra and Probability can help you surf better September 11-15, 2000

Lecturer:

Devdatt Dubhashi, room 2450, extension 1046.

Room: S4

All that Jazz

Is this really a course about IT and all that jazz, and if so, what's it doing here amidst the serious Ph.D. stuff, you ask incredulously. Well, the answer is yes and no. The main aim of the course is to get you interested in algorithms and specifically, some elegant, powerful and versatile mathematical techniques that are useful in algorithm design and analysis. The two techniques we will focus on are

Randomization, in particular Markov chains and sampling .
Linear algebra, in particular, the singular value decomposition .

Web surfing, which is everyone's favourite pastime, will be used as a test bed for these techniques. The aim will be to convince you that in such real life scenarios, dramatic and substantial progress is made not by hacking but by bringing to bear "serious" theoretical computer science and mathematical techniques on the issues at hand.

Time Schedule

	Monday	Tuesday	Wednesday	Thursday	Friday
10 -- 12	Lecture 1	Lecture 2	Lecture 3	Koen's talk	Lecture 5
14 -- 15				Lecture 4
15 -- 16	Discussion	Discussion	Discussion	Lecture 4	Discussion

Plan

Lecture 1: Problems of web surfing. GOOGLE and CLEVER.
Lecture 2: Markov chains and random walks.
Lecture 3: More on Markov chains and SALSA. Singular Value Decomposition (SVD).
Lecture 4: Latent Semantic Indexing (LSI).
Lecture 5: MANJARA and Clustering.

Evaluation

What do you need to do to pass the course? At first the most attractive suggestion by far to me seemed to be Reiner's: buy me some beers! Somewhat reluctantly I've prepared a bunch of problems You need to pick one and solve it in class during the discussion session. You can sign up for a problem by picking up a free slot on the sheet on my door. So to summarise: to pass you need to attend the lectures, the discussion sessions (also Koen's talk?!) and solve one problem in class.

References and Links

HITS algorithm.
- Kleinberg's algorithm
- CLEVER project at IBM Almaden.
Google
- Google , the engine.
- The original paper.
SALSA
- Salsa .
Markov Chains
- Olle Haggstrom's notes.
- Mark Jerrum's page. See the surveys on the Markov Chain Monte Carlo method.
- Introduction to Probability a great textbook with computer demos to illustrate the concepts. There are applets to create Markov chains, find the stationary distributions ...
Latent Semantic Indexing (LSI)
- LSI web site.
- Katarina Blom's page. See her licentiate thesis at Chalmers on information retrieval using SVD and Krylov subspaces.
Manjara and clustering
- Manjara the engine.

Last modified: Wed Sep 13 09:23:13 MET DST 2000