MTech in Theoretical Computer Science



Semester - 1




Semester - 2


Course Code

Course Title



Course Code

Course Title


CS 512

Data Structures and Algorithms



CS 515

Theory of Computation


CS 519

Probability and Linear Algebra



CS 520

Combinatorial Optimization


CS 533

Discrete Mathematical Structures



XX xxx

Elective – 2


XX xxx

Elective – 1



XX xxx

Elective – 3


CS 513


CS 596

Programming Lab







CS 597












Semester - 3




Semester - 4


Course Code

Course Title



Course Code

Course Title


CS 698




CS 699













* Indicates minimum required credits.

List of Electives for MTech in Theoretical Computer Science:


Each student is required to register for three elective courses. If a student wants to opt for electives that are outside following list, the student is required to take permission from DPPC.

Course No        Course Name


CS 501            Parallel Algorithms

CS 502            Computational Geometry

CS 503            Randomized Algorithms

CS 505            Structural Complexity

CS 506            Hierarchical Memory Algorithms

CS 507            Logic in Computer Science

CS 508            Optimization Methods

CS 509            Computational Number Theory and Cryptography

CS 510            Information and Randomness

CS 511            Learning with Kernels

CS 517            Self-stabilizing Algorithms

CS 518            Algorithmic Game Theory

CS 534            Approximation Algorithms


Seminar-1, Seminar-2 and Thesis:


The courses CS 596, CS 597, CS 698 and CS 699 should be opted in the area of Theoretical Computer Science or related topics.




Syllabi for MTech in Theoretical Computer Science


CS 501      Parallel Algorithms                       (3-0-0-6)


Pre-requisites: CS 204 (Algorithms) or equivalent


Theoretical models of parallel computation: variants of the PRAM model, interconnection networks, synchronous and asynchronous models. Performance of parallel algorithms. Basic techniques: balanced trees, recursive doubling, divide and conquer, partitioning, pipelining, accelerated cascading, symmetry breaking. List ranking, the Euler tour technique, tree contraction. Algorithms for searching, merging and sorting. Graph algorithms: Connected Components, Colouring. Parallel algorithms on interconnection networks and other architectures. Algorithms on asynchronous models. Limits to parallelizability. NC-reductions, P-completeness.




1.   J. Jaja, An Introduction to Parallel Algorithms, Addison Wesley, 1992.

2.   F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann Publishers, San Mateo, California, 1992.




1.   J. H. Reif, Synthesis of Parallel Algorithms, Morgan Kaufmann Publishers, San Mateo, California, 1993.

2.   S. G. Akl, Parallel Computation: Models and Methods, Prentice Hall, 1996.



CS 502      Computational Geometry  (3-0-0-6)


Pre-requisites: CS 204 (Algorithms) or equivalent


Algorithmic design paradigms (divide and conquer, incremental, sweep line, and prune and search) and basic data structures (segment and interval trees). Geometric searching: point locations (slab and chain methods) and range searching (kD and range trees); Convex hull: Graham's scan, gift wrapping, quick hull, divide-and-conquer; Voronoi diagram and Delaunay triangulation: properties and construction algorithms (sweep line and divide-and-conquer algorithms). Visibility and Art gallery problems, motion planning and shortest paths. Arrangements and duality; Line segments intersection problem; closest pair computation.




1.   F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, 1985.




1.   J. O'Rourke, Computational Geometry in C, 2nd Ed, Cambridge University Press, 1998.

2.   M. Laszlo, Computational Geometry and Computer Graphics in C++, Prentice-Hall, 1996.

3.   M. De Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry: Algorithms and Applications, Springer -Verlag, 1997.




CS 503      Randomized Algorithms    (3-0-0-6) 


Pre-requisite: CS 204 (Algorithms) and MA203 (Probability and Random Processes) or equivalent


Random numbers: Properties of a random sequence. Generating uniform random numbers: the linear congruential method and others. Statistical tests for random numbers: Chi-square test, Kolmogorov-Smirnov test, empirical / theoretical / spectral tests. Non-uniform random sequences. Tools and techniques of randomized algorithmics: game theoretic techniques, moments and deviations, tail inequalities, the probabilistic method: Lovasz Local Lemma, Markov chains and random walks, algebraic techniques. Applications: Data structures, hashing, linear programming, computational geometry problems, graph problems, approximate algorithms, parallel and distributed algorithms, cryptography, online algorithms.

Derandomization techniques.




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

2.   D. E. Knuth, The Art of Computer Programming, 3rd Ed, Vol 2, Seminumerical Algorithms, Addison-Wesley, 1998.

