Lecture 7: Flow networks with lower and upper limits (cont.) Multiplication of polynomials.

Tutorial 7: Divide an conquer: merge sort, Karatsuba algorithm, Strassen algorithm. 

Lecture 8: Fast Fourier Transform.

Tutorial 8: Fast Fourier Transform: examples.

 Lecture 9: Probabilistic algorithms. Rabin-Miller algorithm for primality testing. 

Tutorial 9: Schwartz-Zippel lemma and polynomial identity testing. Karger's algorithm. 

Lecture 10: Karger's algorithm (cont.) Linear programming problems. 

Lecture 11: Simplex algorithm.

Tutorial 11: Simplex method using tableau format. 

Lecture 12: Simplex algorithm: degeneracy example. Approximation algorithms. Vertex Cover problem. 

Tutorial 12: Set Cover problem. Traveling Salesman problem. 

Lecture 13: Travelling Salesman Problem in directed graphs. 

Lecture 14: PTAS for the bin packing problem. 

Tutorial 14: Using LP in approximation algorithms. Dual fitting based proof for the set cover problem. Rounding algorithm for the set cover.

Lecture 15: Primal-dual algorithms. Primal-dual approach to set cover. 

Tutorial 15: Primal-dual approach to set cover (cont.)