Course: CS451

Approval: UG-Elective

Credit: 8

Description:

• Module 1: (3L+1T) Introduction and Classical Cryptography, Perfect Secrecy, One Time Pad.
• Module 2: (9L+3T) Symmetric Key Encryption. Computational Security, Concrete vs Asymptotic Approach. Semantic Security. Pseudorandom generators and Stream ciphers, Pseudorandom Functions and Block Ciphers. Practical Constructions.
• Module 3: (6L+2T) Hash Functions and Message Authentication Codes. Notions of Security, Generic Attacks, Domain Extension techniques, CBC MAC, HMAC, PMAC, Idea of Authenticated Encryption.
• Module 4: (6L+2T) Review of Basic Number Theory. Hardness Assumptions. One-way functions, Trapdoor Permutations, RSA assumptions, Discrete Log and Diffie Hellman Assumptions, SIS and LWE Assumptions. In- troduction to Elliptic Curves (Optional)
• Module 5. (3L+1T) Key Exchange Protocols and Key Management.
• Module 6. (6L+2T) Public Key Encryption, Semantic Security, El Gamal Encryption, Padded RSA PKCS#1 v1.5. Random Oracle Technique, OAEP.
• Module 7. (6L+2T) Digital Signatures, Hash and Sign paradigm, Schnorr Signature, Forking Lemma, DSA. SSL/TLS.
• Module 8. (6L+2T) (Optional) Idea of some of the following notions, Protocols and Zero Knowledge Proofs, Multiparty Computations and Oblivious Transfers, Secret Sharing. Algorithms for factoring and computing discrete logarithms, Linear and Differential Cryptanalysis, Crypto Currencies.

Reference Book

1. J. Katz and Y. Lindell, Introduction to Modern Cryptography. CRC, 2014.

Course: CS452

Approval: UG-Elective

Credit: 8

Description:

• Module 1: (9L+3T) Entropy, Characterization and Properties. Application to Combinatorics. Mutual Information and KL Divergence.
• Module 2: (6L+2T) Source coding theorem, lossless compression of data, Lempel-Ziv Algorithm, Optimal lossless coding.
• Module 3 (6L+2T) Communication channels (binary symmetric, erasure) and channel capacity, channel coding theorem.
• Module 3: (6L+2T) Introduction to Error Correcting Codes. Hamming Codes and Hamming Bounds. BCH Codes, Maximum likelihood decoding and syndrome decoding; coding theory bounds.
• Module 4: (9L+3T) Reed-Solomon codes and the Berlekamp-Welch decoding algorithm with Analysis. List Decoding of Reed-Solomon Codes.
• Module 5. (6L+2T)Reed-Muller Code and Local decoding.
• Module 6. (3L+1T) (Optional) Lovasz Local lemma and proof.

Reference Book

1. T. M. Cover and J. A. Thomas, “Elements of Information Theory”, Second Edition, Wiley, 2006.
2. S. Ling C. Xing, “ Coding Theory: A First Course”, Cambridge University Press, 2004.
3. J. Radhakrishnan, “Entropy and Counting”, http://www.tcs.tifr.res.in/ jaikumar/Papers/EntropyAndCounting.pdf
4. V. Guruswami, A. Rudra and M. Sudan, “Essential Coding Theory (Draft of a new book)” available at http://www.cse.buffalo.edu/faculty/atri/courses/coding-theory/book/
5. F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland ML, 1983.

Course: CS453

Approval: UG-Elective

Credit: 8

Description:

• Module 1 (9L+3T): Introduction, P and NP - Review of Turing machines, universal Turing machines, and uncomputable functions, P vs. NP, NP vs. co-NP, and NP-completeness, EXP, NEXP
• Module 2: (3L+1T) Cook Levin’s Theorem
• Module 3(12L+4T): Diagonalization, Space complexity, Polynomial Hierarchy
• Module 4 (9L+3T): Interactive Proofs - PCP theorem and its application to approximability
• Module 5 (4L+1T): Circuit complexity and lower bounds
• Module 6 (6L+2T): Hardness vs. Randomness - Randomized Computation, derandomization, Pseudo-random generators
• Module 7(3L+1T): Polynomial identity testing vs Lower bounds for arithmetic circuits

Reference Book

1. S. Arora and B. Barak, “Computational Complexity: A Modern Approach”, Cambridge University Press, 2007.
2. O. Goldreich, “Computational Complexity: A conceptual perspective”, Cambridge University Press, 2008.
3. J. Hopcroft, R. Motwani, J. D. Ullman. Introduction to Automata Theory, Languages, and Computation, Pearson Education, 2002.
4. J. Raddhakrishnan, Graduate course on Computational Complexity, http://www.tcs.tifr.res.in/ jaikumar/Courses/Com

