CS5800 - Advanced Data Structures and Algorithms

Meetings  

• Theme 1 : The Algorithmists Hat - 11 meetings

  • Meeting 01 : Tue, Jul 29, 10:00 am-10:50 am

  Review of asymptotic analysis. (Lecture by Yadu Vasudev)

  References	Chapter 3 of [CLRS]
  Exercises
  Reading

  Review of asymptotic analysis. (Lecture by Yadu Vasudev)
  

  References:

  Chapter 3 of [CLRS]

  • Meeting 02 : Wed, Jul 30, 09:00 am-09:50 am

  Review of asymptotic analysis (Lecture by Yadu Vasudev)

  References	Chapter 3 of [CLRS]
  Exercises
  Reading

  Review of asymptotic analysis (Lecture by Yadu Vasudev)
  

  References:

  Chapter 3 of [CLRS]

  • Meeting 03 : Thu, Jul 31, 12:00 pm-12:50 pm

  To be compensated.

  References
  Exercises
  Reading

  To be compensated.
  

  References:

  None

  • Meeting 04 : Tue, Aug 05, 10:00 am-10:50 am

  Introduction and Administrative announcements about the course. Important algorithms around. Designers thoughts. What is expected from an algorithm designer. Need of mathematical rigor and proofs.

  References	Chapter 2 in [CLRS]
  Exercises
  Reading

  Introduction and Administrative announcements about the course. Important algorithms around. Designers thoughts. What is expected from an algorithm designer. Need of mathematical rigor and proofs.
  

  References:

  Chapter 2 in [CLRS]

  • Meeting 05 : Wed, Aug 06, 09:00 am-09:50 am

  Algorithm designers hat. Four stage thought process after any algorithm design. Termination, Correctness, Analysis, Optimality. Optimality of analysis vs optimality of the algorithm itself. Idea of lower bounds for a problem.

  References	Chapter 2 in [CLRS]
  Exercises
  Reading

  Algorithm designers hat. Four stage thought process after any algorithm design. Termination, Correctness, Analysis, Optimality. Optimality of analysis vs optimality of the algorithm itself. Idea of lower bounds for a problem.
  

  References:

  Chapter 2 in [CLRS]

  • Meeting 06 : Thu, Aug 07, 12:00 pm-12:50 pm

  Techniques for proof of correncess for iterative algorithms. Loop invariants. Analysis of running time by direct counting. Example of insertion sort.

  References	Section 2.1 in [CLRS]
  Exercises
  Reading

  Techniques for proof of correncess for iterative algorithms. Loop invariants. Analysis of running time by direct counting. Example of insertion sort.
  

  References:

  Section 2.1 in [CLRS]

  • Meeting 07 : Mon, Aug 11, 11:00 am-11:50 am

  Multiplying two n-bit numbers. Trivial Methods. A O(2^n) algorithm. Improvement to O(n^2) algorithm. ecursive methods. Termination argument by base case. Correctness argument by induction. Runtime analysis by recurrences. Question of lower bounds. Lower bound of O(n). Karastuba's multiplication surprise. The Karstuba recurrence.

  References	<a href="https://www.cs.cmu.edu/~15451-f21/lectures/lec22.pdf">Karastuba Multiplcation</a>
  Exercises
  Reading

  Multiplying two n-bit numbers. Trivial Methods. A O(2^n) algorithm. Improvement to O(n^2) algorithm. ecursive methods. Termination argument by base case. Correctness argument by induction. Runtime analysis by recurrences. Question of lower bounds. Lower bound of O(n). Karastuba's multiplication surprise. The Karstuba recurrence.
  

  References:

  Karastuba Multiplcation

  • Meeting 08 : Tue, Aug 12, 10:00 am-10:50 am

  Solving recurrences by substitution method. Proofs by induction. Recursion tree method. Developing into masters theorem.

  References	Section 4.2 and 4.3 in [CLRS]
  Exercises
  Reading

  Solving recurrences by substitution method. Proofs by induction. Recursion tree method. Developing into masters theorem.
  

  References:

  Section 4.2 and 4.3 in [CLRS]

  • Meeting 09 : Wed, Aug 13, 09:00 am-09:50 am

  Example applications for masters theorem. Proof of master theorem.

  References	Section 4.5 in [CLRS]
  Exercises
  Reading

  Example applications for masters theorem. Proof of master theorem.
  

  References:

  Section 4.5 in [CLRS]

  • Meeting 10 : Wed, Aug 13, 06:00 pm-06:50 pm

  Completing the proof of masters theorem. Introdcution to adversary arguments. Finding the largest element in an array of n elements require n-1 comparisons.

  References	Section 4.5 in [CLRS]
  Exercises
  Reading

  Completing the proof of masters theorem. Introdcution to adversary arguments. Finding the largest element in an array of n elements require n-1 comparisons.
  

  References:

  Section 4.5 in [CLRS]

  • Meeting 11 : Thu, Aug 14, 12:00 pm-12:50 pm

  Tutorial - I

  References
  Exercises
  Reading

  Tutorial - I
  

  References:

  None

