Course: CS652

Approval: PG-Core

Credit: 8

Description:

• 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) Algebraic Algorithm like Miller Rabin, Solvay-Strassen, Berlekamp
  Algorithm.

Reference Book

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.

Course: CS653

Approval: PG-Core

Credit: 8

Description:

• 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 Book

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. J. Hopcroft, R. Motwani, J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Pearson Education.
4. C. H. Papadimitriou, Computational Complexity, Pearson Education.
5. P. Harsha, Graduate course on Computational Complexity, http://www.tcs.tifr.res.in/ prahladh/teaching/2013-14/complexity.

Course: CS654

Approval: PG-Core

Credit: 8

Description:

• 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 Book

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.
5. Matousek, Jiri, Gartner, Bernd, Understanding and Using Linear Programming, Springer.

Course: CS659

Approval: PG-Core

Credit: 8

Description:

• Module 1: Universal Hashing, Load Balancing, Locally Sensitive Hashing.
• Module 2: String Algorithms
• Module 3: Flow in Networks
• Module 4: Online Algorithms
• Module 5: Approximation Algorithms
• Module 6: Fixed Parameter Algorithms. Parameterized Complexity, Kernelization, Vertex Cover, Connection to Approximation.
• Module 7: Computational Geometry. Convex Hull, Line Segment Inersection, Sweep Lines, Voronoi Diagram.
• Module 8: Graph Sparsification. Graph Spanners, Distance Oracles.
• Module 9. Hardness and equivalences in P.

Reference Book

1. Berg, Mark de, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. New York, NY: Springer-Verlag, 2000.
2. Vijay Vazirani, Approximation Algorithms. Springer.
3. Lecture Notes and Research Papers.

Course: CS660

Approval: PG-Core

Credit: 8

Description:

• Module 1: Introduction
• Module 2: Supervised learning: Supervised learning setup. LMS , Logistic regression. Perceptron. Exponential family , Generative learning algorithms. Gaussian discriminant analysis. Naive Bayes, Support vector machines, Model selection and feature selection., Ensemble methods: Bagging, boosting, Evaluating and debugging learning algorithms.
• Module 3: Learning theory: Bias/variance tradeoff. Union and Chernoff/Hoeffding bounds. VC dimension. Worst case (online) learning. Practical advice on how to use learning algorithms.
• Module 4: Unsupervised learning: Clustering. K-means, EM. Mixture of Gaussians, Factor analysis, PCA (Principal components analysis), ICA (Independent components analysis).
• Module 5: Reinforcement learning and control: MDPs. Bellman equations. , Value iteration and policy iteration, Linear quadratic regulation (LQR) LQG, Q-learning. Value function approximation., Policy search. Reinforce. POMDPs.

Reference Book

1. Richard Duda, Peter Hart and David Stork, Pattern Classification, 2nd ed. John Wiley & Sons.
2. Tom Mitchell, Machine Learning. McGraw-Hill,.
3. Richard Sutton and Andrew Barto, Reinforcement Learning: An introduction. MIT Press

Course: CS661

Approval: PG-Core

Credit: 8

Description:

• Module 1: Review of discrete probability spaces – Basic probability theory (Events, Expectation, Variance, Markov, Chebyshev, and moment inequalities), Simple randomized algorithms analysis (Randomized Quicksort, polynomial identity, min-cut algorithm, median algorithm), Naïve Bayesian classifier
• Module 2: Basic concentration bounds – Chernoff and Hoeffding, Applications (Set balancing, network packet routing, etc.)
• Module 3: The occupancy problem – Balls Into Bins, Hashing, Fingerprinting and random graphs
• Module 4: The Probabilistic Method – MAX-SAT, conditional expectations, Lovazs Local Lemma, explicit constructions
• Module 5: Martingales and concentration bounds
• Module 6: Markov Chains and the Monte Carlo method, Rapidly mixing chains and the coupling method
• Module 7: Foundations of Machine Learning – Sample Complexity, PAC learning, VC-dimension, Rademacher complexity

Reference Book

1. M. Mitzenmacher, E. Upfal, “Probability and Computing: Randomized algorithms and probabilistic analysis”, Cambridge University Press, 2005 (2nd Edition July, 2017).
2. R. Motwani, P. Raghavan, “Randomized Algorithms”, Cambridge University Press, 2004.
3. Dubhashi, Panconesi, “Concentration of Measure for the Analysis of Randomized Algorithms”.
4. Alon, Spencer, “The Probabilistic Method”.
5. Levin, Peres, Wilmer, “Markov Chains and Mixing Times”.
6. William Feller. “An introduction to Probability Theory and Its Applications”, Volumes I and II, John Wiley, New York, 1968.

Course: CS651

Approval: PG-Core

Credit: 8

Description:

• 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 Book

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

Course: CS655

Approval: PG-Core

Credit: 8

Description:

• 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 Book