3.   W. Feller, An Introduction to Probability Theory and its Applications, Vol 1, Wiley Eastern, 1968.



CS 505      Structural Complexity         (3-0-0-6)


Pre-requisite: CS 301 (Formal Language and Automata) and CS 302 (Theory of Computation) or equivalent


Models of computation: automata, Turing machines, oracle Turing machines. Time and space bounded computations.


Central complexity classes: invertibility, honesty, NP-Complete Sets, PSPACE-complete sets, padding arguments, space bounded reducibility. Time bounded reducibility: relativized classes, tally and sparse sets, self-reducibility. Nonuniform complexity: Boolean circuit complexity, polynomial advice. logarithmic advice. Self-producible circuits. probabilistic complexity classes. Uniform diagonalization. The polynomial time hierarchy. Alternation, Kolmogorov complexity.




1.   J. L. Balcazar, J. Diaz and J. Gabarro, Structural Complexity, Vols 1 & 2, EATCS Monographs, Springer-Verlag, 1987.

2.   J. Van Leeuwen, Handbook of Theoretical Computer Science, Vol A, Elsevier and MIT Press, 1990.



CS 506      Hierarchical Memory Algorithms         (3-0-0-6)


Pre-requisite: CS204 (Algorithms) or equivalent


Hierarchical memory levels; performance characteristics; Parallel disk model. Fundamental I/O operations. Design and analysis of efficient external memory algorithms for some representative problems. Sorting, permutation, searching. Depth first search, breadth first search, Minimum spanning forest, connected components, single source shortest path, transitive closure. hashing, string matching. External Memory Data Structures.Cache efficient algorithms. Applications in various areas, for example, Computational geometry.




1.  J. S. Vitter. External Memory Algorithms and Data Structures: Dealing with MASSIVE DATA, ACM Computing Surveys, 33(2), June 2001, 209-271.

2.  Course Material on External Memory Algorithms and Data Structures:

3.  Other research papers.



CS 507      Logic in Computer Science (3-0-0-6)


Pre-requisites: CS203 (Discrete Mathematics) and CS 301 (Formal Languages and Automata Theory) or equivalent


Propositional Logic: Syntax, Proof System, Semantics, Soundness and completeness, Compactness, Normal Forms, Resolution, Horn Clauses, propositional satisfiability solvers, Complexity.


First Order Logic: Syntax, Proof System, Semantics, Soundness and Completeness, Compactness, Herbrand Models, Unification and Resolution, Logic Programming and SLD Resolution, Decidability and Undecidability, Expressiveness, Ehrenfeucht-Fraisse Games, Applications.


Modal Logic: Possibility and Necessity, Knowledge or Belief, Frames and Forcing, Modal Tableaux, Soundness and Completeness, Modal Axioms and Special Accessibility Relations, Logics of knowledge. Applications.



1.           A. Nerode and R. A. Shore, Logic for Applications, Springer-Verlag, 1997, 2nd edition.




 1.        M. Huth and M. Ryan, Logic in Computer Science: Modelling and Reasoning about Systems, 2nd Ed, Cambridge University Press, 2004.

2.        M. Fitting, First-order Logic and automated theorem proving, Springer-Verlag, 1990.

3.        J. H. Gallier, Logic for Computer Science: Foundations of Automatic Theorem Proving (Harper & Row Computer Science and Technology Series), John Wiley & Sons, 1986


CS 508      Optimization Methods        (3-0-0-6)


Introduction to Linear Programming: Connections with Geometry. Simplex Method: Duality Theorem. Complementary Slackness. Farkes Lemma. Revised Simplex Method. General LP Problems: Infeasibility. Sensitivity Analysis. Primal-Dual Algorithm: Applications to Network Flow and Matching. Efficient Algorithm: Linear Programming in fixed dimensions. Randomized Linear Programming. Integer Linear Programming: Total Unimodularity. Semidefinite Programming: Application to MAXSAT problems.




1.      V. Chavtal, Linear Programming, W. H. Freeman and Company, New York, 1983

2.    C. H. Papadimitriou and K. steiglitz, Combinatorial optimization: Algorithms and Complexity, Dover  Publications, Inc., New York, 1998




1.      M. Grotschel, L. Lovasz and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, John Wiley & Sons, Inc., New York, 1998

2.      W. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver, Combinatorial Optimization, John Wiley & Sons, Inc., New York, 1998

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

4.      Related publications in Journals/Conferences



CS 509        Computational Number Theory and Cryptography  (3-0-0-6)