• Theme 2 : Divide & Conquer Technique - 12 meetings

  • Meeting 12 : Mon, Aug 18, 11:00 am-11:50 am

  Merge Sort Algorithm. Correctness. Analysis. Optimality. Adversary Arguments for sorting algorithms.

  References	<a href="https://goldman.cse.wustl.edu/crc2007/handouts/adv-lb.pdf">Reference for Optimality using adversary arguments for sorting</a>.
  Exercises
  Reading

  Merge Sort Algorithm. Correctness. Analysis. Optimality. Adversary Arguments for sorting algorithms.
  

  References:

  Reference for Optimality using adversary arguments for sorting.

  • Meeting 13 : Tue, Aug 19, 10:00 am-10:50 am

  Quicksort Algorithm. Correctness, and analysis. Role of the pivot. Worst case pivot. Best case pivot. Average case analysis.

  References	Chapter 7 in [CLRS]
  Exercises
  Reading

  Quicksort Algorithm. Correctness, and analysis. Role of the pivot. Worst case pivot. Best case pivot. Average case analysis.
  

  References:

  Chapter 7 in [CLRS]

  • Meeting 14 : Wed, Aug 20, 09:00 am-09:50 am

  Randomized Quicksort. Quick recap of probability distributions, random variables and expectation. How to model our problem using this. Decomposing into "simpler" random variables.

  References	Setion 7.4 of [CLRS]
  Exercises
  Reading

  Randomized Quicksort. Quick recap of probability distributions, random variables and expectation. How to model our problem using this. Decomposing into "simpler" random variables.
  

  References:

  Setion 7.4 of [CLRS]

  • Meeting 15 : Mon, Aug 25, 11:00 am-11:50 am

  Indicator random variables and their expectation. Linearity of expectation. Computing the analysis of the randomized quicksort. Overview and features of the method.

  References	Setion 5.2 and Setion 7.4 of [CLRS]
  Exercises
  Reading

  Indicator random variables and their expectation. Linearity of expectation. Computing the analysis of the randomized quicksort. Overview and features of the method.
  

  References:

  Setion 5.2 and Setion 7.4 of [CLRS]

  • Meeting 16 : Tue, Aug 26, 10:00 am-10:50 am

  The task of finding the median. Finding the k-th smallest element. Quick-sort-like method. Median of medians to get an "approximate median" to get a balanced split. The analysis and recurrence relation. Linear time algorithm for k-th smallest element.

  References	Section 1.8 in <a href="https://jeffe.cs.illinois.edu/teaching/algorithms/book/01-recursion.pdf">Jeff Erikson's Book</a>.
  Exercises
  Reading

  The task of finding the median. Finding the k-th smallest element. Quick-sort-like method. Median of medians to get an "approximate median" to get a balanced split. The analysis and recurrence relation. Linear time algorithm for k-th smallest element.
  

  References:

  Section 1.8 in Jeff Erikson's Book.

  • Meeting 17 : Thu, Aug 28, 12:00 pm-12:50 pm

  Counting the number of inversions. The divide and conquer by strengthening the induction/recursion.

  References	[KT] Textbook Sectoion 5.3
  Exercises
  Reading

  Counting the number of inversions. The divide and conquer by strengthening the induction/recursion.
  

  References:

  [KT] Textbook Sectoion 5.3

  • Meeting 18 : Mon, Sep 01, 11:00 am-11:50 am

  Closest Pair Problem. Divide and Conquer for the O(n log n) algorithm. Bounded inspection lemma for the combine step. Proof of correctness.

  References	[KT] Section 5.4
  Exercises
  Reading

  Closest Pair Problem. Divide and Conquer for the O(n log n) algorithm. Bounded inspection lemma for the combine step. Proof of correctness.
  

  References:

  [KT] Section 5.4

  • Meeting 19 : Tue, Sep 02, 10:00 am-10:50 am

  Dictionary data structure. Implementation of dictionary using arrays. Using dictionary operations for a randomized algorithm for closest pair problem with expected linear time.

  References	[KT] Section 13.7
  Exercises
  Reading

  Dictionary data structure. Implementation of dictionary using arrays. Using dictionary operations for a randomized algorithm for closest pair problem with expected linear time.
  

  References:

  [KT] Section 13.7

  • Meeting 20 : Wed, Sep 03, 09:00 am-09:50 am

  Details of the Analysis.

  References	[KT] Section 13.7
  Exercises
  Reading

  Details of the Analysis.
  

  References:

  [KT] Section 13.7

  • Meeting 21 : Thu, Sep 04, 12:00 pm-12:50 pm

  Hashing. Use of Hashing to implement dictionaries. Implementation of hashing using arrays. Disadvantages. Chaining and Worst case behaviour. Using randomness to beat the worst case. The big hash family. Universlity property. Size of the family. Comparisons with the trivial implementation of the hash table.

  References	[KT] Section 13.5 and 13.6
  Exercises
  Reading

  Hashing. Use of Hashing to implement dictionaries. Implementation of hashing using arrays. Disadvantages. Chaining and Worst case behaviour. Using randomness to beat the worst case. The big hash family. Universlity property. Size of the family. Comparisons with the trivial implementation of the hash table.
  

  References:

  [KT] Section 13.5 and 13.6

  • Meeting 22 : Mon, Sep 08, 11:00 am-11:50 am

  Using universality property to derive expected chain length. Discussion of the proof strategy.

  References	[KT] Section 13.5 and 13.6
  Exercises
  Reading

  Using universality property to derive expected chain length. Discussion of the proof strategy.
  

  References:

  [KT] Section 13.5 and 13.6

  • Meeting 23 : Tue, Sep 09, 10:00 am-10:50 am

  Construction of a smaller universal hash family. Achieving universality for hash families.

  References	[KT] Section 13.5 and 13.6
  Exercises
  Reading

  Construction of a smaller universal hash family. Achieving universality for hash families.
  

  References:

  [KT] Section 13.5 and 13.6

