CS 408, Graph Theory

Homework 1. Reading: Section 8.1 - 8.4 of Parallel Computation notes. Product graphs and hypercube symmetries

Homework 2. Reading: Section 8.1 - 8.4 of Parallel Computation notes. Bisection lower bounds.

Reading: Bisection lower bounds.

Homework 3.Reading: Chapter 10 except for discussion of Normal algorithms of Parallel Computation notes. Multibutterflies.

Quiz 1 solution

Homework 4. Reading: for probabilistic method., Embedding and MIS.

Tree Decomposition.

Homework 5.

Homework 6.

Midsem solution

Homework 7. Reading: Planar graphs..

Genome Assembly Notes (introductory companion to paper) . Paper..

Quiz 2.

Homework 8.

Page Rank. Google paper.

Homework 9. Spectral Graph Theory.

Makeup quiz.

Final with solutions.

Instructor: Abhiram Ranade, Office Hours: Monday 11:30-12:30, SIA 318 Kanwal Rekhi Building.

TAs: Vijay Gabale and Ashutosh Shukla.

Course content will be similar to last year. Last year's homepage with notes, homeworks and tests. Rough outline: Graph theory applied to the design of parallel computer networks. Measures such as diameter, bisection width of popular networks. Graph embedding for comparing networks. Graph embedding and partitioning for designing divide and conquer algorithms. Network flow and applications. Matchings in general graphs. Page rank algorithm for web search. Random walks on graphs with applications to graph drawing and graph partitioning.

There is no single text, unfortunately. I will try to give written notes as last year (see that page), and point to appropriate material from easily available books (e.g. Kleinberg-Tardos) when needed.

Eligibility:

CSE UG students who solve and submit Quiz 0 below. No PG students allowed.

Quiz 0 to help you decide whether to take the course

Prerequisites:

Discrete Structures CS 207, Data Structures CS 213, Linear Algebra MA 106, Data Analysis and Interpretation IC 102 (for probability theory).

Grading:

2 quizzes each 10%, Midterm: 20%, Homeworks: 10%, Final: 50%.

Homework Grading scheme

Audit requirement:

Get 8 marks out of 10 on the homeworks, see grading scheme above.

Attendance policy:

Not compulsory. But 100% attendance is strongly recommended, because there is no clear textbook, and this is likely a difficult course (see last year's offering, above). Notes will be put up, but this cannot be guaranteed, and it is your responsibility to keep up with what is covered in class as well as all announcements by attending and/or asking fellow students. You are also strongly encouraged to talk to me during office hours for solving doubts.