Modular Arithmetic: Solving Modular Linear Equations, the Chinese Remainder Theorem, Modular Exponentiation, and DiscreteLogarithm Problem; GCD Computation: Euclid's Algorithm, Extended Euclid's Algorithm; Key Exchange: Diffie Hellman, ElGamal, Massey-Omura, Computation of Generators of Primes; Public Key Cryptosystem: RSA, Different Attacks & Remedies; Primality Testing: Pseudoprimality Testing, Quadratic Residues, Randomized Primality Test & Deterministic Polynomial Time Algorithm; Factorization: Quadratic-Sieve Factoring Algorithm, Pollard-Rho Method; Elliptic Curve Cryptosystem: Theory of Elliptic Curves, Elliptic Curve Encryption & Decryption Algorithms, Security of Elliptic Curves Cryptography, Elliptic Curve Factorization; Cryptographic Hash Functions: MD5 Message Digest Algorithm, Secure Hash Algorithm (SHA-1), Security of Hash Functions & Birthday Attack; Digital Signatures: Authentication Protocols, Digital Signature Standards (DSS).




1. T. H. Cormen, C. E. Leiserson, R. Rivest and C. Stein, Introduction to Algorithms, 2nd Edition, Prentice  Hall, 2002.

2. N. Koblitz, A Course in Number Theory and Cryptography, Springer-Verlag, New York, May 2001




1. O. Goldrich, Foundations of Cryptography-Basics, vol-1, Cambridge Univ. Press, 2005.

2. O. Goldrich, Foundations of Cryptography-Applications, vol-2, Cambridge Univ. Press, 2005

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

4. W. Stallings, Cryptography and Network security: Principles and Practice, 3rd Ed, Prentice Hall, 2003.



CS 510      Information and Randomness   (3-0-0-6)


Definitions of randomness: statistical (Martin-Loef, Solovay), based on program size complexity (Chaitin). Equivalence of the definitions.


Random numbers: Properties of random and pseudo-random sequences. Provably secure pseudo-random generators. Examples of pseudo-random generators: Fake One-Time Pads, Period of a pRNG, Congruential Generators, Feedback Shift Generators, Blum-Blum-Shub Generator, Naor-Reingold Generator. Statistical tests for random numbers: Chi-square test, Kolmogorov-Smirnov test, empirical / theoretical / spectral tests. Non-uniform random sequences. Randomized algorithms. Derandomization techniques.


Pseudo-random functions and permutations. Sequences of families of PSFs and PSPs. Applications: cryptographically strong hashing, prediction, learning, identify friend or foe, private-key encryption.




1. G. J. Chaitin, Algorithmic Information Theory, Cambridge University Press, 2004.

2. G. J. Chaitin, Information, Randomness and Incompleteness, 2nd edition, World Scientific, 1990.

3. G. J. Chaitin, Exploring Randomness, Springer-Verlag, 2001.

4. S. Goldwasser and M. Bellare, Lecture Notes in Cryptography,                                              , 2001.

5.P. Garrett, Making and Breaking Codes: Introduction to Cryptology, Prentice-Hall, 2000

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

7.D. E. Knuth, The Art of Computer Programming, 3rd Ed, Vol 2, Seminumerical Algorithms, Addison-Wesley, 1998

8.W. Feller, An Introduction to Probability Theory and its Applications, Vol 1, Wiley Eastern, 1968


CS 511      Learning with Kernels        (3-0-0-6)


Introduction: Data representation, similarity, statistical learning theory, hyper-plane classifiers, support vector classification, support vector regression, kernel principal component analysis; Kernels: Product features, representation of similarities in linear spaces, examples and properties of kernels; Risk and loss functions: Loss functions, test error, expected risk, statistical perspective, robust estimators; Regularization: Regularized risk functional, representer theorem, regularization operators, translation invariant kernels, dot product kernels; Optimization: Convex optimization, unconstrained problems, constrained problems; Support vector machines: Separating hyper-planes, role of margin, optimal margin hyper-planes, nonlinear support vector classifiers, soft margin hyperplanes,multi-class hyper-planes; Single class problems: introduction, algorithms,optimization, theory; Regression estimation: Linear regression with insensitive loss function, dual problems, -SV regression; Implementation: Tricks of the trade, sparse greedy matrix approximation, subset selection methods, sequential minimal optimization, iterative methods; Designing kernels: Tricks for constructing kernels, string kernels, natural kernels.




1.  B. SchÖlkopf and A. J. Smola. Learning with Kernels - support vector machines, regularization, optimization and beyond, The MIT Press, Cambridge, Massachusetts, London, England, 2002.




