CS6100 - Topics in Design and Analysis of Algorithms

Meetings  

• Theme 1 : Flows and Cuts in graphs - 16 meetings

  • Meeting 01 : Mon, Jan 09, 11:00 am-11:50 am

  Introduction to course contents, administrative announcements, TA introduction. <br> Max Flow problem definition, Min-cost Max flow problem definition.

  References
  Exercises
  Reading

  Introduction to course contents, administrative announcements, TA introduction.
  Max Flow problem definition, Min-cost Max flow problem definition.
  

  References:

  None

  • Meeting 02 : Tue, Jan 10, 10:00 am-10:50 am

  Reductions as algorithms. Single source single sink shortest path in directed graphs to Min-cost max flow problem. Max Flow to Min-cost max flow problem. What does it involve to show that the reduction is correct?

  References	Chapter 26 CLRS.
  Exercises
  Reading

  Reductions as algorithms. Single source single sink shortest path in directed graphs to Min-cost max flow problem. Max Flow to Min-cost max flow problem. What does it involve to show that the reduction is correct?
  

  References:

  Chapter 26 CLRS.

  • Meeting 03 : Wed, Jan 11, 09:00 am-09:50 am

  Ford Fulkerson Method, Augmenting path, Defining a residual network, Modifying the flow. Proving that the new flow is a valid flow in the original network.

  References	Section 26.2 CLRS
  Exercises
  Reading

  Ford Fulkerson Method, Augmenting path, Defining a residual network, Modifying the flow. Proving that the new flow is a valid flow in the original network.
  

  References:

  Section 26.2 CLRS

  • Meeting 04 : Thu, Jan 12, 12:00 pm-12:50 pm

  Cuts in a graph, Capacity of a cut, Flow across a cut, Max-Flow Min-Cut theorem. Proof that output of FF algorithm is a max-flow. Running time of the FF algorithm. Towards a strongly polytime algorithm.

  References	Section 26.2 CLRS
  Exercises
  Reading

  Cuts in a graph, Capacity of a cut, Flow across a cut, Max-Flow Min-Cut theorem. Proof that output of FF algorithm is a max-flow. Running time of the FF algorithm. Towards a strongly polytime algorithm.
  

  References:

  Section 26.2 CLRS

  • Meeting 05 : Mon, Jan 16, 11:00 am-11:50 am

  Dinitz Algorithm for Max-Flow. Definition of a layered network, Definition of a blocking flow. Overall algorithm with an example.

  References
  Exercises
  Reading

  Dinitz Algorithm for Max-Flow. Definition of a layered network, Definition of a blocking flow. Overall algorithm with an example.
  

  References:

  None

  • Meeting 06 : Tue, Jan 17, 10:00 am-10:50 am

  Dinitz algorithm continued. Computing a blocking flow in the layered network. Analysis of time complexity. <br> Proof that the distance from the source to the target strictly increases across phases of the algorithm.

  References	http://www.cse.iitm.ac.in/~meghana/CS6100/ref/Dinitz_alg.pdf
  Exercises
  Reading

  Dinitz algorithm continued. Computing a blocking flow in the layered network. Analysis of time complexity.
  Proof that the distance from the source to the target strictly increases across phases of the algorithm.
  

  References:

  http://www.cse.iitm.ac.in/~meghana/CS6100/ref/Dinitz_alg.pdf

  • Meeting 07 : Wed, Jan 18, 09:00 am-09:50 am

  Push-Relabel Algorithm. The overall intuition, invariants of the algorithm, contrast with algorithms based on augmenting paths. Illustration with an example.

  References	CLRS.
  Exercises
  Reading

  Push-Relabel Algorithm. The overall intuition, invariants of the algorithm, contrast with algorithms based on augmenting paths. Illustration with an example.
  

  References:

  CLRS.

  • Meeting 08 : Thu, Jan 19, 12:00 pm-12:50 pm

  Push Relabel continued. Height function, invariants. <br> Does the algorithm terminate? <br> Do we ever have an s-t path in the residual network<br> What is the largest height that a vertex can achieve?<br> Bound on number of relabels and number of saturating pushes.

  References	CLRS
  Exercises
  Reading

  Push Relabel continued. Height function, invariants.
  Does the algorithm terminate?
  Do we ever have an s-t path in the residual network
  What is the largest height that a vertex can achieve?
  Bound on number of relabels and number of saturating pushes.
  

  References:

  CLRS

  • Meeting 09 : Mon, Jan 23, 11:00 am-11:50 am

  Analysis of Push Relabel continued. Bounding the number of relabels, saturating and non-saturating pushes. Discussion on implementing push relabel. An O(n^2m) time algorithm for max-flow. <br> A small modification to the algorithm. Improving the bound on number of non-saturating pushes. An O(n^3) time algorithm for max-flow.

  References	CLRS and see lecture notes from Prof. Roughgarden (Stanford) http://www.cse.iitm.ac.in/~meghana/CS6100/ref/Push-Relabel-Roughgarden-Stanford.pdf
  Exercises
  Reading

  Analysis of Push Relabel continued. Bounding the number of relabels, saturating and non-saturating pushes. Discussion on implementing push relabel. An O(n^2m) time algorithm for max-flow.
  A small modification to the algorithm. Improving the bound on number of non-saturating pushes. An O(n^3) time algorithm for max-flow.
  

  References:

  CLRS and see lecture notes from Prof. Roughgarden (Stanford) http://www.cse.iitm.ac.in/~meghana/CS6100/ref/Push-Relabel-Roughgarden-Stanford.pdf

  • Meeting 10 : Tue, Jan 24, 10:00 am-10:50 am

  Quick Recap of reduction from Bipartite Matching to max-flow problem. Halls Theorem and its proof via max-flow min-cut theorem.

  References
  Exercises
  Reading

  Quick Recap of reduction from Bipartite Matching to max-flow problem. Halls Theorem and its proof via max-flow min-cut theorem.
  

  References:

  None

  • Meeting 11 : Wed, Jan 25, 09:00 am-09:50 am

  Cuts in Graph. Min-cut vs min-s-t cut. Finding min-cut using flow based algorithm. A simple algorithm using O(n^2) max-flow computations. Improving this algorithm to an algorithm that requires O(n) max-flow computations.

  References
  Exercises
  Reading

  Cuts in Graph. Min-cut vs min-s-t cut. Finding min-cut using flow based algorithm. A simple algorithm using O(n^2) max-flow computations. Improving this algorithm to an algorithm that requires O(n) max-flow computations.
  

  References:

  None

  • Meeting 12 : Thu, Jan 26, 12:00 pm-12:50 pm

  Republic Day Holiday.

  References
  Exercises
  Reading

  Republic Day Holiday.
  

  References:

  None

  • Meeting 13 : Mon, Jan 30, 11:00 am-11:50 am

  Min-cut in an undirected graph. Karger's randomized min-cut algorithm. Simple algorithm and its analysis to bound the error probability.

  References	Randomized Algorithms by Motwani and Raghavan. Chapter 10.
  Exercises
  Reading

  Min-cut in an undirected graph. Karger's randomized min-cut algorithm. Simple algorithm and its analysis to bound the error probability.
  

  References:

  Randomized Algorithms by Motwani and Raghavan. Chapter 10.

  • Meeting 14 : Tue, Jan 31, 10:00 am-10:50 am

  Fast MinCut algorithm. Start with n vertices and repeatedly contract till we reach roughly n/sqrt(2) vertices. Recurse on the graph obtained. Repeat this procedure twice.

  References	Randomized Algorithms, Motowani Raghavan (Chapter 10)
  Exercises
  Reading

  Fast MinCut algorithm. Start with n vertices and repeatedly contract till we reach roughly n/sqrt(2) vertices. Recurse on the graph obtained. Repeat this procedure twice.
  

  References:

  Randomized Algorithms, Motowani Raghavan (Chapter 10)

  • Meeting 15 : Wed, Feb 01, 09:00 am-09:50 am

  Analysis of Fast MinCut. Bounding the error probability. Running time of the algorithm. <br> Bound on total number of min-cuts in a graph. A simple example achieving the bound.

  References	Chapter 10, Motwani and Raghavan.
  Exercises
  Reading

  Analysis of Fast MinCut. Bounding the error probability. Running time of the algorithm.
  Bound on total number of min-cuts in a graph. A simple example achieving the bound.
  

  References:

  Chapter 10, Motwani and Raghavan.

  • Meeting 16 : Thu, Feb 02, 12:00 pm-12:50 pm

  Problem Solving session.

  References
  Exercises
  Reading

  Problem Solving session.
  

  References:

  None