Course: CS454

Approval: UG-Elective

Credit: 8

Description:

• Module 1: (10L+3T) Basic geoemetry and linear algebra related to Linear Programming. Simplex-method and Duality theorem (leading to Von Neumann’s minmax principle) and complementary slackness.
• Module 2: (8L+3T) Ellipsoid algorithm. separation oracles.
• Module 3: (9L+3T) Semidefinite programming as an extension of linear programming.
• Module 4: (9L+3T) LP relaxation. Examples of problems where LP relaxation achieves optimum. Examples where LP/SDP relaxation achieves approximate solution. Integrality gaps.
• Module 5: (6L+2T) Rounding, probabilistic roundings, iterative rounding, primal dual methods.
• Module 6 (Optional): (3L+1T) Gale-Shapley algorithm, Connection of LP to Cooperative Game Theory Combinatorial optimization games.

Reference Book

1. A. Schrijver, “Theory of Linear and Integer Programming”, Wiley, 1998.
2. A. Schrijver, “Combinatorial Algorithm: Polyhedra and Efficiency, Volume A”, Springe, 2003r.
3. V. Vazirani, “Approximation Algorithm”, Springer, 2001.
4. S. Chakraborty, M. Mitra, P. Sarkar, “A Course on Cooperative Game Theory”, Cambridge University Press, 2014.

Course: CS455

Approval: UG-Elective

Credit: 8

Description:

• Module 1: (9L+3T) Foundations of distributed network algorithms - Broadcast, converge-cast, maximal independent set, coloring, leader election, spanning tree algorithms, shortest paths, and routing.
• Module 2:(9L+3T) Fundamental concepts in distributed algorithms - Symmetry breaking, locality, synchronizers 6
• Module 3:(9L+3T) Basics of distributed network systems - Communication, synchronization, fault-tolerance, and resource allocation
• Module 4:(9L+3T) Applications to real-world networks - Internet, peer-to-peer networks, wireless networks, sensor networks and dynamic networks
• Module 5:(9L+3T) Lower bounds using communication complexity, distributed computation of large-scale data, dynamic network algorithms.

Reference Book

1. D. Peleg, “Distributed Computing: A Locality-Sensitive Approach”, SIAM 2000.
2. Distributed Computing: Fundamentals, Simulations and Advanced Topics, by Hagit Attiya, Jennifer Welch, McGraw-Hill Publishing, 1998.
3. N. Lynch, “Distributed Algorithms”, Morgan Kaufmann 1996.
4. G. Tel, Introduction to Distributed Algorithms, Cambridge University Press 2000.
5. G. Pandurangan, “Distributed Network Algorithms, a monograph”, Department of CS, University of Houston.

Course: CS456

Approval: UG-Elective

Credit: 4

Description:

• Module 1: (3L+1T) Introduction to Computational Geometry, Convex hull algorithms
• Module 2: (3L+1T) Visibility Problems: Art gallery problem, Chvátal's art gallery theorem
• Module 3: (6L+2T) Dual Transformation and Applications: Intersection of Half Planes and Duality
• Module 4: (9L+3T) Range searching: Orthogonal range searching, Priority Search Trees, Non-Orthogonal Range Searching, Half-Plane Range Query
• Module 5: (9L+3T) Voronoi Diagram: Voronoi Diagram: Properties, Fortune's algorithm, Delaunay triangulation, Voronoi diagram in higher dimension
• Module 6: (9L+3T) Point Location and Triangulation: Planar Point Location, Point Location, and Triangulation, Triangulation of Arbitrary Polygon
• Module 7: (3L+1T) VC-dimension, Epsilon-nets: Epsilon-Nets and VC Dimension, Geometric Set Cover (with Bounded VC Dimension)

Reference Book

1. Berg, M. D., Kreveld, M. V., Overmars, M., and Schwarzkopf, O., (2008), Computational Geometry: Algorithms and Applications, 3rd Edition, Springer
2. Preparata, F., and Shamos, M., (1985), Computational Geometry: An Introduction, 1st Edition, Springer-Verlag
3. Mulmuley, K., (1994), Computational Geometry: An Introduction Through Randomized Algorithms, 1st Edition, Prentice-Hall

Course: CS457

Approval: UG-Elective

Credit: 4

Description:

• Module 1 (3L+1T). Introduction to parameterized problems, parameterized algorithms, and parameterized hardness.
• Module 2 (3L+1T): The technique of bounded search tree.
• Module 3 (3L+1T). The technique of Iterative Compression.
• Module 4(3L+1T). Kernelization as a tool for polynomial-time preprocessing algorithms.
• Module 5 (9L+3T). Randomized techniques
• Module 6(9L+3T ). Advanced algorithmic techniques: Matroids, Representative Sets, etc
• Module 7 (9L+3T). Parameterized hardness and W-hierarchy.
• Module 8 (3L + 1T ) Lower bounds based on Exponential Time Hypothesis

