21-366: Random Structures and Algorithms, Fall 2024

Monday, Wednesday, Friday, 11:00am -- 11:50am, WEH7201:
Office hours: Tuesday, Thursday 2:00pm -- 3:00pm, WEH6204.



We will follow the book
Introduction to Random Graphs: Hard Copy.
                                                     Digital Copy
Alan Frieze and Michal Karonski.


Old Notes, in addition to the book.


We study various models of a random graph i.e. a graph drawn from some probability distribution.
It is an interesting fact that in many cases we can predict with high probability (w.h.p.), what the values of
various parameters are.

For example, if G=G_n,m denotes a graph chosen uniformly at random from all graphs with vertex set [n]
and m edges, then if m=n^3/2log n, then w.h.p. G has diameter two.

We will discuss many such properties. We will endeavor to cover the following:

Chapter 1:   Random graph models.
Chapter 2:   Evolution of a random graph.
Chapter 3:   The degree sequence.
Chapter 4.   Connectivity.
Chapter 5.   Small sub-graphs.
Chapter 6.   Spanning sub-graphs.
Chapter 7.   Extreme characteristics.
Chapter 10. Fixed degree sequence.
Chapter 11. Intersection Graphs.
Chapter 12. Digraphs.
Chapter 17. Real world networks.
Chapter 18. Weighted graphs.

We will also study the average case performance of algorithms. In particular, algorithms that run in polynomial time and solve NP-hard problems w.h.p.

Grading: There will be weekly homeworks and three in-class tests.
               Homework: 25%
               Tests:          75%

Test dates: October 4.
                  November 13.
                  Last day of classes.

Tests: in class 50 minutes.

A:  >=80%

B:  >=70%

C:  >=60%


Homework.

Book: the red text indicates what has been covered so far.

Old Tests