• Theme 3 : Greedy Technique & Data Structures - 23 meetings

  • Meeting 24 : Wed, Sep 10, 09:00 am-09:50 am

  Greedy strategies for optimization problems. Interval scheduling problem. Five heuristic greedy strategies. Counter examples for claim of optimality for four of them. The need of a formal proof for the "earliest finishing task first" strategy.

  References	Section 4.1 in [KT]
  Exercises
  Reading

  Greedy strategies for optimization problems. Interval scheduling problem. Five heuristic greedy strategies. Counter examples for claim of optimality for four of them. The need of a formal proof for the "earliest finishing task first" strategy.
  

  References:

  Section 4.1 in [KT]

  • Meeting 25 : Thu, Sep 11, 12:00 pm-12:50 pm

  Correctness proof details - Greedy stays ahead. Discussion on implementation.

  References	Section 4.1 in [KT]
  Exercises
  Reading

  Correctness proof details - Greedy stays ahead. Discussion on implementation.
  

  References:

  Section 4.1 in [KT]

  • Meeting 26 : Mon, Sep 15, 11:00 am-11:50 am

  Single source shortest path. Greedy stays ahead. Dijkstra's algorithm. Greedy stays ahead strategy - the loop invariant.

  References	Section 4.2 in [KT]
  Exercises
  Reading

  Single source shortest path. Greedy stays ahead. Dijkstra's algorithm. Greedy stays ahead strategy - the loop invariant.
  

  References:

  Section 4.2 in [KT]

  • Meeting 27 : Tue, Sep 16, 10:00 am-10:50 am

  Analysis of Dijkstra's Algorithm using improved implementations. Implementation of priority queue, the required operations. Simple implementations. Cost analysis.

  References	Section 4.2 in [KT]
  Exercises
  Reading

  Analysis of Dijkstra's Algorithm using improved implementations. Implementation of priority queue, the required operations. Simple implementations. Cost analysis.
  

  References:

  Section 4.2 in [KT]

  • Meeting 28 : Wed, Sep 17, 09:00 am-09:50 am

  Heaps. Almost full binary trees with heap property. Array representation. Heapify procedure. Analysis of Heapify procedure.

  References	Section 6.1 and 6.2 of [CLRS]
  Exercises
  Reading

  Heaps. Almost full binary trees with heap property. Array representation. Heapify procedure. Analysis of Heapify procedure.
  

  References:

  Section 6.1 and 6.2 of [CLRS]

  • Meeting 29 : Thu, Sep 18, 12:00 pm-12:50 pm

  Tutorial 2 (Based on problem sheets 3 and 4)

  References
  Exercises
  Reading

  Tutorial 2 (Based on problem sheets 3 and 4)
  

  References:

  None

  • Meeting 30 : Mon, Sep 22, 11:00 am-11:50 am

  Implemetation Details of Maxheaps - Analysis of Buildheap, Extract-min, Decrease Key. Motivation to do better on Decrease key operation.

  References	Section 6.3 and 6.5 in [CLRS]
  Exercises
  Reading

  Implemetation Details of Maxheaps - Analysis of Buildheap, Extract-min, Decrease Key. Motivation to do better on Decrease key operation.
  

  References:

  Section 6.3 and 6.5 in [CLRS]

  • Meeting 31 : Tue, Sep 23, 10:00 am-10:50 am

  Strategy to do better implementation for decrease-key operations. Introduction to amortization. Example of bit increments in a binary counter. Stack with Multipop example.

  References	Section 16.1 in [CLRS]
  Exercises
  Reading

  Strategy to do better implementation for decrease-key operations. Introduction to amortization. Example of bit increments in a binary counter. Stack with Multipop example.
  

  References:

  Section 16.1 in [CLRS]

  • Meeting 32 : Wed, Sep 24, 09:00 am-09:50 am

  Accounting Method of amortized analysis. Applying to the binary counter, and the multistack example.

  References	Section 16.2 in [CLRS]
  Exercises
  Reading

  Accounting Method of amortized analysis. Applying to the binary counter, and the multistack example.
  

  References:

  Section 16.2 in [CLRS]

  • Meeting 33 : Sat, Sep 27, 09:00 am-10:15 am

  Potential Method for amortized analysis. Applying for the binary counter, multistack, array doubling and the binary heap example.

  References	Section 16.3 in [CLRS]
  Exercises
  Reading

  Potential Method for amortized analysis. Applying for the binary counter, multistack, array doubling and the binary heap example.
  

  References:

  Section 16.3 in [CLRS]

  • Meeting 34 : Mon, Sep 29, 11:00 am-11:50 am

  Fibonacci Heaps - Basic ideas, examples. Insert and Union. Implementation Details.

  References	[CLRS] Slides shared with class.
  Exercises
  Reading

  Fibonacci Heaps - Basic ideas, examples. Insert and Union. Implementation Details.
  

  References:

  [CLRS] Slides shared with class.

  • Meeting 35 : Tue, Sep 30, 10:00 am-10:50 am

  Fibonacci Heaps - Extract min. Potential function. Analysis of extract min.

  References	[CLRS]. Slides shared with class.
  Exercises
  Reading

  Fibonacci Heaps - Extract min. Potential function. Analysis of extract min.
  

  References:

  [CLRS]. Slides shared with class.

  • Meeting 36 : Wed, Oct 01, 09:00 am-09:50 am

  Fibonacci Heaps - Decrease Key. Analysis of Decrease Key.

  References	[CLRS] Slides shared with class.
  Exercises
  Reading

  Fibonacci Heaps - Decrease Key. Analysis of Decrease Key.
  

  References:

  [CLRS] Slides shared with class.

  • Meeting 37 : Mon, Oct 06, 11:00 am-11:50 am

  Proof of degree bounds in Fib heaps.<br> Minimal Spanning Tree Problem. Problem definition and discussion.

  References	[CLRS] Slides shared with class.
  Exercises
  Reading

  Proof of degree bounds in Fib heaps.
  Minimal Spanning Tree Problem. Problem definition and discussion.
  

  References:

  [CLRS] Slides shared with class.

  • Meeting 38 : Tue, Oct 07, 10:00 am-10:50 am

  Is the MST unique? Glimpse of an "exchange argument" to prove that if all edge weights are distinct, then MST must be unique. <br> Approaches towards MST problem. The idea of growing and MST from scratch. Safe edges to add. When is an edge safe to add?

  References	[E] Section 7.1, 7.2
  Exercises
  Reading

  Is the MST unique? Glimpse of an "exchange argument" to prove that if all edge weights are distinct, then MST must be unique.
  Approaches towards MST problem. The idea of growing and MST from scratch. Safe edges to add. When is an edge safe to add?
  

  References:

  [E] Section 7.1, 7.2

  • Meeting 39 : Wed, Oct 08, 09:00 am-09:50 am

  Lightest cut edges are always safe. All safe edges must be a part of any MST. Exchange argument in action. <br> So we can add all safe edges and recurse - Boruvka's Algorithm. Different ways of moving towards MST. Kruskal's Algorithm and Prim's Algorithm.

  References	[E] Section 7.1, 7.2 and [KT] section 4.5
  Exercises
  Reading

  Lightest cut edges are always safe. All safe edges must be a part of any MST. Exchange argument in action.
  So we can add all safe edges and recurse - Boruvka's Algorithm. Different ways of moving towards MST. Kruskal's Algorithm and Prim's Algorithm.
  

  References:

  [E] Section 7.1, 7.2 and [KT] section 4.5

  • Meeting 40 : Thu, Oct 09, 12:00 pm-12:50 pm

  Tutorial 3

  References
  Exercises
  Reading

  Tutorial 3
  

  References:

  None

  • Meeting 41 : Mon, Oct 13, 11:00 am-11:50 am

  Spectrum of MST Algorithms via the cut property and the cycle property. Implementing Prim's Algorithm. Using Binary heaps and then Fib heaps.

  References	[E] Section 7.1, 7.2 and [KT] section 4.5
  Exercises
  Reading

  Spectrum of MST Algorithms via the cut property and the cycle property. Implementing Prim's Algorithm. Using Binary heaps and then Fib heaps.
  

  References:

  [E] Section 7.1, 7.2 and [KT] section 4.5

  • Meeting 42 : Tue, Oct 14, 10:00 am-10:50 am

  Implemeting Kruskal's Algorithm. Union-Find Data structure. Array implementation. Amortized analysis. MAKESET in O(1), FIND in O(1), UNION in O(log k) amortized over k unions.

  References	[KT] section 4.6
  Exercises
  Reading

  Implemeting Kruskal's Algorithm. Union-Find Data structure. Array implementation. Amortized analysis. MAKESET in O(1), FIND in O(1), UNION in O(log k) amortized over k unions.
  

  References:

  [KT] section 4.6

  • Meeting 43 : Wed, Oct 15, 09:00 am-09:50 am

  Union by rank implementation. Rank based analysis. MAKESET in O(1), UNION in O(1), FIND in O(log n) worst case analysis.

  References	[DPV] Section 5.1.4
  Exercises
  Reading

  Union by rank implementation. Rank based analysis. MAKESET in O(1), UNION in O(1), FIND in O(log n) worst case analysis.
  

  References:

  [DPV] Section 5.1.4

  • Meeting 44 : Thu, Oct 16, 12:00 pm-12:50 pm

  Union by rank and path compression. Implementation of path compression. Examples. Properties being preserved.

  References	[DPV] Section 5.1.4
  Exercises
  Reading

  Union by rank and path compression. Implementation of path compression. Examples. Properties being preserved.
  

  References:

  [DPV] Section 5.1.4

  • Meeting 45 : Tue, Oct 21, 10:00 am-10:50 am

  Analysis to prove that MAKESET in O(1), UNION in O(1), FIND in O(log* n) amortized cost. Pocket money argument based on the rank interval.

  References	[DPV] Section 5.1.4
  Exercises
  Reading

  Analysis to prove that MAKESET in O(1), UNION in O(1), FIND in O(log* n) amortized cost. Pocket money argument based on the rank interval.
  

  References:

  [DPV] Section 5.1.4

  • Meeting 46 : Wed, Oct 22, 09:00 am-09:50 am

  Huffman coding problem. The greedy algorithm. Greedy-choice correctness property via an exchange argument. Optimal substructure property.

  References
  Exercises
  Reading

  Huffman coding problem. The greedy algorithm. Greedy-choice correctness property via an exchange argument. Optimal substructure property.
  

  References:

  None

