Course Information
Instructor: Gary Miller
(Office Hours:
Monday 1-2PM and Thursday 3-4PM )
Place/Time: GHC 4211, TT 1:30 - 2:50pm.
Teaching Assistants: Volunteers welcome
Course Secretary: Amy Williams, GHC 8122
Official Course Blog will be:
cmu-spectral-graph-theory.blogspot.com
Announcing the Official Course Blog!
Future announcements, homework hints and clarifications, etc. will be posted on the course blog. We encourage you to participate in this blog.
If you use an RSS reader, you probably want to subscribe to our feed (link at the bottom of the blog page).
Announcements
- The last two classes will be held in GHC 4303, see schedule.
- Welcome to Spectral Graph Theory. Please take a
minute to review the course policies.
Overview
This class will cover material from three areas: Spectral Graph Theory,
Numerical Linear Algebra, and the application to problem in CS.
The central issue in spectral graph theory is understanding, estimating, and finding
eigenvectors and eigenvalues of graphs. The study of random walks on a graph was
one of the first users of spectral graph
theory. Answering such questions as: How many times should you shuffle a deck of cards
to insure that the deck is "well shuffled"? More recent application include Google's page rank
algorithm which performs a random walk on the hyperlink graph of the Internet.
It has also been applied to the problem of finding these eigenvectors as well as solving
related linear systems.