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