wth modelsCS 683

Advanced Design and Analysis of Algorithms

Spring 2008 Topics: Random graphs, spectral analysis, high dimensional data, search engines

**
Overview
**

The course will focus on topics in information capture and access such as large graphs, spectral analysis, clustering, and efficient algorithms for extremely large problems.

## InstructorJohn Hopcroft5144 Upson Phone: 255-1179 |
## Time and PlaceMWF 2:30-3:20 |
## Office HoursTBD |

Prerequisites

There will be a project that can either be done individually or in a small group. The course is intended for PhD students but is open to any student with CS482 as a prerequisite.

Announcements

**Potential homework and projects**

Threshold for graph connectivity

Differential equations with random variables

**Lecture notes** List of note takers

Lecture 1 Lecture1 alternative

Lecture2.pdf Lecture2.tex stepfuction

Lecture 3 second moments

Lecture 9 Generating functions

Lecture 17 Feb 27 Random walks

Lecture 20 Random walks on graphs

Lecture March 7 effective resistance

Lecture 26 March 26 Catalan Number and overview of Wigner

Lecture 27 March 28 Power Law Graphs

Lecture 28 April 2 Arrow's Theorem

Lecture 29 April 4 Arrow's Theorem

Lecture 30 April 7 High dimensions

Lecture 3/31 Eigenvalues of graphs

Lecture 32 4/9 High dimensions and large data sets

Lecture 4/14 data streams part 2

Lecture 4/25 Belief propagation and VC dimension

Lecture 4/28 VC-dimension part 1

Lecture 32 Data Streams Apr 11

Lecture 34 Data Streams Apr 16

Lecture 35 4/18/08 Low memory approximations

Lecture 4/21/08 Part 2 Belief propagation

**References**

Nicholas C. Wormald, “Differential Equations for Random Processes and Random Graphs” Ann Appl Probab Vol5 Number 4 (1995) 1217-1235.

Reference may prove that you can write differential equations with expected values and get the correct answer.