Skip to main content
  • Skip to main content
  • Site Map
  • Log in
  • T
  • T
-A A +A
Home
School of Computer Sciences
राष्ट्रीय विज्ञान शिक्षा एवंअनुसंधान संस्थान
National Institute of Science Education and Research

Old Website

NISER

  • Home
  • People
    • Faculty
    • Postdoc
    • Students
      • Ph.D.
  • Research
    • Publications
  • Teaching
    • Under Graduate Courses
    • PhD Course/Program
  • Activities
    • Past
      • Conference/Sympom/Worksp
      • Seminar/Colloquium
      • Meeting
  • Programs
    • Minor
    • PhD
  • Events calendar
  • Contact

Breadcrumb

  1. Home
  2. UG Elective Courses

UG Elective Courses

CS451
CS451 : Modern Cryptology
Course No:
CS451
Credit:
4
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:
  1. J. Katz and Y. Lindell, Introduction to Modern Cryptography. CRC, 2014.
CS452
CS452 : Agorithmic Coding Theory
Course No:
CS452
Credit:
4
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:
  1. T. M. Cover and J. A. Thomas, ``Elements of Information Theory''  (Second Edition, Wiley).
  2. S. Ling C. Xing, `` Coding Theory: A First Course'', Cambridge University Press.
  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.
CS453
CS453 : Complexity Theory
Course No:
CS453
Credit:
4
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:
  1.  S. Arora and B. Barak, ``Computational Complexity: A Modern Approach'', Cambridge University Press.
  2. O. Goldreich, ``Computational Complexity: A conceptual perspective'', Cambridge University Press.
  3. C. H. Papadimitriou, Computational Complexity, Pearson Education.
  4. J. Hopcroft, R. Motwani, J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Pearson Education.
CS454
CS454 : Linear Programming and Combinatorial Optimization
Course No:
CS454
Credit:
4
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:
  1. A. Schrijver, ``Theory of Linear and Integer Programming'', Wiley.
  2. A. Schrijver, ``Combinatorial Algorithm: Polyhedra and Efficiency, Volume A'', Springer.
  3. V. Vazirani, ``Approximation Algorithm'', Springer.
  4. S. Chakraborty, M. Mitra, P. Sarkar, ``A Course on Cooperative Game Theory'', Cambridge University Press.
CS455
CS455 : Distributed Network Algorithms
Course No:
CS455
Credit:
4
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:
  1. D. Peleg, ``Distributed Computing: A Locality-Sensitive Approach'', SIAM 2000.
  2. G. Pandurangan, ``Distributed Network Algorithms, a monograph'', Department of CS, University of Houston.
  3. H. Attiya,  J. Welch, ``Distributed Computing: Fundamentals", Simulations and Advanced Topics, McGraw-Hill Publishing, 1998.
  4. N. Lynch, ``Distributed Algorithms'', Morgan Kaufmann 1996.
  5. G. Tel, Introduction to Distributed Algorithms, Cambridge University Press 2000.
© 2022 School of Computer Sciences, NISER, All Rights Reserved.