• Theme 4 : Dynamic Programming Techniques - 4 meetings

  • (Upcoming) Meeting 47 : Thu, Oct 23, 12:00 pm-12:50 pm

  Recap of an example from decrease and conquer. Computing the Fibanacci Number. Recurisve Algorithm. Memoization as a technique to close the recursion faster. Iterative version. Weighted interval scheduling problem. A recurrence relation and proof of correctness.

  References
  Exercises
  Reading

  Recap of an example from decrease and conquer. Computing the Fibanacci Number. Recurisve Algorithm. Memoization as a technique to close the recursion faster. Iterative version. Weighted interval scheduling problem. A recurrence relation and proof of correctness.
  

  References:

  None

  • (Upcoming) Meeting 48 : Mon, Oct 27, 11:00 am-11:50 am

  Algorithm description for Weighted interval scheduling. Iterative version. From memoization to dynamic programming. Structure of Dynamic Programming Solutions. Overlapping Subproblems and the Dependency DAG of subproblems. Requirements for the DP algorithms to be efficient. Maximum sum subarray problem.

  References
  Exercises
  Reading

  Algorithm description for Weighted interval scheduling. Iterative version. From memoization to dynamic programming. Structure of Dynamic Programming Solutions. Overlapping Subproblems and the Dependency DAG of subproblems. Requirements for the DP algorithms to be efficient. Maximum sum subarray problem.
  

  References:

  None

  • (Upcoming) Meeting 49 : Tue, Oct 28, 10:00 am-10:50 am

  Knapsack Problem and Variants. The subset sum problem. Attempts on greedy algorithm. Counter examples. Dynamic Programming algorithm. Proof of correctness. Generalization for the integral knapsack. O(nW) pseudopolynomial algorithm.

  References
  Exercises
  Reading

  Knapsack Problem and Variants. The subset sum problem. Attempts on greedy algorithm. Counter examples. Dynamic Programming algorithm. Proof of correctness. Generalization for the integral knapsack. O(nW) pseudopolynomial algorithm.
  

  References:

  None

  • (Upcoming) Meeting 50 : Wed, Oct 29, 09:00 am-09:50 am

  Shortest paths in negative edge weighted graphs. Bellman Ford Algorithm, Proof of correctness, Running time. Improved analysis using amortization. Space-efficient implementation using rowwise incremental implementation.

  References
  Exercises
  Reading

  Shortest paths in negative edge weighted graphs. Bellman Ford Algorithm, Proof of correctness, Running time. Improved analysis using amortization. Space-efficient implementation using rowwise incremental implementation.
  

  References:

  None