• Theme 2 : Matching in graphs - 20 meetings

  • Meeting 17 : Mon, Feb 06, 11:00 am-11:50 am

  Matchings, introduction, definitions of alternating paths, augmenting paths, examples. Berge's theorem statement.

  References	Chapter 10, Combinatorial Optimization by Papadimirtou and Steiglitz
  Exercises
  Reading

  Matchings, introduction, definitions of alternating paths, augmenting paths, examples. Berge's theorem statement.
  

  References:

  Chapter 10, Combinatorial Optimization by Papadimirtou and Steiglitz

  • Meeting 18 : Tue, Feb 07, 10:00 am-10:50 am

  Symmetric Difference of two matchings. Using that to prove Berge's theorem. A template Algorithm for computing maximum cardinality matching in general graphs. <br> Special case of bipartite graphs. Dinic's like algorithm.

  References	Chapter 10, Combinatorial Optimization, Papadimitriou and Steiglitz.
  Exercises
  Reading

  Symmetric Difference of two matchings. Using that to prove Berge's theorem. A template Algorithm for computing maximum cardinality matching in general graphs.
  Special case of bipartite graphs. Dinic's like algorithm.
  

  References:

  Chapter 10, Combinatorial Optimization, Papadimitriou and Steiglitz.

  • Meeting 19 : Wed, Feb 08, 09:00 am-09:50 am

  Notion of maximal vertex disjoint shortest augmenting paths. Invariants after we augment along these paths. Hopcroft Karp Algorithm with analysis of O(msqrt{n}) time.

  References	Earlier reference as well as Chapter 3 from Introduction to Graph Theory Douglas B West.
  Exercises
  Reading

  Notion of maximal vertex disjoint shortest augmenting paths. Invariants after we augment along these paths. Hopcroft Karp Algorithm with analysis of O(msqrt{n}) time.
  

  References:

  Earlier reference as well as Chapter 3 from Introduction to Graph Theory Douglas B West.

  • Meeting 20 : Thu, Feb 09, 12:00 pm-12:50 pm

  Weighted Matchings in Graphs. Formulating it as an LP. Formulating VC, Max-Flow as an LP. Dual of an LP. How to form a dual. Why is the dual useful?

  References	Chapter on LPs in CLRS.
  Exercises
  Reading

  Weighted Matchings in Graphs. Formulating it as an LP. Formulating VC, Max-Flow as an LP. Dual of an LP. How to form a dual. Why is the dual useful?
  

  References:

  Chapter on LPs in CLRS.

  • Meeting 21 : Mon, Feb 13, 11:00 am-11:50 am

  Primal Dual Algorithm for Max-weight matching in a bipartite graph. Equality Subgraph. Modifying the Dual.

  References
  Exercises
  Reading

  Primal Dual Algorithm for Max-weight matching in a bipartite graph. Equality Subgraph. Modifying the Dual.
  

  References:

  None

  • Meeting 22 : Tue, Feb 14, 10:00 am-10:50 am

  Max-Weight Primal Dual algo continued. Definition of a labeling function. Finding a vertex cover in the equality subgraph. Which edges are having excess? How to modify Duals.

  References
  Exercises
  Reading

  Max-Weight Primal Dual algo continued. Definition of a labeling function. Finding a vertex cover in the equality subgraph. Which edges are having excess? How to modify Duals.
  

  References:

  None

  • Meeting 23 : Wed, Feb 15, 09:00 am-09:50 am

  Running time analysis. O(n^4) running time algorithm.

  References
  Exercises
  Reading

  Running time analysis. O(n^4) running time algorithm.
  

  References:

  None

  • Meeting 24 : Thu, Feb 16, 12:00 pm-12:50 pm

  Dulmage Mendelsohn Decomposition Theorem for bipartite graphs. Brief description of application to rank maximal matchings.

  References
  Exercises
  Reading

  Dulmage Mendelsohn Decomposition Theorem for bipartite graphs. Brief description of application to rank maximal matchings.
  

  References:

  None

  • Meeting 25 : Mon, Feb 20, 11:00 am-11:50 am

  Non Bipartite Matchings. Edmonds algorithm. Definition of a blossom. Why is the definition useful?

  References
  Exercises
  Reading

  Non Bipartite Matchings. Edmonds algorithm. Definition of a blossom. Why is the definition useful?
  

  References:

  None

  • Meeting 26 : Tue, Feb 21, 10:00 am-10:50 am

  Edmonds Blossom Shrinking Lemma with proof. How do we find blossoms? How many times do we need to "explore" a vertex to search for augmenting paths?

  References
  Exercises
  Reading

  Edmonds Blossom Shrinking Lemma with proof. How do we find blossoms? How many times do we need to "explore" a vertex to search for augmenting paths?
  

  References:

  None

  • Meeting 27 : Wed, Feb 22, 09:00 am-09:50 am

  Edmonds Algorithm description. Labeling vertices odd and even. How to detect a blossom (even, even edge)?

  References
  Exercises
  Reading

  Edmonds Algorithm description. Labeling vertices odd and even. How to detect a blossom (even, even edge)?
  

  References:

  None

  • Meeting 28 : Thu, Feb 23, 12:00 pm-12:50 pm

  Edmonds algorithm revisited. Assignment 1 solutions discussed.

  References
  Exercises
  Reading

  Edmonds algorithm revisited. Assignment 1 solutions discussed.
  

  References:

  None

  • Meeting 29 : Mon, Feb 27, 11:00 am-11:50 am

  Discussion of MidSem solutions. <br>

  References
  Exercises
  Reading

  Discussion of MidSem solutions.
  
  

  References:

  None

  • Meeting 30 : Tue, Feb 28, 10:00 am-10:50 am

  Tutte's theorem (non-biparitite equivalent of Halls theorem). Definition of a Good Set and Bad Set. Edge maximal graph.

  References
  Exercises
  Reading

  Tutte's theorem (non-biparitite equivalent of Halls theorem). Definition of a Good Set and Bad Set. Edge maximal graph.
  

  References:

  None

  • Meeting 31 : Wed, Mar 01, 09:00 am-09:50 am

  Proof of Tutte's theorem continued.

  References
  Exercises
  Reading

  Proof of Tutte's theorem continued.
  

  References:

  None

  • Meeting 32 : Thu, Mar 02, 12:00 pm-12:50 pm

  Tutte Berge Formula with its proof.<br> Deriving Hall's Theorem from Tutte's theorem.

  References
  Exercises
  Reading

  Tutte Berge Formula with its proof.
  Deriving Hall's Theorem from Tutte's theorem.
  

  References:

  None

  • Meeting 33 : Mon, Mar 06, 11:00 am-11:50 am

  Gallai Edmonds Decomposition theorem.

  References
  Exercises
  Reading

  Gallai Edmonds Decomposition theorem.
  

  References:

  None

  • Meeting 34 : Tue, Mar 07, 10:00 am-10:50 am

  Proof of Gallai Edmond's decomposition theorem. <br> LP for Bipartite matching revisited. Proof that the extreme points of this LP are integral. The natural LP for non-bipartite matchings is not integral.

  References
  Exercises
  Reading

  Proof of Gallai Edmond's decomposition theorem.
  LP for Bipartite matching revisited. Proof that the extreme points of this LP are integral. The natural LP for non-bipartite matchings is not integral.
  

  References:

  None

  • Meeting 35 : Wed, Mar 08, 09:00 am-09:50 am

  Perfect Matching LP for general graphs. Proof that the LP is 1/2 integeral. <br> The odd-set constraints. After adding these constraints the LP has integral extreme points.

  References
  Exercises
  Reading

  Perfect Matching LP for general graphs. Proof that the LP is 1/2 integeral.
  The odd-set constraints. After adding these constraints the LP has integral extreme points.
  

  References:

  None

  • Meeting 36 : Thu, Mar 09, 12:00 pm-12:50 pm

  Proof of Integrality of the perfect matching polytopes in general graphs (continued from previous class).

  References
  Exercises
  Reading

  Proof of Integrality of the perfect matching polytopes in general graphs (continued from previous class).
  

  References:

  None

