MTech in Theoretical
Computer Science

Semester  1 



Semester  2 

Course Code 
Course Title 
LTPC 

Course Code 
Course Title 
LTPC 
CS 512 
Data Structures and Algorithms 
3006 

CS 515 
Theory of Computation 
3006 
CS 519 
Probability
and Linear Algebra 
3006 

CS 520 
Combinatorial
Optimization 
3006 
CS 533 
Discrete
Mathematical Structures 
4008 

XX xxx 
Elective – 2 
3006* 
XX xxx 
Elective – 1 
3006* 

XX xxx 
Elective – 3 
3006* 
CS 513 OR CS 596 
Programming Lab Seminar1 
0033 0033 

CS 597 
Seminar2 
0033 

Total 
130329* 


Total 
120327* 

Semester  3 



Semester  4 

Course Code 
Course Title 
LTPC 

Course Code 
Course Title 
LTPC 
CS 698 
Thesis 
002424 

CS 699 
Thesis 
002424 

Total 
002424 


Total 
002424 
GRAND TOTAL CREDITS 
25054104 
* 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 Selfstabilizing
Algorithms
CS
518 Algorithmic
Game Theory
CS 534 Approximation
Algorithms
Seminar1, Seminar2
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 (3006)
Prerequisites: 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.
NCreductions, Pcompleteness.
Texts:
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.
References:
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 (3006)
Prerequisites: 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, divideandconquer; Voronoi diagram and Delaunay triangulation: properties and
construction algorithms (sweep line and divideandconquer algorithms). Visibility and Art gallery problems, motion planning and shortest
paths. Arrangements and duality; Line segments intersection problem;
closest pair computation.
Texts:
1. F. P. Preparata
and M. I. Shamos, Computational Geometry: An
Introduction, SpringerVerlag, 1985.
References:
1. J. O'Rourke, Computational
Geometry in C, 2^{nd} Ed, Cambridge University Press, 1998.
2. M. Laszlo, Computational
Geometry and Computer Graphics in C++, PrenticeHall, 1996.
3. M. De Berg, M. van Kreveld, M. Overmars, O.
Schwarzkopf, Computational Geometry:
Algorithms and Applications, Springer Verlag,
1997.
CS 503 Randomized
Algorithms (3006)
Prerequisite:
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: Chisquare test, KolmogorovSmirnov test, empirical / theoretical / spectral
tests. Nonuniform 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.
Texts/References:
1. R. Motwani
and P. Raghavan, Randomized Algorithms, Cambridge University Press,
1995.
2. D. E. Knuth, The
Art of Computer Programming, 3^{rd} Ed, Vol
2, Seminumerical Algorithms, AddisonWesley, 1998.
3. W. Feller, An
Introduction to Probability Theory and its Applications, Vol 1, Wiley Eastern, 1968.
CS 505 Structural
Complexity (3006)
Models
of computation: automata, Turing machines, oracle Turing machines. Time and
space bounded computations.
Central
complexity classes: invertibility, honesty,
NPComplete Sets, PSPACEcomplete sets, padding arguments, space bounded
reducibility. Time bounded reducibility: relativized
classes, tally and sparse sets, selfreducibility. Nonuniform
complexity: Boolean circuit complexity, polynomial advice. logarithmic
advice. Selfproducible circuits. probabilistic
complexity classes. Uniform diagonalization.
The polynomial time hierarchy. Alternation,
Kolmogorov complexity.
Texts/References:
1.
J. L. Balcazar,
J. Diaz and J. Gabarro, Structural Complexity,
Vols 1 & 2, EATCS Monographs, SpringerVerlag, 1987.
2. J. Van Leeuwen, Handbook of Theoretical Computer Science, Vol A, Elsevier and MIT Press, 1990.
CS 506 Hierarchical
Memory Algorithms (3006)
Prerequisite: 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.
Texts/References:
1. J.
S. Vitter. External Memory Algorithms and Data Structures: Dealing with MASSIVE
DATA, ACM Computing Surveys, 33(2), June 2001, 209271.
2. Course
Material on External Memory Algorithms and Data Structures: http://www.brics.dk/~gerth/emF99/
3. Other
research papers.
CS 507 Logic
in Computer Science (3006)
Prerequisites: 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, EhrenfeuchtFraisse
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.
Texts:
1.
A.
Nerode and R. A. Shore, Logic for Applications,
SpringerVerlag, 1997, 2nd edition.
References:
1.
M. Huth and M. Ryan, Logic in Computer Science: Modelling and Reasoning about Systems, 2^{nd}
Ed, Cambridge University Press, 2004.
2.
M. Fitting, Firstorder Logic and automated theorem proving, SpringerVerlag, 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 (3006)
Introduction
to Linear Programming: Connections with Geometry. Simplex
Method: Duality Theorem. Complementary Slackness. Farkes Lemma. Revised Simplex Method.
General LP Problems: Infeasibility. Sensitivity Analysis.
PrimalDual 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.
Texts:
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
References:
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 (3006)
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,
MasseyOmura, 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:
QuadraticSieve Factoring Algorithm, PollardRho 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 (SHA1), Security of Hash Functions & Birthday
Attack; Digital Signatures: Authentication Protocols, Digital Signature
Standards (DSS).
Texts:
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, SpringerVerlag, New York, May 2001
References:
1.
O. Goldrich, Foundations of CryptographyBasics,
vol1, Cambridge Univ. Press, 2005.
2. O. Goldrich, Foundations of CryptographyApplications, vol2,
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 (3006)
Definitions
of randomness: statistical (MartinLoef, Solovay), based on program size complexity (Chaitin). Equivalence of the definitions.
Random
numbers: Properties of random and pseudorandom sequences. Provably secure
pseudorandom generators. Examples of pseudorandom generators: Fake OneTime
Pads, Period of a pRNG, Congruential
Generators, Feedback Shift Generators, BlumBlumShub
Generator, NaorReingold Generator. Statistical tests
for random numbers: Chisquare test, KolmogorovSmirnov
test, empirical / theoretical / spectral tests. Nonuniform
random sequences. Randomized algorithms. Derandomization
techniques.
Pseudorandom
functions and permutations. Sequences of families of
PSFs and PSPs. Applications: cryptographically strong hashing, prediction,
learning, identify friend or foe, privatekey encryption.
Texts/References:
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, SpringerVerlag, 2001.
4.
S. Goldwasser and M. Bellare,
Lecture Notes in Cryptography, http://wwwcse.ucsd.edu/~mihir/papers/gb.pdf,
2001.
5.P. Garrett, Making and
Breaking Codes: Introduction to Cryptology, PrenticeHall, 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, AddisonWesley, 1998
8.W. Feller, An
Introduction to Probability Theory and its Applications, Vol
1, Wiley Eastern, 1968
CS 511 Learning
with Kernels (3006)
Introduction: Data representation,
similarity, statistical learning theory, hyperplane 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 hyperplanes, role of margin,
optimal margin hyperplanes, nonlinear support vector classifiers, soft margin hyperplanes,multiclass hyperplanes; 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.
Texts:
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.
References:
1. J. ShaweTaylor
and N. Cristianini, Kernel Methods for Pattern
Analysis, Cambridge University Press, 2004.
2.
N. Cristianini and J. ShaweTaylor , Introduction to Support Vector Machines, CambridgeUniversity Press, 2000.
CS 512 Data
Structures and Algorithms (3006)
Performance of algorithms: space and
time complexity, asymptotics; Design techniques: the
greedy method, divideandconquer, dynamic programming; Sorting and searching;
Graph Algorithms; Priority Queues: lists, heaps, binomial heaps, Fibonacci
heaps; Hashing; Search Trees: binary search trees, redblack trees, AVL trees,
splay trees, Btrees; The disjoint set union problem; String matching; Strings:
suffix arrays, tries; Randomized data structures: skip lists; A selection of
advanced topics.
Texts:
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.
References:
1.
A. Aho, J E Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms,
AddisonWesley, 1974.
2.
S Sahni, Data
Structures, Algorithms and Applications in C++, McGrawHill, 2001.
3.
M. T. Goodrich and R. Tamassia,
Algorithm Design: Foundations, Analysis and Internet Examples, John
Wiley & Sons, 2001.
CS 513 Programming
Lab (0033)
Experiments would be designed to
provide handson experience in programming data structures and algorithms, to
learn a few systems programming tools, and scripting.
References:
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,
CS 515 Theory
of Computation (3006)
Automata and Languages: finite
automata and regular expressions, pushdown automata and contextfree grammars,
pumping lemmas and closure proprties of regular and contextfree languages,
noncontextfree languages; Computability theory: the ChurchTuring thesis,
Hilbert's problem, decidability, halting problem, reducibility; Complexity
theory: time and space complexity, Classes P, NP, NPcomplete, PSPACE, and
PSPACEcomplete; Intractability: hierarchy theorem, Relativization, Circuit
complexity.
Texts:
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.
References:
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, AddisonWesley 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 NPCompleteness,
Freeman, New York, 1979.
CS
517 SelfStabilizing
Algorithms (3006)
Introduction
to Selfstabilization, Different Models, Performance of stabilizing algorithms,
Design of Basic Selfstabilizing Distributed Algorithms (Selfstabilizing BFS
tree, Selfstabilizing DFS tree etc), Role of daemon (central, distributed),
Distributed reset, Local Stabilization, FaultContainment, Selfstabilization
using random walk, Snapstabilization and Superstabilization,
Adaptive stabilization, Selfstabilizing algorithms for dynamic networks
Texts/ References:
1. S. Dolev, SelfStabilization, 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
(3006)
Games and equilibria, two player ZeroSum 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.,WileyBlackwell,
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 (3006)
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,
eigenvalues.
Texts:
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, 2^{nd} Edn.,
PHI, 1971.
References:
1. S. Ross, A First Course in Probability, 6^{th}
Edn.,
Pearson Education India, 2002.
2. C. M. Grinstead and J. L. Snell, Introduction to Probability, 2^{nd} Edn., Universities
Press
India, 2009.
3. D. S. Watkins, Fundamentals of Matrix Computations, 2^{nd}
Edn.,
Wiley, 2005.
4. G. Strang, Introduction
to Linear Algebra, WellesleyCambridge Press, 2009.
CS 520 Combinatorial
Optimization (3006)
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,
GomoryHu
trees.
Texts:
1.
C. Papadimitriou and K. Steiglitz, Combinatorial optimization: algorithms and
complexity, 2^{nd} Edn.,
Dover, 1998)
2.
A. Schrijver, Combinatorial
Optimization, SpringerVerlag, 2002.
References:
1. R. J. Wilson, Introduction to Graph Theory, Longman, 1985.
2. D. B. West, Introduction to Graph Theory, 2^{nd}
Edn.,
PHI, 2001.
CS 533 Discrete Mathematical
Structures (4008)
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.
Texts:
1. C. L. Liu, Elements of Discrete Mathematics, 2^{nd}
Edn.,
Tata McGrawHill, 2000.
2. R. C .Penner, Discrete
Mathematics: Proof Techniques and Mathematical Structures,
World Scientific, 1999.
References:
1. R L Graham, D E
Knuth, and O Patashnik, Concrete Mathematics, 2^{nd} Edn., AddisonWesley, 1994.
2. K. H. Rosen, Discrete Mathematics & its Applications,
6^{th} Edn., Tata McGrawHill, 2007.
3. J. L. Hein, Discrete Structures, Logic, and
Computability, 3^{rd} 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 McGrawHill, 1999.
6.
J. P. Tremblay and R. P. Manohar, Discrete Mathematics with Applications to
Computer Science, Tata McGrawHill, 1997.
CS 534
Approximation Algorithms (3006)
Prerequisites:
CS 204 Algorithms or equivalent
Approximation algorithms: Set cover, maxSAT, 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, primaldual method, rounding of linear/semidefinite programs, random sampling, derandomization,
power of two solutions. Lower bounds on approximations and
the relevant complexity classes.
Texts:
1. D.
P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms, 1^{st} Edn.,
Cambridge University Press, 2011.
2.
V.
V. Vazirani, Approximation
Algorithms, 1^{st} Edn., Springer, 2004.
References:
1. D.
S. Hochbaum (Ed.), Approximation Algorithms for NPhard Problems, Course Technology,
1996.
2. S. HarPeled, Geometric
Approximation Algorithms, 1^{st} Edn., American Mathematical
Society, 2011.
3. DingZhu
Du, KerI Ko, Design
and Analysis of Approximation Algorithms, 1^{st} Edn.,
Springer, 2012.