MTech in Theoretical
Computer Science
|
|
Semester - 1 |
|
|
|
Semester - 2 |
|
|
Course Code |
Course Title |
L-T-P-C |
|
Course Code |
Course Title |
L-T-P-C |
|
CS 512 |
Data Structures and Algorithms |
3-0-0-6 |
|
CS 515 |
Theory of Computation |
3-0-0-6 |
|
CS 519 |
Probability
and Linear Algebra |
3-0-0-6 |
|
CS 520 |
Combinatorial
Optimization |
3-0-0-6 |
|
CS 533 |
Discrete
Mathematical Structures |
4-0-0-8 |
|
XX xxx |
Elective – 2 |
3-0-0-6* |
|
XX xxx |
Elective – 1 |
3-0-0-6* |
|
XX xxx |
Elective – 3 |
3-0-0-6* |
|
CS 513 OR CS 596 |
Programming Lab Seminar-1 |
0-0-3-3 0-0-3-3 |
|
CS 597 |
Seminar-2 |
0-0-3-3 |
|
|
Total |
13-0-3-29* |
|
|
Total |
12-0-3-27* |
|
|
Semester - 3 |
|
|
|
Semester - 4 |
|
|
Course Code |
Course Title |
L-T-P-C |
|
Course Code |
Course Title |
L-T-P-C |
|
CS 698 |
Thesis |
0-0-24-24 |
|
CS 699 |
Thesis |
0-0-24-24 |
|
|
Total |
0-0-24-24 |
|
|
Total |
0-0-24-24 |
|
GRAND TOTAL CREDITS |
25-0-54-104 |
* 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.
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 (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.
Texts:
1. F. P. Preparata
and M. I. Shamos, Computational Geometry: An
Introduction, Springer-Verlag, 1985.
References:
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.
Texts/References:
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)
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.
Texts/References:
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.
Texts/References:
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: http://www.brics.dk/~gerth/emF99/
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.
Texts:
1.
A.
Nerode and R. A. Shore, Logic for Applications,
Springer-Verlag, 1997, 2nd edition.
References:
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.
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 (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).
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, Springer-Verlag, New York, May 2001
References:
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.
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, Springer-Verlag, 2001.
4.
S. Goldwasser and M. Bellare,
Lecture Notes in Cryptography, http://www-cse.ucsd.edu/~mihir/papers/gb.pdf,
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.
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. 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.
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,
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.
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 (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.
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, 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,
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, 2nd Edn.,
PHI, 1971.
References:
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.
Texts:
1.
C. Papadimitriou and K. Steiglitz, Combinatorial optimization: algorithms and
complexity, 2nd Edn.,
Dover, 1998)
2.
A. Schrijver, Combinatorial
Optimization, Springer-Verlag, 2002.
References:
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.
Texts:
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.
References:
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.
Texts:
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.
References:
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.