1. J. Shawe-Taylor and N. Cristianini, Kernel Methods for Pattern Analysis, Cambridge University Press, 2004.

2. N. Cristianini and J. Shawe-Taylor , Introduction to Support Vector Machines, CambridgeUniversity Press, 2000.







CS 512                Data Structures and Algorithms         (3-0-0-6)

Performance of algorithms: space and time complexity, asymptotics; Design techniques: the greedy method, divide-and-conquer, dynamic programming; Sorting and searching; Graph Algorithms; Priority Queues: lists, heaps, binomial heaps, Fibonacci heaps; Hashing; Search Trees: binary search trees, red-black trees, AVL trees, splay trees, B-trees; The disjoint set union problem; String matching; Strings: suffix arrays, tries; Randomized data structures: skip lists; A selection of advanced topics.



1.     T H Cormen, C E Leiserson, R L Rivest and C Stein, Introduction to Algorithms, MIT Press, 2001.

2.     J.Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005.



1.     A. Aho, J E Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.

2.     S Sahni, Data Structures, Algorithms and Applications in C++, McGraw-Hill, 2001.

3.     M. T. Goodrich and R. Tamassia, Algorithm Design: Foundations, Analysis and Internet Examples, John Wiley & Sons, 2001.



CS 513                Programming Lab                                  (0-0-3-3)


Experiments would be designed to provide hands-on experience in programming data structures and algorithms, to learn a few systems programming tools, and scripting.



1.     T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, MIT Press, 2001.

2.     J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005,

  1. M. A. Weiss, Data Structures and Algorithm Analysis in C++, Addison-Wesley, 2007



CS 515      Theory of Computation               (3-0-0-6)

Automata and Languages: finite automata and regular expressions, pushdown automata and context-free grammars, pumping lemmas and closure proprties of regular and context-free languages, non-context-free languages; Computability theory: the Church-Turing thesis, Hilbert's problem, decidability, halting problem, reducibility; Complexity theory: time and space complexity, Classes P, NP, NP-complete, PSPACE, and PSPACE-complete; Intractability: hierarchy theorem, Relativization, Circuit complexity.



1.     M. Sipser, Introduction to the Theory of Computation, Thomson, 2004.

2.     H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation, PHI, 1981.



1.     J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Narosa, 1979.

2.     S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

3.     C. H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, 1994.

4.     D. C. Kozen, Theory of Computation, Springer, 2006.

5.     D. S. Garey and G. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979.


CS 517      Self-Stabilizing Algorithms         (3-0-0-6)



Introduction to Self-stabilization, Different Models, Performance of stabilizing algorithms, Design of Basic Self-stabilizing Distributed Algorithms (Self-stabilizing BFS tree, Self-stabilizing DFS tree etc), Role of daemon (central, distributed), Distributed reset, Local Stabilization, Fault-Containment, Self-stabilization using random walk, Snap-stabilization and Superstabilization, Adaptive stabilization, Self-stabilizing algorithms for dynamic networks


Texts/ References:


1. S. Dolev, Self-Stabilization, MIT Press, 2000.

2. A. D. Kshemkalyani and M. Singhal, Distributed Computing: Principles, Algorithms, and

Systems, Cambridge University Press, 2010

3.S. Ghosh, Distributed Systems: An Algorithmic Approach, Chapman & Hall/CRC, 2010



CS 518      Algorithmic Game Theory                    (3-0-0-6)


Games and equilibria, two player Zero-Sum Games, proof of Nash Equilibria, complexity of finding Nash equilibria, information, strategies, dynamic and repeated games, bargaining, auctions, market equilibria, algorithmic mechanism design, inefficiency of equilibria, routing games, load balancing games.


Texts/ References:


1. N. Nisan, T. Roughgarden, V. Vazirani and E. Tardos, Algorithmic Game Theory,Cambridge University Press, 2007.

2. E. Rasmusen, Games and Information: An Introduction to Game Theory, 4th Edn.,Wiley-Blackwell, 2006.

3. M. J. Osborne and A. Rubinstein, A Course in Game Theory, The MIT press, 1994.

4. V. Krishna, Auction theory, Elsevier, 2002.

5. K. R. Apt and E. Graedel, Lectures in Game Theory for Computer Scientists, Cambridge University Press, 2011.

6. J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior, Princeton Univ. Press, 1944.



CS 519      Probability and Linear Algebra (3-0-0-6)


Course contents:


Combinatorial analysis, axioms of probability, conditional probability and stochastic