1. D. Peleg, “Distributed Computing: A Locality-Sensitive Approach”, SIAM 2000.
2. H. Attiya, J. Welch, “Distributed Computing: Fundamentals, Simulations and Advanced Topics”,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: CS656

Approval: PG-Core

Credit: 8

Description:

• Module 1: Introduction to Computer Forensics: computer crimes, evidence, extraction, preservation, etc..
• Module 2: Overview of hardware and operating systems: structure of storage media/devices; windows/Macintosh/ Linux – registry, boot process, file systems, file metadata.
• Module 3: Data and File System Analysis: identifying hidden data, Encryption/Decryption, Steganography, recovering deleted files.
• Module 4: Windows Systems and Artifacts: uncovering attacks that evade detection by Event Viewer, Task Manager, and other Windows GUI tools, data acquisition, disk imaging, recovering swap files, temporary & cache files
• Module 5: Linux Systems and Artifacts: File system layers, linux boot process and services, system organization and artifacts, logs and task scheduling
• Module 6: Mac Artifacts: File system, system artifacts, user artifacts
• Module 7: Internet Artifacts: Browser artifacts, mail artifacts
• Module 8: File Analysis: Images, audio, video, archives and documents
• Module 9: Automating analysis and extending capabilities: Graphical investigation environments, automating artifact extraction, timelines.
• Module 10: Mobile Network Forensic: Introduction, Mobile Network Technology, Investigations, Collecting Evidence, Where to seek Digital Data for further Investigations, Interpretation of Digital Evidence on Mobile Network.
• Module 11: Computer crime and Legal issues: Intellectual property, privacy issues, Criminal Justice system for forensic, audit/investigative situations and digital crime scene, investigative procedure/standards for extraction, preservation, and deposition of legal evidence in a court of law.

Reference Book

1. Cory Altheide , Harlan Carvey , Ray Davidson, ”Digital Forensics with Open Source Tools”, Syngress Publishing; 1 edition (April 28, 2011)
2. Albert J. Marcella Jr., Frederic Guillossou ”Cyber Forensics: From Data to Digital Evidence”, Wiley Publication
3. Marjie T. Britz, ”Computer Forensics and Cyber Crime: An Introduction”, (3rd Edition) 2013

Course: CS657

Approval: PG-Core

Credit: 8

Description:

• Module 1: Penetration Testing: What You Should Know, Getting Comfortable with Kali Linux
• Module 2: The Essential Tools: Netcat, Ncat, Wireshark, Tcpdump
• Module 3: Passive Information Gathering: Open Web information gathering, Emailharvesting
• Module 4: Active Information Gathering: DNS enumeration, port scanning, SMB enumeration, SNMP enumeration
• Module 5: Vulnerability Scanning, Buffer Overflows, Win32 Buffer Overflow Exploitation, Linux Buffer Overflow Exploitation
• Module 6: Working with Exploits, File Transfers, Privilege Escalation
• Module 7: Client Side Attacks: Know Your Target, MS12-037- Internet Explorer 8 Fixed Col Span ID, Java Signed Applet Attack
• Module 8: Web Application Attacks: Cross Site Scripting (XSS), File Inclusion Vulnerabilities, MySQL SQL Injection, Web Application Proxies
• Module 9: Password Attacks: Preparing for Brute Force, Online Password Attacks, Password Hash Attacks
• Module 10: Port Redirection and Tunneling: SSH Tunneling, Proxychains
• Module 11: The Metasploit Framework: Metasploit Payloads, Building Your Own MSF Module, Post Exploitation with Metasploit, Bypassing Antivirus Software

Reference Book

1. Hacking Exposed 7: Network Security Secrets and Solutions, Stuart McClure, Joel Scambray, George Kurtz, 2012, McGraw Hill, ISBN 978-0-07-178028-5.
2. Penetration Testing: A Hands-On Introduction to Hacking, Georgia Weidman, No Starch Press

Course: CS658

Approval: PG-Core

Credit: 8

Description:

• Module 1: Introduction and the Bowtie Structure of the Web
• Module 2: Basic Network Properties and the Random Graph Model
• Module 3: The Small World Phenomena, Decentralized search in small-world and P2P networks
• Module 4: User Evaluations in Social Media
• Module 5: Cascading Behavior: Decision Based Models of Cascades, Cascading Behavior: Probabilistic Models of Information Flow
• Module 6: Influence Maximization, Outbreak Detection
• Module 7: Power-laws and Preferential attachment
• Module 8: Link Analysis: HITS and PageRank
• Module 9: Strength of weak ties and Community structure in networks, Network community detection: Modularity optimization and Spectral Clustering, Overlapping communities in networks
• Module 10: Link Prediction and Network Inference, Biological networks

Reference Book

1. Networks, Crowds, and Markets: Reasoning About a Highly Connected World by David Easley and Jon Kleinberg.
2. Networks: An introduction by Mark Newman