CS4850    Spring 2009

Mathematical Foundations for the Information Age

M W F     11:15-12:05     Thurston Hall 203

Announcements        Concepts        Exams        Homework       Course Staff        Lecture Notes       Office Hours        Useful Formulas

Announcements

Todays (April 9) office hours will be moved to 2:30-3:30 due to a conflict.  Sorry about the late notice. 

• Note room change to Thurston 203

Concepts: The course will cover mathematical foundation of modeling and searching of the WWW and other complex networks, discovering trends, data mining, and making recommendations based on user behavior. Topics will include large graphs, random structures, phase transitions, spectral methods, data in high dimensions, Chernoff bounds, generating functions, second order methods.

Exams: tbd

Homework:  Students are encouraged to work together.  The only requirement is that you understand everything you turn in.

• Homework 1 (due Jan 30)
• Homework 2 (due Feb 6)
• Homework 3 (due Feb 13)
• Homework 4 (due Feb 20)
• Homework 5 (due Feb 27)
• Homework 6 (due March 6)
• Homework 7 (due March 13)
• Homework 8 (due March 27)
• Homework 9 (due April 3)
• Homework 10 (due April 10)
• Homework 11 (due April 17)
• Homework 12 (due April 24)
• Homework 13 (due May 1)

   

• matrix of distances and names of cities

Course Staff: Prof. John Hopcroft -- jeh@cs.cornell*                         
                            *add .edu after these addresses when sending email

Lecture Notes Please let us know if you need a change, or change it in the sign-up sheet in class.  Scribe Schedule (note to scribes: please try to combine your notes together to one set of notes per class).

• Lecture 1: High Dimension
• Lecture 2: High dimesions2
• Lecture 3:  High Dimesions3 and random graphs
• Lecture 4:  Properties of random graphs
• Lecture 5:  Phase transitions, isolated vertices, second moments
• Lecture 6:  Threshold for graph connectivity and thresholds
• Lecture 7:  All increasing properties have threshold
• Lecture 8:  phase transitions
• Lecture 9: Volume of sphere in high dimensions
• Lecture 10: Distribution of component sizes in G(n,p)
• Lecture 11:  Probability distributions and directed graphs
• Lecture 12:  Molloy Reed, Branching processes
• Lecture 13:  Branching processes
• Lecture 14:  Branching process expected size and start of generating functions
• Lecture 15:  Generating function from recurrence equation and growing graphs
• Lecture 16:  Growth model
• Lecture 17:  Growing graph with preferential attachment
• Lecture 18:  Small-world phenomena
• Lecture 19:  Random walks and analogy with electrical networks
• Lecture 20:  Random walks and probabilistic interpretations of voltage and current
• Lecture 21:  Random walks and interpretation of current
• Lecture 22:  Random walk in 3-dimensions
• Lecture 23:  Random walks and hitting time
• Lecture 24:  Hitting time
• Lecture 25:  Random walks on directed graphs
• Lecture 26:  Singular Value Decomposition
• Lecture 27:  SVD
• Lecture 28:  Matrix norms and Eigenvalues
• Lecture 29:  Eigenvalues of a random graph
• Lecture 30:  Eigenvalues of a random graph
• Lecture 31:  VC dimension
• Lecture 32:  VC dimension circles and rotated squares
• Lecture 33  VC half spaces and primal shatter function
• Lecture 34  Primal shatter function
• Lecture 35:  Discrepancy
• Lecture 36:  Data streams
• Lecture 37:  Data streams
• Lecture 38:  Approximation algorithms and hidden Markov model
• Lecture 39:  Hidden Markov Models
• Lecture 40:
• Lecture 41:  Arrow's theorem
• Lecture 42:
  
  

Office Hours

• Prof. Hopcroft

  • Tuesday 1:15-2:30 pm (Upson 5144)
  • Wednesday 3:30-4:30pm (Upson 5144)
  • Thursday 1:30-2:30 (Upson 5144)
• Thursday 1:30-2:30pm (Upson 5144) may be cancelled due to lack of students

Useful Formulas

• See file