• Theme 5 : Iterative Improvement Technique - 5 meetings

  • (Upcoming) Meeting 51 : Thu, Oct 30, 12:00 pm-12:50 pm

  Tutorial

  References
  Exercises
  Reading

  Tutorial
  

  References:

  None

  • (Upcoming) Meeting 52 : Mon, Nov 03, 11:00 am-11:50 am

  Flow networks, Maximum flow problem. Examples. Improving flow values. Trivial strategies to improve flow. Counter examples. Residual network and the capacities. Paths in the residual networks. Formal definition of residual network. Augmenting using flows in residual network to improve the flow in the original network. Augmented function gives a flow.Augmentation always improves the flow value. Bound on the number of augmentation iterations. Plan of the proof that "no augmenting path" in residual network implies flow cannot be improved. Cuts, capacity of cuts and netflow across cuts. Examples. For any flow, the net flow across any cut is equal to the flow value. If there is no augmenting path in the residual network of a flow, then there is a cut for which the flow value is equal to capacity of the cut, and hence the flow cannot be improved further. Psuedopolynomial time. Ideas for improvement to polynomial time algorithm due to Edmond-Karp (without formal proof). Maximum Bipartite Matching Problem. Transformation to an instance of maximum flow problem. Using the maximum flow to solve the maximum cardinality matching problem. Integrality of flow values. Formal proof of correctness of the transformation. If M is a matching of size k, then there is an integral flow of value k.

  References
  Exercises
  Reading

  Flow networks, Maximum flow problem. Examples. Improving flow values. Trivial strategies to improve flow. Counter examples. Residual network and the capacities. Paths in the residual networks. Formal definition of residual network. Augmenting using flows in residual network to improve the flow in the original network. Augmented function gives a flow.Augmentation always improves the flow value. Bound on the number of augmentation iterations. Plan of the proof that "no augmenting path" in residual network implies flow cannot be improved. Cuts, capacity of cuts and netflow across cuts. Examples. For any flow, the net flow across any cut is equal to the flow value. If there is no augmenting path in the residual network of a flow, then there is a cut for which the flow value is equal to capacity of the cut, and hence the flow cannot be improved further. Psuedopolynomial time. Ideas for improvement to polynomial time algorithm due to Edmond-Karp (without formal proof). Maximum Bipartite Matching Problem. Transformation to an instance of maximum flow problem. Using the maximum flow to solve the maximum cardinality matching problem. Integrality of flow values. Formal proof of correctness of the transformation. If M is a matching of size k, then there is an integral flow of value k.
  

  References:

  None

  • (Upcoming) Meeting 53 : Tue, Nov 04, 10:00 am-10:50 am

  Continuing the correctness of transformation. From an integral flow of value k to a matching in the bipartite graph of cardinality k.

  References
  Exercises
  Reading

  Continuing the correctness of transformation. From an integral flow of value k to a matching in the bipartite graph of cardinality k.
  

  References:

  None

  • (Upcoming) Meeting 54 : Wed, Nov 05, 09:00 am-09:50 am

  Minimum vertex cover problem on bipartite graphs. Konig's theorem. Minimum vertex cover size is equal to minimum capacity of a cut. Using the maxflow-mincut theorem to complete the argument for Konig's theorem.

  References
  Exercises
  Reading

  Minimum vertex cover problem on bipartite graphs. Konig's theorem. Minimum vertex cover size is equal to minimum capacity of a cut. Using the maxflow-mincut theorem to complete the argument for Konig's theorem.
  

  References:

  None

  • (Upcoming) Meeting 55 : Thu, Nov 06, 12:00 pm-12:50 pm

  Tutorial - 5

  References
  Exercises
  Reading

  Tutorial - 5
  

  References:

  None

