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. 

Instructor John Hopcroft 5144 Upson Phone: 255-1179

Time and Place MWF 2:30-3:20

Office Hours TBD

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

    Random graphs homework

    Phase transitions homework

    Threshold for graph connectivity

    Giant component and the gap

    Directed graphs

    Differential equations with random variables

    Preferential attachment

    mileage between cities

Lecture notes    List of note takers

    Lecture 1       Lecture1 alternative

    Lecture2.pdf    Lecture2.tex    stepfuction

    Lecture 3     second moments

    Lecture 4

    Lecture 5

    Lecture 6

    Lecture 7

    Lecture 8

    Lecture 9    Generating functions

    Lecture 10    Bayesian Networks

    Lecture 11     Bayesian Networks

    Lecture 12      Branching process

    derivation of equation for g

    Lecture 13 Growth models

    Feb 20 Part 1    Feb 20 Part 2

    Lecture 15 Feb 22

    Lecture 16 Feb 25

    Lecture 17 Feb 27 Random walks

    Lecture 20 Random walks on graphs

    Lecture March 7 effective resistance

    Lecture 22

    Lecture 23 3/12

Lecture 24 3/14/08

Lecture 25 March 24 Wigner

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

Belief propagation and VC Dimension

Lecture 41 VC dimension

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.