CS5800 - Advanced Data Structures and Algorithms

Meetings  

• Theme 1 : The Algorithmists Hat - 10 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 : 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 04 : 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 05 : 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 06 : 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 07 : 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 08 : 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 09 : 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 10 : 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 11 : 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 12 : 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 13 : 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 14 : 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 15 : 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 16 : 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 17 : 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 18 : 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 19 : 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 20 : 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 21 : 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 22 : 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 - 24 meetings

  • Meeting 23 : 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 24 : 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 25 : 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 26 : 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 27 : 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 28 : 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 29 : 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 30 : 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 31 : 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 32 : 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 33 : 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 34 : 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 35 : 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 36 : 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 37 : 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 38 : 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 39 : Thu, Oct 09, 12:00 pm-12:50 pm

  Tutorial 3

  References
  Exercises
  Reading

  Tutorial 3
  

  References:

  None

  • Meeting 40 : 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 41 : 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 42 : 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 43 : 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 44 : 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 45 : 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

  • Meeting 46 : Thu, Oct 23, 12:00 pm-12:50 pm

  Matroids. Exchange axiom and maximal independent sets. Examples of matroids. Linear Matroid. Graphic Matroid. Proof that the set of acyclic subsets of edges forms the independent sets of a graphic matroid. Recasting the minimal spanning tree problem as a maximal independent set problem in the graphic matroid. Interpreting Kruskal's algorithm as an algorithm in this matroid.

  References	Section 17.4 in [CLRS] 3rd edition - for some reason, this is not there in 4th edition.
  Exercises
  Reading

  Matroids. Exchange axiom and maximal independent sets. Examples of matroids. Linear Matroid. Graphic Matroid. Proof that the set of acyclic subsets of edges forms the independent sets of a graphic matroid. Recasting the minimal spanning tree problem as a maximal independent set problem in the graphic matroid. Interpreting Kruskal's algorithm as an algorithm in this matroid.
  

  References:

  Section 17.4 in [CLRS] 3rd edition - for some reason, this is not there in 4th edition.

• Theme 4 : Dynamic Programming Techniques - 7 meetings

  • Meeting 47 : Sat, Oct 25, 02:00 pm-02:50 pm

  (Compensatory Lecture for Jul 31st) Computing the Fibonacci Number. Recursive Algorithm. Memoization as a technique to close the recursion faster. Iterative version. Weighted interval scheduling problem. A recurrence relation and proof of correctness. The DP graph of the problem.

  References	[E] Section 3.1
  Exercises
  Reading

  (Compensatory Lecture for Jul 31st) Computing the Fibonacci Number. Recursive Algorithm. Memoization as a technique to close the recursion faster. Iterative version. Weighted interval scheduling problem. A recurrence relation and proof of correctness. The DP graph of the problem.
  

  References:

  [E] Section 3.1

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

  Anatomy of DP solutions. (a) the recursive formulation (b) correctness of recursive relation (c) dependency between the subproblems represented in the form of the dependency graph. Two more examples - (1) shortest path in DAGs (2) longest increasing subsequence in a given sequence of numbers.

  References	[DPV] Chapter 6 - Section 6.1 and 6.2
  Exercises
  Reading

  Anatomy of DP solutions. (a) the recursive formulation (b) correctness of recursive relation (c) dependency between the subproblems represented in the form of the dependency graph. Two more examples - (1) shortest path in DAGs (2) longest increasing subsequence in a given sequence of numbers.
  

  References:

  [DPV] Chapter 6 - Section 6.1 and 6.2

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

  Tutorial (based on Practice Sheets 7 and 8)

  References
  Exercises
  Reading

  Tutorial (based on Practice Sheets 7 and 8)
  

  References:

  None

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

  Knapsack Problem and Variants. The subset sum problem. Fractional Knapsack Problem. Greedy Algorithm. Attempts on greedy algorithm for the subset sum problem. Counter examples.

  References	[KT] Section 6.4<br> <a href-"https://courses.cs.duke.edu/compsci330/spring19/lecture8scribe.pdf">Greedy Algorithm for fractional Knapsack</a>.
  Exercises
  Reading

  Knapsack Problem and Variants. The subset sum problem. Fractional Knapsack Problem. Greedy Algorithm. Attempts on greedy algorithm for the subset sum problem. Counter examples.
  

  References:

  [KT] Section 6.4 Greedy Algorithm for fractional Knapsack.

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

  Dynamic Programming algorithm for Knapsack problem. Proof of correctness. Generalization for the integral knapsack. O(nW) pseudopolynomial algorithm.

  References	[KT] Section 6.4
  Exercises
  Reading

  Dynamic Programming algorithm for Knapsack problem. Proof of correctness. Generalization for the integral knapsack. O(nW) pseudopolynomial algorithm.
  

  References:

  [KT] Section 6.4

  • Meeting 52 : Thu, Oct 30, 06:00 pm-06:50 pm

  (Compensatory Lecture for Nov 3rd)<br>Greedy Approximation Algorithm for Integral Knapsack problem. Proof of the approximation ratio. <br><br>Shortest paths in negative edge weighted graphs. Preliminary observations and negative cycles. Arriving at the subproblem.

  References	<a href="https://ac.informatik.uni-freiburg.de/lak_teaching/ws11_12/combopt/notes/knapsack.pdf">Lecture Notes</a><br> [KT] Section 6.6
  Exercises
  Reading

  (Compensatory Lecture for Nov 3rd)
  Greedy Approximation Algorithm for Integral Knapsack problem. Proof of the approximation ratio.
  
  Shortest paths in negative edge weighted graphs. Preliminary observations and negative cycles. Arriving at the subproblem.
  

  References:

  Lecture Notes [KT] Section 6.6

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

  Bellman-Ford recursive formulation. Proof of correctness, Running time. Improved analysis using amortization. Space-efficient implementation using rowwise incremental implementation.

  References	[KT] Section 6.6
  Exercises
  Reading

  Bellman-Ford recursive formulation. Proof of correctness, Running time. Improved analysis using amortization. Space-efficient implementation using rowwise incremental implementation.
  

  References:

  [KT] Section 6.6

• Theme 5 : Intractability - 3 meetings

  • (Upcoming) Meeting 54 : Sat, Nov 08, 02:00 pm-02:50 pm

  (Compesatory Lecture for Nov 4th) 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

  (Compesatory Lecture for Nov 4th) 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 55 : Mon, Nov 10, 11:00 am-11: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 56 : Tue, Nov 11, 10:00 am-10: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

• Theme 6 : Evaluation Meetings - 2 meetings

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

  Short Exam 1

  References
  Exercises
  Reading

  Short Exam 1
  

  References:

  None

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

  Short Exam 2

  References
  Exercises
  Reading

  Short Exam 2
  

  References:

  None