Department of Computer Science and Engineering

Module 1 (14 Hours)

Generating functions and applications: Power series expansion and generating functions, Catalan and Stirling numbers, solving recurrence equations using generating functions, Lambert series, Bell series and Dirichlet series, Applications.
Module 2 (14 Hours)

Existential Combinatorics: Ramsey theory, Ramsey theorem, Ramsey numbers, lower bound for R(k,k), Lovasz local lemma - bound on R(k,k) using Lovasz lemma, applications of local lemma.

Module 3 (14 Hours)

Matching theory: Bipartite matching, Konig's theorem, Hall's Matching Theorem, Network flow, Max flow min cut theorem, integrality, Ford Fulkerson method

Connectivity: Properties of 2 connected and 3 connected graphs, Menger's theorem, Applications
Module 4 (14 Hours)

Planar graphs and Colouring: Planar graphs, 5 color theorem, Brook's theorem, edge coloring, Vizing's theorem, list colouring, Thomassen's theorem.

References:

1. 
   R. P. Grimaldi, Discrete and Combinatorial Mathematics, Addison Wesley, 1998.
   
2. 
   R. P. Stanley. Enumerative Combinatorics, Cambridge University Press, 2001.
   
3. 
   P. J. Cameron, Combinatorics: Topics, Techniques and Algorithms, Cambridge University Press, 1995.
   

CS4026 COMBINATORIAL ALGORITHMS

Pre-requisite: Nil

L	T	P	C
3	0	2	4

Total Hours: 70 Hrs  

Module 1 (10 (T) + 7(P) Hours)

Network Flows: Review of graph theory – spanning trees, shortest paths. Connectivity, Network Flows - Max flow min cut theorem, algorithms of Ford-Fulkerson, Edmond Karp, preflow-push algorithms.
Module 2 (10 (T) + 7(P) Hours)

Primal Dual Theory: Linear programming – Primal dual theory, LP-duality based algorithm design.

Applications to Network flow and other combinatorial problems, Applications to graph theory - Konig's theorem, Halls theorem, Menger's theorem.
Module 3 (10 (T) + 7(P) Hours)

Matching Theory: Tutte's theorem, Primal dual algorithms – Hungarian algorithm, Edmond's maximum matching algorithm. Application to marriage problems, Hopcroft Karp algorithm.

Module 4 (12 (T) + 7(P) Hours)

Approximation: Primal Dual approximation algorithms for set cover, Maximum satisfiability, Steiner tree, multicut, Steiner forest, sparsest cut and k-medians.

References:

1. 
   D. West, Graph Theory, Prentice Hall, 2002.
   
2. 
   D. Jungnickel, Graphs Networks and Algorithms, Springer, 2005.
   
3. 
   U. Vazirani, Approximation Algorithms, Springer, 2003.
   
4. 
   T. H. Cormen, C. E. Leiserson, R. L. Rivest, S. C. Stein, Introduction to Algorithms, 4/e, McGraw Hill, 2010.
   

CS4027 TOPICS IN ALGORITHMS

Pre-requisite: Nil

L	T	P	C
4	0	0	4

Total Hours: 56 Hrs  

Module 1 (14 Hours)

Discrete Probability: Probability, Expectations, Tail Bounds, Chernoff Bound, Markov Chains. Random Walks Exponential Generating Functions, homogeneous and non-homogeneous of first and second degrees. Review of algorithm analysis.
Module 2 (14 Hours)

Randomized Algorithms, Moments and Deviations. Tail Inequalities. Randomized selection.

Las Vegas Algorithms. Monte Carlo Algorithms. Parallel and Distributed Algorithms. De-Randomization

Complexity: Probabilistic Complexity Classes

Module 3 (14 Hours)

Proof Theory. Examples of probabilistic algorithms. Probabilistic Method and Proofs, Proving that an algorithm is correct 'Almost sure'. Complexity analysis of probabilistic algorithms, Probabilistic Counting. Super recursive algorithms and inductive Turing machines

Module 4 (14 Hours)

Kolmogorv Complexity – Basic concepts. Models of Computation. Applications to analysis of algorithms. Lower bounds. Relation to Entropy. Kolmogorov complexity and universal probability. Godel's Incompleteness Theorem. Chatin’s Proof for Godel’s Theorem.

References:

1. R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.

2. C. H. Papadimitriou, Computational Complexity, Addison Wesley, 1994.

3. Dexter C. Kozen, The Design and Analysis of Algorithms, Springer Verlag, 1992.

4. Ronald Graham, Donald Knuth, Oren Patashnik, Concrete Mathematics, Addison-Wesley, 1989.

CS4028 QUANTUM COMPUTATION

Pre-requisite: Nil

L	T	P	C
4	0	0	4

Total Hours: 56 Hrs