• Theme 6 : Intractability - 4 meetings

  • (Upcoming) Meeting 56 : Mon, Nov 10, 11:00 am-11:50 am

  Formulating some algorithmic problems of relevance. Independent Set, Vertex Cover, Clique, Minckt Problem, Composites, Graph Isomorphism, Satisfiability checking. Need of efficient algorithms. Trivial exponential time algorithms.

  References
  Exercises
  Reading

  Formulating some algorithmic problems of relevance. Independent Set, Vertex Cover, Clique, Minckt Problem, Composites, Graph Isomorphism, Satisfiability checking. Need of efficient algorithms. Trivial exponential time algorithms.
  

  References:

  None

  • (Upcoming) Meeting 57 : Tue, Nov 11, 10:00 am-10:50 am

  Question 2 - notion of reductions. The running time of the reduction. "many-one" reductions. Examples, Clique vs Independent Set. Formal proof of correctness of the reduction. Independent set vs Vertex Cover.

  References
  Exercises
  Reading

  Question 2 - notion of reductions. The running time of the reduction. "many-one" reductions. Examples, Clique vs Independent Set. Formal proof of correctness of the reduction. Independent set vs Vertex Cover.
  

  References:

  None

  • (Upcoming) Meeting 58 : Wed, Nov 12, 09:00 am-09:50 am

  The hardest problems in NP. Notion of NP-hardness and NP-completeness. Cook-Levin Theorem (Statement). 3SAT to Vertex Cover Reduction and its correctness. 2SAT can be solved in polynomial time.

  References
  Exercises
  Reading

  The hardest problems in NP. Notion of NP-hardness and NP-completeness. Cook-Levin Theorem (Statement). 3SAT to Vertex Cover Reduction and its correctness. 2SAT can be solved in polynomial time.
  

  References:

  None

  • (Upcoming) Meeting 59 : Thu, Nov 13, 12:00 pm-12:50 pm

  Tutorial - 6

  References
  Exercises
  Reading

  Tutorial - 6
  

  References:

  None

• Theme 7 : Evaluation Meetings - 2 meetings

  • Meeting 60 : Thu, Aug 21, 12:00 pm-12:50 pm

  Short Exam 1

  References
  Exercises
  Reading

  Short Exam 1
  

  References:

  None

  • Meeting 61 : Thu, Sep 25, 12:00 pm-12:50 pm

  Short Exam 2

  References
  Exercises
  Reading

  Short Exam 2
  

  References:

  None