• Theme 3 : Data structures and algorithms for Dynamic graphs - 12 meetings

  • Meeting 37 : Mon, Apr 03, 11:00 am-11:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 38 : Tue, Apr 04, 10:00 am-10:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 39 : Wed, Apr 05, 09:00 am-09:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 40 : Thu, Apr 06, 12:00 pm-12:50 pm

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 41 : Mon, Apr 10, 11:00 am-11:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 42 : Tue, Apr 11, 10:00 am-10:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 43 : Wed, Apr 12, 09:00 am-09:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 44 : Thu, Apr 13, 12:00 pm-12:50 pm

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 45 : Mon, Apr 17, 11:00 am-11:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 46 : Tue, Apr 18, 10:00 am-10:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 47 : Wed, Apr 19, 09:00 am-09:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 48 : Thu, Apr 20, 12:00 pm-12:50 pm

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

• Theme 4 : Matchings under preferences - 12 meetings

  • Meeting 49 : Mon, Mar 13, 11:00 am-11:50 am

  Holi Non Instructional Day.

  References
  Exercises
  Reading

  Holi Non Instructional Day.
  

  References:

  None

  • Meeting 50 : Tue, Mar 14, 10:00 am-10:50 am

  Stable marriage problem. Introduction, Gale and Shapley (GS) Algorithm. Proof that GS algorithm outputs a stable matching.

  References	Lecture notes on homepage. <br> Stable Marriage Structure and Algorithms. (by Irving and Gusfield).
  Exercises
  Reading

  Stable marriage problem. Introduction, Gale and Shapley (GS) Algorithm. Proof that GS algorithm outputs a stable matching.
  

  References:

  Lecture notes on homepage. Stable Marriage Structure and Algorithms. (by Irving and Gusfield).

  • Meeting 51 : Wed, Mar 15, 09:00 am-09:50 am

  Every execution of the GS algorithm outputs the same stable matching. Proof of the same.<br> Variants of the stable matchings, incomplete lists, ties.

  References
  Exercises
  Reading

  Every execution of the GS algorithm outputs the same stable matching. Proof of the same.
  Variants of the stable matchings, incomplete lists, ties.
  

  References:

  None

  • Meeting 52 : Thu, Mar 16, 12:00 pm-12:50 pm

  The case of strict and incomplete lists. Stable matchings exist. All stable matchings match the same set of vertices in A and B. Thus all stable matchings have the same size.

  References
  Exercises
  Reading

  The case of strict and incomplete lists. Stable matchings exist. All stable matchings match the same set of vertices in A and B. Thus all stable matchings have the same size.
  

  References:

  None

  • Meeting 53 : Mon, Mar 20, 11:00 am-11:50 am

  Kiraly's approximation algorithm. Intuition of giving 2 chances to an unmatched participant.

  References	Paper by Z. Kiraly (available on homepage).
  Exercises
  Reading

  Kiraly's approximation algorithm. Intuition of giving 2 chances to an unmatched participant.
  

  References:

  Paper by Z. Kiraly (available on homepage).

  • Meeting 54 : Tue, Mar 21, 10:00 am-10:50 am

  A 3/2 approximation algo for the simple case of max. cardinality weakly stable matching with ties only on one side.

  References
  Exercises
  Reading

  A 3/2 approximation algo for the simple case of max. cardinality weakly stable matching with ties only on one side.
  

  References:

  None

  • Meeting 55 : Wed, Mar 22, 09:00 am-09:50 am

  Stable matchings with ties on both sides and incomplete lists. Approximation to max. card. weakly stable matching. A 5/3 approximation algorithm.

  References
  Exercises
  Reading

  Stable matchings with ties on both sides and incomplete lists. Approximation to max. card. weakly stable matching. A 5/3 approximation algorithm.
  

  References:

  None

  • Meeting 56 : Thu, Mar 23, 12:00 pm-12:50 pm

  Completing the proof of 5/3 approx algo for max-card. weakly stable matching.

  References	Paper by Z. Kiraly (available on homepage).
  Exercises
  Reading

  Completing the proof of 5/3 approx algo for max-card. weakly stable matching.
  

  References:

  Paper by Z. Kiraly (available on homepage).

  • Meeting 57 : Mon, Mar 27, 11:00 am-11:50 am

  Stable Roommates problem.

  References
  Exercises
  Reading

  Stable Roommates problem.
  

  References:

  None

  • Meeting 58 : Tue, Mar 28, 10:00 am-10:50 am

  Holiday (Ugadi).

  References
  Exercises
  Reading

  Holiday (Ugadi).
  

  References:

  None

  • Meeting 59 : Wed, Mar 29, 09:00 am-09:50 am

  References
  Exercises
  Reading

  
  

  References:

  None

  • Meeting 60 : Thu, Mar 30, 12:00 pm-12:50 pm

  References
  Exercises
  Reading

  
  

  References:

  None