# UG Elective Courses

Prerequisites CS202, CS301

Classes per week 3 Lectures + 1 Tutorial

Syllabus - Module 1: Introduction and Classical Cryptography, Perfect Secrecy, One Time Pad.
- Module 2: 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: Hash Functions and Message Authentication Codes. Notions of Security, Generic Attacks, Domain Extension techniques, CBC MAC, HMAC, PMAC, Idea of Authenticated Encryption.
- Module 4: Review of Basic Number Theory. Hardness Assumptions. One-way functions, Trapdoor Permutations, RSA assumptions, Discrete Log and Diffie Hellman Assumptions, SIS and LWE Assumptions. Introduction to Elliptic Curves (Optional)
- Module 5. Key Exchange Protocols and Key Management.
- Module 6. Public Key Encryption, Semantic Security, El Gamal Encryption, Padded RSA PKCS\#1 v1.5. Random Oracle Technique, OAEP.
- Module 7. Digital Signatures, Hash and Sign paradigm, Schnorr Signature, Forking Lemma, DSA. SSL/TLS.
- Module 8. (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 Books - J. Katz and Y. Lindell, Introduction to Modern Cryptography. CRC, 2014.

Classes per week 3 Lectures + 1 Tutorial

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

Reference Books - T. M. Cover and J. A. Thomas, ``Elements of Information Theory'' (Second Edition, Wiley).
- S. Ling C. Xing, `` Coding Theory: A First Course'', Cambridge University Press.
- J. Radhakrishnan, ``Entropy and Counting'', http://www.tcs.tifr.res.in/~jaikumar/Papers/EntropyAndCounting.pdf
- 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/
- F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland ML, 1983.

Prerequisites CS201, CS202, CS301

Classes per week 3 Lectures + 1 Tutorial

Syllabus - Module 1: 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: Cook Levin's Theorem
- Module 3: Diagonalization, Space complexity (Savitch's Theorem, Immerman-Szelepchenyi Theorem, and Reyngold's Theorem.), Polynomial Hierarchy
- Module 4: Interactive Proofs - PCP theorem and its application to approximability, Queery Complexity, Communication Complexity
- Module 5: Circuit complexity and lower bounds
- Module 6: Hardness vs. Randomness - Randomized Computation, derandomization, Pseudo-random generators
- Module 7: Polynomial identity testing vs Lower bounds for arithmetic circuits

Reference Books - S. Arora and B. Barak, ``Computational Complexity: A Modern Approach'', Cambridge University Press.
- O. Goldreich, ``Computational Complexity: A conceptual perspective'', Cambridge University Press.
- C. H. Papadimitriou, Computational Complexity, Pearson Education.
- J. Hopcroft, R. Motwani, J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Pearson Education.

Prerequisites CS202, CS301

Classes per week 3 Lectures + 1 Tutorial

Syllabus - Module 1: 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: Ellipsoid algorithm. separation oracles.
- Module 3:Semidefinite programming as an extension of linear programming.
- Module 4: LP relaxation. Examples of problems where LP relaxation achieves optimum. Examples where LP/SDP relaxation achieves approximate solution. Integrality gaps.
- Module 5: Rounding, probabilistic roundings, iterative rounding, primal dual methods.
- Module 6 (Optional): Gale-Shapley algorithm, Connection of LP to Cooperative Game Theory core, nucleolus, combinatorial optimization games.

Reference Books - A. Schrijver, ``Theory of Linear and Integer Programming'', Wiley.
- A. Schrijver, ``Combinatorial Algorithm: Polyhedra and Efficiency, Volume A'', Springer.
- V. Vazirani, ``Approximation Algorithm'', Springer.
- S. Chakraborty, M. Mitra, P. Sarkar, ``A Course on Cooperative Game Theory'', Cambridge University Press.

Prerequisites CS202, CS301

Classes per week 3 Lectures + 1 Tutorial

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

Reference Books - D. Peleg, ``Distributed Computing: A Locality-Sensitive Approach'', SIAM 2000.
- G. Pandurangan, ``Distributed Network Algorithms, a monograph'', Department of CS, University of Houston.
- H. Attiya, J. Welch, ``Distributed Computing: Fundamentals", Simulations and Advanced Topics, McGraw-Hill Publishing, 1998.
- N. Lynch, ``Distributed Algorithms'', Morgan Kaufmann 1996.
- G. Tel, Introduction to Distributed Algorithms, Cambridge University Press 2000.

Corporate Site - This is a contributing Drupal Theme

Design by

WeebPal.