A BRICS Mini-Course
May 9, 10, 14 and 15, 2001
Lectures by
Devdatt Dubhashi, dubhashi@cs.chalmers.se
Computing Science, Chalmers University of Technology and Göteborg University
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
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.
Roughly, the first half of each lecture will be quite non-technical, and the second half fairly technical.
Why do you prefer Google to other search engines? Because it ranks the results better! (So if you don't use it, you should! Disclaimer; I'm not employed by Google!) How does Google do it? By taking a random walk!
A British web page might talk of a "lift" while an American one is likely to talk of an "elevator", when referring to the same thing. How can we extract the hidden "latent semantic" information out of the text on a page?
The query "Java" is likely to return pages for programming language, the Indonesian island and the coffee of the same name. How can one automatically form clusters corresponding to these?
When you go to Amazon.com to buy a book, they provide you a list of recommendations. Sometimes they really snare you! How do they do it?