CS 408, Graph Theory, Spring 2022

Instructor: Abhiram Ranade

Approximate topic list: Graphs in parallel computer design. Properties of multidimensional arrays, hypercubes, butterfly, shuffle exchange, deBruijn etc. Flows, planar graphs and planar separators. Randomness in expander construction, elementary results related to Ramsey numbers. Spectral graph theory. Relation to page rank, graph partitioning, graph drawing, random walks.

An earlier offering (somewhat similar).

Lectures and assessment

Lectures uploaded on MSTeams for each week by Monday.

Doubt clearing session: Thursday 9:30-10:30

Approximately Biweekly Quizzes: Monday 11:30-12:30

Reading material

Graphs in parallel computer design.

Eligibility:

Third, fourth, fifth year UG students who like proofs, counting, mathematical induction, linear algebra, probability theory. The course will use concepts covered in CS 207 Discrete Structures, CS 213 Data Structures and Algorithms, and CS 218 Design and Analysis of Algorithms. These are not prerequisites but be prepared to work harder if you encounter something you do not know.

No PG students allowed.

Audit: Not allowed.

Lecture 1:

Video 1 Video 2 Slides