HONR 278J Under the Hood: Algorithms and their Applications
Tuesday/Thursday, 3:30-4:45 p.m.
Dr. Samir Khuller, Department of Computer Science
Ever wondered, how does google do such a remarkable job as a search engine? How does mapquest give directions? How do we compress large amounts of data? How do we sequence DNA using computers? How do companies mine data and learn about you?
The main point of this course is to study a few topics, and to explore the algorithmic methods and technology behind these methods. To reach the point of being able to understand some of these applications, we will first review the history of algorithms, study many diverse (and easy to understand) algorithms. Finally, we will pick a few topics and study the required graph theory and algorithmic tools required to understand the principles behind these software tools and packages.
Topics (not a comprehensive list as yet).
Algorithms in general
Simple examples of algorithms–sorting, searching, art gallery problems,
gcd, primality testing, stable marriages, online algorithms, scheduling
Searching the web: link analysis/page rank, etc.
Mapquest: shortest paths and GIS’s
DNA sequencing: the success of Celera
Data Mining
Main Reading:
David Harel, Algorithmics: The Spirit of Computing
There will also be a few assigned readings from papers, books and the Internet. Notes will be developed by the class and made available on the class page after the lecture.
CORE: Math and Formal Reasoning [MS]