independence, the binomial, Poisson and normal distributions, random variables,

expectation, laws of large numbers, limit theorems, random walks, Markov chains.

Linear equations, vector spaces, linear transformations, inner products, determinants,





1. W. Feller, An Introduction to Probability Theory and its Applications, Vol. 1, 3rd Edn.,

Wiley, 1968.

2. K. Hoffman and R. Kunz, Linear Algebra, 2nd Edn., PHI, 1971.




1. S. Ross, A First Course in Probability, 6th Edn., Pearson Education India, 2002.

2. C. M. Grinstead and J. L. Snell, Introduction to Probability, 2nd Edn., Universities

Press India, 2009.

3. D. S. Watkins, Fundamentals of Matrix Computations, 2nd Edn., Wiley, 2005.

4. G. Strang, Introduction to Linear Algebra, Wellesley-Cambridge Press, 2009.



CS 520                         Combinatorial Optimization        (3-0-0-6)


Course contents:


Fundamental concepts of graphs, trees and distance, shortest paths, disjoint paths,

matchings and factors, bipartite matching and vertex cover, connectivity and paths,

vertex coloring, edge colouring, edges and cycles, planar graphs, maximum flow,

Gomory-Hu trees.




1. C. Papadimitriou and K. Steiglitz, Combinatorial optimization: algorithms and complexity, 2nd Edn.,  Dover, 1998)

2. A. Schrijver, Combinatorial Optimization, Springer-Verlag, 2002.




1. R. J. Wilson, Introduction to Graph Theory, Longman, 1985.

2. D. B. West, Introduction to Graph Theory, 2nd Edn., PHI, 2001.




CS 533      Discrete Mathematical Structures      (4-0-0-8)


Set theory: sets, relations, functions, countability; Logic: formulae, interpretations, methods of proof, soundness and completeness in propositional and predicate logic; Number theory: division algorithm, Euclid's algorithm, fundamental theorem of arithmetic, Chinese remainder theorem, special numbers like Catalan, Fibonacci, harmonic and Stirling; Combinatorics: permutations, combinations, partitions, recurrences, generating functions; Graph Theory: paths, connectivity, subgraphs, isomorphism, trees, complete graphs, bipartite graphs, matchings, colourability, planarity, digraphs; Algebraic Structures: semigroups, groups, subgroups,

homomorphisms, rings, integral domains, fields, lattices and boolean algebras.




1. C. L. Liu, Elements of Discrete Mathematics, 2nd Edn., Tata McGraw-Hill, 2000.

2. R. C .Penner, Discrete Mathematics: Proof Techniques and Mathematical Structures,

World Scientific, 1999.




1. R L Graham, D E Knuth, and O Patashnik, Concrete Mathematics, 2nd Edn.,   Addison-Wesley, 1994.

2. K. H. Rosen, Discrete Mathematics & its Applications, 6th Edn., Tata McGraw-Hill, 2007.

3. J. L. Hein, Discrete Structures, Logic, and Computability, 3rd Edn., Jones and Bartlett, 2010.

4. N. Deo, Graph Theory, Prentice Hall of India, 1974.

5. S. Lipschutz and M. L. Lipson, Schaum's Outline of Theory and Problems of Discrete Mathematics, 2/e, Tata McGraw-Hill, 1999.

6. J. P. Tremblay and R. P. Manohar, Discrete Mathematics with Applications to Computer Science, Tata McGraw-Hill, 1997.



CS 534          Approximation Algorithms      (3-0-0-6)


Prerequisites: CS 204 Algorithms or equivalent


Approximation algorithms: Set cover, max-SAT, knapsack, bin packing, scheduling, spanners, Steiner trees, cuts, clustering, facility location, traveling salesman tour, network design, metric embeddings. Design techniques: greedy, local search, dynamic programming, linear program formulations, dual fitting, primal-dual method, rounding of linear/semidefinite programs, random sampling, derandomization, power of two solutions. Lower bounds on approximations and the relevant complexity classes.




1.  D. P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms, 1st Edn., Cambridge University Press, 2011.

2.  V. V. Vazirani, Approximation Algorithms, 1st Edn., Springer, 2004.




1.  D. S. Hochbaum (Ed.), Approximation Algorithms for NP-hard Problems, Course Technology, 1996.

2.  S. Har-Peled, Geometric Approximation Algorithms, 1st Edn., American Mathematical Society, 2011.

3.  Ding-Zhu Du, Ker-I Ko, Design and Analysis of Approximation Algorithms, 1st Edn., Springer, 2012.