Reference Book

1. Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S., Parameterized algorithms, 2016, 1st Edition, Springer Nature
2. Neidermeir, R., Invitation to fixed parameter algorithms, 2006, 1st Edition, OUP Oxford
3. Downey, R., and Fellows, M., Fundamentals of parameterized complexity, 2013, 1st Edition, Springer Nature

Course: CS458

Approval: UG-Elective

Credit: 4

Description:

• Module 1: (3L+1T) Lecture 1: Introduction, the notion of approximation ratio
• Module 2: (6L+2T) Greedy and combinatorial methods
• Module 3: (6L+2T) Local search
• Module 4: (9L+3T) Dynamic programming and approximation schemes
• Module 5: (9L+3T) Linear programming rounding methods (randomized, primal-dual, dual-fitting, iterated rounding)
• Module 6: (6L+2T) Semi-definite program based rounding
• Module 7: (3L+1T) Metric methods

Reference Book

1. The design of Approximation Algorithms, by David Williamson and David Shmoys, Cambridge University Press; 1st edition (2011)
2. Approximation Algorithms, by Vijay Vazirani, Springer Nature (SIE) (2013)
3. Approximation Algorithms for NP-hard Problems, edited by Dorit S. Hochbaum, Cambridge University Press; 1st edition ( 2011)

Course: CS459

Approval: UG-Elective

Credit: 4

Description:

• Module 1 (6L+2T). Introduction and Examples. Mechanism Design Basics. Algorithmic Mechanism Design.
• Module 2 (6L+2T ) Introduction to Auctions. Revenue Maximizing, Near-Optimal Auction etc.
• Module 3 (3L+1T). Spectrum Auctions.
• Module 4 (6L+2T). Mechanism Design with Payment Constraints.
• Module 5 (3L+1T). Kidney Exchange and Stable Matching
• Module 5 (9L+3T). Selfish Routing and the Price of Anarchy
• Module 7 (3L+1T). Equilibria--Definitions, Examples and Existence
• Module 8 (6L+2T) Best-Case and Strong Nash Equilibria.

Reference Book

1. Roughgarden, Twenty Lectures on Algorithmic Game Theory, 2016, 1st edition, Cambridge University Press
2. Leyton-Brown, Essentials of Game Theory, 2008, 1st edition, Morgan & Claypool Publishers
3. Yoav Shoham and Kevin Leyton-Brown, MULTIAGENT SYSTEMS Algorithmic, Game-Theoretic, and Logical Foundations, 2008, 1st edition, Cambridge University Press;
4. David Manlove, Algorithmics of Matchings under Preferences, 2013, 1st edition, WSPC
5. Brandt, Conitzer, Endriss, Lang, Procaccia, Handbook of Computational Social Choice, 2013, 1st edition, Cambridge University Press

Course: CS460

Approval: UG-Elective

Credit: 4

Description:

• Module 1 (9L + 3T): Introduction, Learning, Inductive bias, Features, Labels, Basics of statistics and probability
• Module 2(9L + 3T): Supervised learning: Linear Regression, Logistic regression. Perceptron. Naive Bayes, Support vector machines, Model selection and feature selection.,
• Module 3(9L + 3T): Ensemble methods: Bagging, boosting, Learning theory: Bias/variance tradeoff.
• Module 4(9L + 3T): Unsupervised learning: Clustering. K-means, EM. Mixture of Gaussians, Factor analysis, PCA (Principal components analysis), ICA (Independent components analysis).
• Module 5(6L + 2T): Reinforcement learning,  Value iteration and policy iteration,

Reference Book

1. Richard Duda, Peter Hart and David Stork, Pattern Classification, 2nd ed. John Wiley & Sons 2007
2. Tom Mitchell, Machine Learning. McGraw-Hill, 1st Edition, 2017
3. Richard Sutton and Andrew Barto, Reinforcement Learning: An introduction. MIT Press, 2nd Edition, 2018.
4. The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Second Edition (Springer Series in Statistics), 9th printing 2017 edition

Course: CS461/CS661

Approval: UG-Elective

Credit: 4

Description:

• Module 1(6L + 2T): Regression, classification, regularization, gradient descent
• Module 2(9L + 3T): Neural Networks - Multilayer perceptron, Backpropagation, TensorFlow
• Module 3(9L + 3T): Images - Deep Learning - Convolutional Neural Networks, motivation, architecture
• Module 4(9L + 3T): NLP - Recurrent neural networks, backpropagation through time, long short term memory, attention networks, memory networks
• Module 5(9L + 3T): Generative Models - Generative Adversarial Networks, Unsupervised learning, dimensionality reduction and visualization.

Reference Book

1. Ian Goodfellow, Yoshua Bengio and Aaron Courville. Deep Learning. 1st Edition, MIT Press 2016
2. Kevin P. Murphy. Machine Learning: A Probabilistic Perspective. 1st Edition, MIT Press 2012

Course: CS472

Approval: UG-Elective

Credit: 4

Description:

• Module 1 (12L+4T).Discrete Mathematical Structures: Groups, Rings, Fields.
• Module 2 (12L+4T).Algorithms for integer arithmetic: Divisibility, GCD, modular arithmetic, modular exponentiation, Montgomery arithmetic, congruence, Chinese remainder theorem, Hensel lifting, orders and primitive roots, quadratic residues, integer and modular square roots, prime number theorem, continued fractions and rational approximations.
• Module 3 (9L+3T).Representation of finite fields: Prime and extension fields, representation of extension fields, polynomial basis, primitive elements, normal basis, optimal normal basis, irreducible polynomials.
• Module 4 (9L+3T).Algorithms for polynomials: Root-finding and factorization, Lenstra-Lenstra -Lovasz algorithm, polynomials over finite fields.

Reference Book

1. V. Shoup, A computational introduction to number theory and algebra, 2nd edition, 2008, Cambridge University Press.
2. M. Mignotte, Mathematics for computer algebra, 1st edition, 1992, Springer.
3. J. von zur Gathen and J. Gerhard, Modern computer algebra, 3rd edition, 2013, Cambridge University Press.
4. R. Lidl and H. Niederreiter, Introduction to finite fields and their applications, 2nd edition, 1994, Cambridge University Press.
5. Alfred J. Menezes, I. F. Blake, X-H Gao, R. C. Mullin, S. A. Vanstone and T. Yaghoobian, Applications of finite fields, 1st edition, 1993, Springer.
6. J. H. Silverman and J. Tate, Rational points on elliptic curves, 1st edition, 2010, Springer.
7. D. R. Hankerson, A. J. Menezes and S. A. Vanstone, Guide to elliptic curve cryptography, 1st edition, 2010, Springer.

Text Book

1. I. N. Herstein, Topics in Algebra, 2nd edition, 2006, Wiley.
2. A. Das, Computational Number Theory, 1st edition, 2013, CRC Press.
3. S. Galbraith, Mathematics of Public Key Cryptography, 1st edition, 2011, Cambridge University Press.
4. I. Niven, H. S. Zuckerman and H. L. Montgomery, An introduction to the theory of numbers, 5th edition, 2008, Wiley.

Course: CS473

Approval: UG-Elective

Credit: 4

Description:

• Elliptic curves: The elliptic curve group, elliptic curves over finite fields, Schoof's point counting algorithm.(12L + 2T)
• Primality testing algorithms: Fermat test, Miller-Rabin test, Solovay-Strassen test, AKS test.(7L + 1T)
• Integer factoring algorithms:Trial division, Pollard rho method, p-1 method, CFRAC method, quadratic sieve method, elliptic curve method.(10L + 1T)
• Computing discrete logarithms over finite fields:Baby-step-giant-step method, Pollard rho method, Pohlig-Hellman method, index calculus methods, linear sieve method, Coppersmith's algorithm.(12L + 1T)
• Applications:Public Key Cryptography.(8L + 2T)

Reference Book

1. V. Shoup, A computational introduction to number theory and algebra, 2nd edition, 2008, Cambridge University Press.
2. M. Mignotte, Mathematics for computer algebra, 1st edition, 1992, Springer.
3. J. von zur Gathen and J. Gerhard, Modern computer algebra, 3rd edition, 2013, Cambridge University Press.
4. R. Lidl and H. Niederreiter, Introduction to finite fields and their applications, 2nd edition, 1994, Cambridge University Press.
5. Alfred J. Menezes, I. F. Blake, X-H Gao, R. C. Mullin, S. A. Vanstone and T. Yaghoobian, Applications of finite fields, 1st edition, 1993, Springer.
6. J. H. Silverman and J. Tate, Rational points on elliptic curves, 1st edition, 2010, Springer.
7. D. R. Hankerson, A. J. Menezes and S. A. Vanstone, Guide to elliptic curve cryptography, 1st edition, 2010, Springer.

Text Book

1. A. Das, Computational Number Theory, 1 edition, 2013, CRC Press.
2. S. Galbraith, Mathematics of Public Key Cryptography, 1 edition, 2011, Cambridge University Press.
3. I. Niven, H. S. Zuckerman and H. L. Montgomery, An introduction to the theory of numbers, 5th edition, 2008, Wiley.