|E0 219 (3:1)
||Linear Algebra and Applications
||R. Vittal Rao / Dilip P. Patil
Vector Spaces : Subspaces, Linear independence, Basis and dimension, orthogonality. Matrices : Solutions of linear equations, Gaussian elimination, Determinants, Eigenvalues and Eigenvectors, Characteristic polynomial, Minimal polynomial, Positive definite matrices and Canonical forms. Singular Value Decomposition, Applications.
- G Strang, Linear Algebra and Applications, Thomson-Brooks/Cole, 4th edition, 2006.
Vertex cover, matching, path cover, connectivity, hamiltonicity, edge colouring, vertex colouring, list colouring; Planarity, Perfect graphs; other special classes of graphs; Random graphs, Network flows, Introduction to Graph minor theory
- Reinhard Diestel, "Graph Theory", Springer (2010)
- Douglas B. West, "Introduction to Graph Theory", Prentice Hall (2001)
- A. Bondy and U. S. R. Murty, "Graph Theory", Springer (2008)
- B. Bollabas, "Modern Graph Theory", Springer (1998)
Basic Mathematical Notions: Logic, Sets, Relations, Functions, Proofs; Abstract Orders: Partial Orders, Lattices, Boolean Algebra, Well Orders.;Counting & Combinatorics: Pigeonhole Principle, The Principle of Inclusion and Exclusion, Recurrence Relations, Permutations and Combinations, Binomial Coefficients and Identities; Number Theory: Mathematical Induction, Divisibility, The Greatest Common Divisor, The Euclidean Algorithm, Prime Numbers, integers, Fundamental Theorem of Arithmetic, Modular Arithmetic, Arithmetic with a Prime Modulus, Arithmetic with an Arbitrary Modulus, The RSA Algorithm; Groups and Fields: Basics, Isomorphism theorems, Chinese Remainder Theorem, Finite Fields; Graph Theory: Graph Terminology and Special Types of Graphs, Bipartite Graphs and Matching, Representation of Graphs, Connectivity, Euler and Hamilton Paths and Cycles, Planar Graphs, Graph Coloring, Trees.
- Laszlo Lovasz, Jozsef Pelikan, Katalin L. Vesztergombi: Discrete Mathematics, Springer 2003.
- Graham,R.L., Knuth, D.E. and Patashnik, O: Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley Professional; 2 edition, 1994.
- Herstein I N : Topics in Algebra, 2 ed., Wiley India 1975.
Automata and Logic, including Buchi's logical characterization of regular languages,automata-based decision procedures for logics of natural numbers with order (N,<), Presburger logic, and algebraic approach to regular languages.Pushdown Systems, including Parikh's theorem, Reachability in pushdown systems,Deterministic PDA's and complementation, Visibly Pushdown Automata, and decidability results for PDA's and subclasses like Counter Automata. Automata on infinite words, including closure properties, and Deterministic Buchi automata.Automata on Trees, including closure properties, decision procedures, congruences and minimization.Extended topics, including Schutzenberger-McNaughton-Papert Theorem, automata on partial-orders, distributed automata, and automata in description and analysis of infinite-state transition systems
- Hopcroft J.E. and Ullman J.D.: Introduction to Automata, Languages and Computation. Addison Wesley, 1979.
- Dexter Kozen: Automata and Computability. Springer 1999.
- Wolfgang Thomas: Automata on infinite objects, in Handbook of Theoretical Computer Science, Volume B, Elsevier, 1990.
- Deepak D'Souza and Priti Shankar (Eds): Modern Applications of Automata Theory,World Scientific, 2012.
- Research papers.
(1) Formal models of systems: labelled state transition diagrams for concurrent processes and protocols, timed and hybrid automata for embedded and real-time systems. (2) Specification logics: propositional and first-order logic; temporal logics (CTL, LTL, CTL*); fixpoint logic: mu-calculus. (3) Algorithmic analysis: model checking, data structures and algorithms for symbolic model checking, decision procedures for satisfiability and satisfiability modulo theories. (4) Tools: Student projects and assignments involving model checking and satisfiability tools e.g. zChaff, SPIN, NuSMV, Uppaal.
- Michael Huth, Mark Ryan: Logic in Computer Science: Modelling and Reasoning about Systems, Cambridge University Press, 2004.
- Edmund M. Clarke, Orna Grumberg, Doron Peled: Model Checking, MIT Press, 2001.
- Daniel Kroening, Ofer Strichman: Decision Procedures: An Algorithmic Point of View, Springer, 2008.
- Basics of data structures, algorithms, and automata theory.
Computational complexity theory is the fundamental subject of classifying computational problems based on their `complexities'. In this context, `complexity' of a problem is a measure of the amount of resource (time/space/random bits, or queries) used by the best possible algorithm that solves the problem. The aim of this course is to give a basic introduction to this field. Starting with the basic definitions and properties, we intend to cover some of the classical results and proof techniques of complexity theory.
Introduction to basic complexity classes; notion of `reductions' and `completeness'; time hierarchy theorem & Ladner's theorem; space bounded computation; polynomial time hierarchy; Boolean circuit complexity; complexity of randomized computation; interactive proofs; complexity of counting.
- The book titled `Computational Complexity - A Modern Approach' by Sanjeev Arora and Boaz Barak.
- Lecture notes of similar courses as and when required.
- Basic familiarity with undergraduate level theory of computation and data structures & algorithms would be helpful.
- More importantly, some mathematical maturity with an inclination towards theoretical computer science.
Review of basic data structures, searching, sorting. Algorithmic paradigms, e.g., greedy algorithms, divide and conquer strategies, dynamic programming. Advanced data structures. Graph algorithms. Geometric algorithms, Randomized algorithms. NP and NP-completeness.
- Jon Kleinberg and Ã‰va Tardos, Algorithm Design, Addison Wesley, 2005.
- Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein C, Introduction to Algorithms, 2nd Edition, Prentice Hall, 2001.
- Aho, A.V., Hopcraft J.E., and Ullman, J.D., Design and Analysis of Algorithms, Addison-Wesley, 1974.
Linear Algebra: System of Linear Equations, Vector Spaces, Linear Transformations, Matrices, Polynomials, Determinants, Elementary Canonical Forms, Inner Product Spaces, Orthogonality. Probability: Probability Spaces, Random Variables, Expectation and Moment generating functions, Inequalities, Some Special Distributions. Limits of sequence of random variables, Introduction to Statistics, Hypothesis testing.
- Gilbert Strang, Linear Algebra and its Applications, Thomson-Brooks/ Cole, 4th edition, 2006.
- Hoffman and Kunze, Linear Algebra, Prentice Hall, 2nd edition, 1971.
- Kishor S. Trivedi, Probability and Statistics with Reliability, Queueing, and Computer Science Applications, Wiley, 2nd edition, 2008.
- Vijay K. Rohatgi, A. K. Md. Ehsanes Saleh, An Introduction to Probability and Statistics, Wiley, 2nd edition, 2000.
- Kai Lai Chung, Farid Aitsahlia, Elementary Probability Theory, Springer, 4th edition, 2006.
Semantics of programs: denotational semantics, operational semantics, Hoare logic. Dataflow analysis: Computing join-over-all-paths information as the least solution to a set of equations that model the program statements, analysis of multi-procedure programs. Abstract interpretation of programs: Correctness of abstract interpretation, Galois connections, dataflow analysis as an abstract interpretation. Type inference: Hindley-Milner's type inference algorithm for functional programs, subset-based and unification-based type inference for imperative programs. Pointer analysis.
- Flemming Nielson, Hanne Riis Nielson, and Chris Hankin: Principles of Program Analysis, Springer, (Corrected 2nd printing, 452 pages, ISBN 3-540-65410-0), 2005.
- Benjamic Pierce: Types and Programming Languages, Prentice-Hall India, 2002.
- Research papers
Basic combinatorial numbers, selection with repetition, pigeon hole principle, Inclusion-Exclusion Principle, Double counting; Recurrence Relations, Generating functions; Special combinatorial numbers: Sterling numbers of the first and second kind, Catalan numbers, Partition numbers; Introduction to Ramsey theory; Combinatorial designs, Latin squares; Introduction to Probabilistic methods, Introduction to Linear algebra methods.
- R. P. Grimaldi, B. V. Ramana, "Discrete and Combinatorial Mathematics: An applied introduction", Pearson Education (2007)
- Richard A Brualdi, "Introductory Combinatorics", Pearson Education, Inc. (2004)
- Miklos Bona, "Introduction to Enumerative Combinatorics", Mc Graw Hill (2007)
- Miklos Bona, "A walk through Combinatorics: An introduction to enumeration and graph theory", World Scientific Publishing Co. Pvt. Ltd. (2006)
- J. H. Vanlint, R. M. Wilson, "A course in Combinatorics", Cambridge University Press (1992, 2001)
- Stasys Jukna, "Extremal Combinatorics: With applications in computer science", Springer-Verlag (2001)
- Noga Alon, Joel H. Spencer, P. Erdos, "The Probabilistic methods", Wiley Interscience Publication
- Laszlo Babai and Peter Frankl, "Linear Algebra Methods in Combinatorics, with Applications to Geometry and Computer Science" (Unpublished Manuscript, 1992)
- None. (A very basic familiarity with probability theory and linear algebra is preferred, but not a must. The required concepts will be introduced quickly in the course.)
|E0 229 (3:1)
||Foundations of Data Science
||Ravi Kannan / Ramesh Hariharan / Navin Goyal
High Dimensional Geometry,SVD and applications,Random Graphs,Markov Chains, Algorithms in Machine Learning, Clustering,Massive data and Sampling on the fly
- Foundations of Data Science by Hopcroft and Kannan
- Basic Linear Algebra, Basic Probability.
Need for unconstrained methods in solving constrained problems. Necessary conditions of unconstrained optimization, Structure of methods, quadratic models. Methods of line search, Armijo-Goldstein and Wolfe conditions for partial line search. Global convergence theorem, Steepest descent method. Quasi-Newton methods: DFP, BFGS, Broyden family. Conjugate-direction methods: Fletcher-Reeves, Polak-Ribierre. Derivative-free methods: finite differencing. Restricted step methods. Methods for sums of squares and nonlinear equations. Linear and Quadratic Programming. Duality in optimization.
- Fletcher R., Practical Methods of Optimization, John Wiley, 2000.
Basic algebraic notions: Integers, Euclidean algorithm, division algorithm, ring and polynomial rings, abstract orders and Dicksonâ€™s lemma; Introduction to GrÃ¶bner bases: Term orders, multivariate division algorithm, Hilbert basis theorem, GrÃ¶bner bases and Buchberger algorithm, computation of syzygies, basic algorithms in ideal theory, universal GrÃ¶bner bases; Algebraic Applications: Hilbert nullstellensatz, implicitization, decomposition, radical and zeros of ideals; Other applications: Toric ideals and integer programming, applications to graph theory, coding, cryptography, statistics.
- Ideals, Varieties and Algorithms by D. Cox and Oâ€™Shea, Springer; 2nd ed. 1997.
- Algorithmic Algebra by Bhubaneswar Mishra, Springer, 1993.
Probability spaces and continuity of probability measures, random variables and expectation, moment inequalities, multivariate random variables, sequence of random variables and different modes of convergence, law of large numbers, Markov chains, statistical hypothesis testing, exponential models, introduction to large deviations.
- An Introduction to Probability and Statistics by Vijay K. Rohatgi, A. K. Md. Ehsanes Saleh, Wiley, 2nd edition 2000.
- An Intermediate course in Probability, by Allen Gut, Springer, 2008.
Data compression and Kraft's inequality, source coding theorem and Shannon entropy, Kullback-Leibler divergence and maximum entropy, I-projections and Sanov theorem, Kullback- siszar iteration and iterative scaling algorithms, Fisher information and Cramer-Rao inequality, quantization and introduction to rate distortion theory, generalized information measures and power-law distributions.
- Elements of Information Theory, by T. M. Cover and J. A. Thomas, John Wiley & Sons, 2nd edition, 2006.
- Information Theory, Inference, and Learning Algorithms by D.J.C. MacKay, Cambridge University Press, 2003.
Basic concepts in probability theory - event, random variables, distribution, expectations etc.; Moments and Deviations; Tail inequalities; The Probabilistic method; Markov chains and random walks; Entropy: A measure of randomness; Algebraic techniques.
- Randomized Algorithms books by Motwani and Raghavan
- Probability and Computing book by Mitzenmacher and Upfal
- An undergraduate course on Algorithms and Probability theory will be helpful.
Elementary number theory, Finite fields, Arithmetic and algebraic algorithms, Secret key and public key cryptography, Pseudo random bit generators, Block and stream ciphers, Hash functions and message digests, Public key encryption, Probabilistic encryption, Authentication, Digital signatures, Zero knowledge interactive protocols, Elliptic curve cryptosystems, Formal verification, Cryptanalysis, Hard problems.
- Stinson. D. Cryptography: Theory and Practice.
- Menezes. A. et. al. Handbook of Applied Cryptography, CRC Press,1996.
Information retrieval using the Boolean model. The dictionary and postings lists. Tolerant retrieval. Index construction and compression. Vector space model and term weighting. Evaluation in information retrieval. Relevance feedback and query expansion. Probabilistic information retrieval. Language models for information retrieval. Text classification and clustering. Latent semantic indexing. Web search basics. Web crawling and indexes. Link analysis.
- C. D. Manning, P. Raghavan, and H. Schutze, Introduction to Information Retrieval, Cambridge University Press, 2008.
- Recent Literature
Concepts of Agency and Intelligent Agents. Action of Agents, Percepts to Actions. Structure of Intelligent Agents, Agent Environments, Communicating, Perceiving, and Acting. Concepts of Distributed AI, Cooperation, and Negotiation. Applications: Web-based Agents, Database Applications. Agent Programming
- S. Russel and P. Norvig, Artificial Intelligence - A Modern Approach, Prentice Hall, 1995.
- Recent Papers
Introduction to Artificial Intelligence, Problem solving, knowledge and reasoning, Logic, Inference, Knowledge based systems, reasoning with uncertain information, Planning and making decisions, Learning, Distributed AI, Communication, Web based agents, Negotiating agents, Artificial Intelligence Applications and Programming.
- S. Russel and P. Norvig, Artificial Intelligence - A Modern Approach, Prentice Hall, 1995.
- George F. Luger, Artificial Intelligence, Pearson Education, 2001.
- Nils J. Nilsson, Artificial Intelligence - A New Synthesis, Morgan Kaufmann Publishers, 2000
Our dependence on software is increasing at a phenomenal rate. As a consequence, the concerns about reliability of software in terms of correctness and security are taking the center stage. In this course, we study the state-of-the-art techniques for analyzing and improving software reliability. Our focus will be on: (1) understanding the dominant models of concurrent programming and formal reasoning for them and (2) understanding the nature and causes of security vulnerabilities and techniques to detect them. We will study concurrency and security issues related to smartphone and web programming in addition to more traditional software issues.
- Programming Android, Zigurd Mednieks, Laird Dornin, G. Blake Meike and Masumi Nakamura, O'Reilly, 2011.
- Even Faster Websites, Steve Souders, O'Reilly, 2009.
- Additional research papers.
Introduction to Probability theory, Random variables, commonly used continuous and discrete distributions. Introduction to Stochastic Process, Poisson process, Markov chains, steady stateand transient analysis. Psuedo random numbers: Methods of Generation and testing. Methods for generating continuous and discrete distributions. Methods for generating Poisson Process. Building blocks of Simulation, Data Structures and Algorithms. Introduction to Probabilistic modelling, Maximum Likelihood Variance reduction techniques: antithetic variates, control variates, common random numbers, importance sampling. Analysis of Simulation results: confidence intervals, design of experiments. Markov Chain Monte Carlo techniques.
- Sheldon M. Ross: Introduction to Probability Models 7th Edition, Academic Press, 2002
- Donald E. Knuth: The Art of Computer Programming - Volume 2: Semi Numerical Algorithms, 2nd Edition, Addison Wesley, Reading MA, USA 2000
- Sheldon M. Ross Simulation 3rd Edition, Academic Press, 2002
- A. M. Law and W. D. Kelton: Simulation Modeling and Analysis, 3rd Edition, McGrawHill, New York, USA, 1998
- Raj Jain The Art of Computer Systems Performance Analysis, John Wiley and Sons, New York, USA, 1991
Introduction to computer networks; telephone networks, networking principles; switching - circuit switching, packet switching; scheduling - performance bounds, best effort disciplines, naming and addressing, protocol stack, SONET/SDH; ATM networks - AAL, virtual circuits, SSCOP; Internet - addressing, routing, end point control; Internet protocols - IP, TCP, UDP, ICMP, HTTP; performance analysis of networks - discrete and continuous time Markov chains, birth-death processes, time reversibility, queueing / delay models - M/M/1, M/M/m, M/M/m/m, M/G/1 queues, infinite server systems; open and closed queueing networks, Jackson's theorem, Little's law; traffic management - models, classes, scheduling; routing algorithms - Bellman Ford and Dijkstra's algorithms; multiple access, frequency and time division multiplexing; local area networks - Ethernet, token ring, FDDI, CSMA/CD, Aloha; control of networks - QoS, window and rate congestion control, open and closed loop flow control, large deviations of a queue and network, control of ATM networks.
- I. Mitrani, Modelling of Computer and Communication Systems, Cambridge, 1987.
- J.Walrand and P.Varaiya, High Performance Communication Networks, Harcourt Asia (Morgan Kaufmann), 2000.
- S.Keshav, An Engineering Approach to Computer Networking, Pearson Education, 1997.
- D.Bertsekas and R.Gallager, Data Networks, Prentice Hall of India, 1999.
- J.F.Kurose and K.W.Ross, Computer Networking: A Top-Down Approach Featuring the Internet, Pearson Education, 2001.
Review of Probability theory: Random variables, Expectation, Central Limit theorem. Latent variable models: mixture models, HIdden Markov models, EM algorithm, Graphical models: Algorithms for Inference, Markov Chain Monte Carlo Methods, Belief Propagation, Variational methods Factor Analysis. Applications to Text: Maxent Formalism, Statistical Parsing, CKY algorithm, Topic models.
- Sheldon Ross - Introduction to Probability theory
- C. Bishop - Pattern Recognition
- J. Pearl: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference
- C. Manning and H. Schutzle - Foundations of Statistical Natural Language Processing
Processor Architecture: Instruction-Level Parallelism, Superscalar and VLIW architecture; Multi-core processors; Memory Subsystem: Multilevel caches, Caches in multi-core processors, Memory controllers for multi-core systems; Multiple processor systems: taxonomy, distributed and shared memory system, memory consistency models, cache coherence, and Interconnection networks; Advanced topics in architecture.
- Hennessy, J.L., and Patterson, D.A.: Computer Architecture, A quantitative Approach, Morgan Kaufmann.
- Current literature
Voronoi diagram, Delaunay triangulation, Geometric Data Structures â€” Interval tree, Range tree, Segment tree. Complexes â€” simplicial complex, Rips complex, alpha complex, homology, Betti numbers, persistence homology, Morse functions, Reeb graph, approximation and fixed parameter algorithms for geometric problems - hitting set and set cover, epsilon nets, epsilon approximations, geometric intersection graphs, geometric discrepancy, clustering.
- Computational Topology : An Introduction, Herbert Edelsbrunner and John L. Harer, American Mathematical Society, Indian Edition, 2010.
- Computational Geometry: Algorithms and Applications, Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, Third Edition, Springer (SIE), 2011.
- Geometric Approximation Algorithms, Sariel Har-Peled, American Mathematical Society, Indian Edition, 2013.
- E0225 : Design and Analysis of Algorithms
Redundancy techniques, fault coverage, computational integrity, fault detection methods fault identification algorithms, exception handling, damage assessment and confinement, system diagnosability, diagnosis algorithms, system recovery and distribution, reconfiguration techniques, repairable systems, algorithms based fault tolerance testing techniques, test scheduling, test pattern generation, fault tolerant computer communication networks, fault tolerance of software.
- Anderson, L., and Lee, P. A., Fault Tolerance, Principles and Practice, Prentice Hall, 1981.
- Siework, C. P. and Swartz, R. S., Theory and Practice of Reliable System Design, Mc-Graw Hill, 1982.
- Current Literature.
Hard and soft real-time systems, deadlines and timing constraints, workload parameters, periodic task model, precedence constraints and data dependency, real time scheduling techniques, static and dynamic systems, optimality of EDF and LST algorithms, off-line and on-line scheduling, clock driven scheduling, cyclic executives, scheduling of aperiodic and static jobs, priority driven scheduling, fixed and dynamic priority algorithms, schedulable utilization, RM and DM algorithms, priority scheduling of aperiodic and sporadic jobs, deferrable and sporadic servers, resource access control, priority inversion, priority inheritance and priority ceiling protocols, real-time communication, operating systems.
- Jane W. S. Liu, Real-Time Systems, Pearson Education, New Delhi, 2001.
- Current literature
Basic concepts and issues, survey of applications of sensor networks, homogeneous and heterogeneous sensor networks, topology control and clustering protocols, routing and transport protocols, access control techniques, location awareness and estimation, security information assurance protocols, data fusion and management techniques, query processing, energy efficiency issues, lifetime optimization, resource management schemes, task allocation methods, clock synchronization algorithms. Tiny operating system, middleware support, simulation packages.
- C. S. Raghavendra, K. M. Shivalingam and T. Znati, Wireless Sensor Networks, Springer, New York, 2004.
- F. Zhao and L.Guibas, Wireless Sensor Networks, An Information processing Approach, Morgan Kauffmann, San Fransisco 2004.
- Current literature
|E0 248 (3:1)
||Theoretical Foundations of Cryptography
One-way functions, indistinguishability, pseudo-random generators, pseudo-random functions, trapdoor permutations, encryption, digital signatures, hash functions, commitments and some special topics (private information retrieval, zero-knowledge proofs etc.).
- Oded Goldreich, Foundations of Cryptography: Volumes 1 and 2, Cambridge University Press, 2001 and 2004.
- Prerequisites: Mathematical maturity
Greedy algorithms; Local search; Linear programs (relaxations and rounding); Iterated rounding; Primal dual algorithms; Randomized rounding; Semidefinite programming; Sparsest cut and metric embeddings; Label cover; Unique games.
- "The Design of Approximation Algorithms" by David Shmoys and David Williamson".
- Approximation Algorithms and Semidefinite Programming" by Bernd GÃƒrtner and Jiri Matousek - Research papers.
- E0225: Design and Analysis of Algorithms.
Most of the machine learning algorithms give very good accuracies provided one feeds the algorithms with as set of `handpicked' features that are extracted from the data. To automate this task, one has to take a recourse to `deep' models'. In recent years deep architectures have gained a lot of prominence for learning complex AI tasks. This course will cover basic deep learning techniques and how to apply these to solve challenging problems in computer vision and speech.
- Basics: Maximum entropy and exponential family, Ising models, Boltzmann machines, Gibbs sampling, variational inference. Unsupervised feature learning: Restricted Boltzmann machines (RBM), Gaussian RBMs, Contrastive divergence, Deep Boltzmann machines, Autoencoders, Denoising, Recursive, Sparse coding. Supervised feature learning: Neural networks and back propagation algorithm, Convolutional Neural networks, Recurrent neural network, Deep belief networks.
- Yoshua Bengio, Learning Deep Architectures for AI, Now Publishers, 2009.
- Kevin Murphy, Machine Learning - A Probabilistic Perspective, MIT Press, 2012.
- Li Deng and Dong Yu, Deep Learning: Methods and Applications, Now Publishers, 2014.
Abstract data types and data structures, Classes and objects, Complexity of algorithms: worst case, average case, and amoritized complexity. Algorithm analysis. Algorithm Design Paradigms. Lists: stacks, queues, implementation, garbage collection. Dictionaries: Hash tables, Binary search trees, AVL trees, Red-Black trees, Splay trees, Skip-lists, B-Trees. Priority queues. Graphs: Shortest path algorithms, minimal spanning tree algorithms, depth-first and breadth-first search. Sorting: Advanced sorting methods and their analysis, lower bound on complexity, order statistics.
- A.V. Aho, J.E. Hopcroft, and J.D. Ullman, Data Structures and Algorithms, Addison Wesley, Reading Massachusetts, USA, 1983.
- T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, The MIT Press, Cambridge, Massachusetts, USA, 1990.
- M.A. Weiss, Data Structures and Algorithms Analysis in C++, Benjamin/Cummins, Redwood City, California, USA, 1994.
Features and implementation of imperative, object-oriented, concurrent, distributed, logicprogramming, functional, aspect-oriented, scripting, business-oriented and web programming languages. Example languages from each of the above categories would be discussed along with their implementation details. Formal semantics would be used to enhance the understanding of the features and to assist in the design of correct implementations. However, there will be no deep discussion of the theory. This is neither a course on compiler design nor a course on the theory of programming languages. Emphasis would be on understanding the features and their implementation. Students will be required to carry out mini projects as a part of the course. The course will have moderate size programming assignments and seminars.
- Robert Harper, Practical Foundations for Programming Languages, Cambridge University Press, 2012.
- John Mitchell, Concepts in Programming Languages, Cambridge University Press, 2002.
- John Reynolds, Theories of Programming Languages, Cambridge University Press, 2009.
- None. However, programming in C/C++/Java/shell/Perl and a course on compiler design at the BE/BTech level would be helpful. There will be no overlap with the compiler design course in the CSA department (E0 255).
User Level Specification of OS. Fundamental Concepts of Multiprogrammed OS, Basic Concepts and Techniques for Implementation of Multiprogrammed OS. Processes and the Kernel, Microkernel Architecture of OS. Multiprocessor, Multimedia, and Real-Time OS. POSIX Standards. Management and Control of Processes. Basic Concept of Threads, Types of Threads, Models of Thread Implementations. Traditional and Real-Time Signals. Clocks, Timers and Callouts. Thread Scheduling for Unix, Windows, and Real-Time OS, Real-Time Scheduling. Interprocess/Interthread Synchronization and Communication, Mutual Exclusion/Critical Section Problem, Semaphores, Monitors, Mailbox, Deadlocks. Concepts and Implementation of Virtual Memory(32-bit and 64-bit), Physical Memory Management. File Organization, File System Interface and Virtual File Systems, Implementation of File Systems. I/O Software:Interrupt Service Routines and Device Drivers. Protection and Security. Case Study of Unix, Windows, and Real-Time OS.
- Andrew S. Tanenbaum: Modern Operating Systems, Second Edition, Pearson Education, Inc., 2001.
- Uresh Vahalia: UNIX Internals: The New Frontiers, Prentice-Hall, 1996.
- J. Mauro and R. McDougall: Solaris Internals: Core Kernel Architecture, Sun Microsystems Press, 2001.
- Daniel P. Bovet and Marco Cesati: Understanding the Linux kernel, 2nd Edition O'Reilly & Associates, Inc., 2003.
Security Requirements of Distributed Systems; Security Violations, Security Goals, Security Services, Security Protocols, and Security Mechanisms; Attack on Security Protocols and Security Mechanisms; Secret Sharing Techniques and One-Way Functions; Discrete Logs, Block Encryption/Decryption Functions, Hash Functions, and MAC Functions; Algorithmic Implementation and Security Requirements of One-Way Functions; OS Security Violations and Techniques to Prevent Them; Access Control Models; Authenticated Diffie-Hellman Key Establishment Protocols; Group Key Establishment Protocols; Block Ciphers and Stream Ciphers; Block Cipher Modes of Encryption; Nonce, Timestamps and Authentication Protocols; Digital Signatures and Source Non-Repudiation Protocols; PKI and X.509 Authentication Service; Security Protocol Verification: Strand Space Theory; Kerberos; E-mail Security; Security Issues in Layered Communication Models: IP Security, Secure Socket Layer and Transport Layer Security; Secure Electronic Transactions; Intrusion Detection; Malicious Software Detection; Firewalls.
- William Stallings: Cryptography and Network Security: Principles and Practices, Sixth Edition, Prentice Hall, 2014.
- Neil Daswani, Christoph Kern and Anita Kesavan: Foundations of Security: What Every Programmer Needs to Know, Published by Apress, 2007.
- Yang Xiao and Yi Pan: Security in Distributed and Networking Systems, World Scientific, 2007.
- Current Literature.
- Knowledge of Java is desirable, but not necessary.
Review of syntax analysis and use of tools LEX and YACC; symbol tables and semantic analysis; run time storage administration and intermediate code generation; dataflow analysis, code optimization and register allocation; instruction selection and code generation; machine dependent optimizations for pipelined, and clustered architectures.
- Aho, A.V., Ravi Sethi and J.D. Ullman: Compilers - Principles, Techniques and Tools, Addison Wesley, 1988.
- S. Muchnick: Advanced Compiler Design and Implementation, Morgan Kauffman, 1998
- Selected Papers.
|E0 256 (3:1)
||Distributed Embedded Systems Development: Rigorous Modeling and design methodologies
||S. Ramesh / Y.N. Srikant
Basics of Embedded Systems: Introduction, Examples, Salient features, Importance, Small and Large Applications, Cyber-physical systems; Overview of design of embedded systems: Challenges and need for rigorous methods; Introduction to Model Based development of Embedded Systems: Functional Model Development and Analysis, Distributed Platform Model Development and Analysis, Allocation and Scheduling of function on Distributed Platform, Performance Analysis and Design Space Exploration; Functional Models of Embedded Systems: Finite State Machines and Statecharts, Data Flow Process Graphs and, Communicating Finite State Machines, Synchronous Reactive Models, Illustrative introduction to various modeling languages like Simulink/SF, Esterel and SCADE; Model Simulation and Verification: Model execution, HW and Plant in loop simulation, Property Specification and design verification, Model based testing; Implementation Platform Models: Centralized and Distributed Platforms, Event and Time Triggered Systems, RTOS and Middleware, Various bus protocols: CAN, TT and Flexray Periodic and sporadic Tasks, Task Communication, dependency graphs; Task Scheduling: Fixed priority Scheduling, Priority inversion and ceiling, Rate monotonic, Deadline Monotonic and Dynamic (EDF) scheduling, Utility based and Response Time Analysis; Distributed Scheduling: Task and message scheduling, Holistic scheduling, Scheduling of dependent tasks; Design methodologies and tools: Overview of some well-known tools which include Metropolis (UC Berkeley), Time-weaver (CMU) and TTTech Tools (TU Vienna); Advanced Topics: Emerging Component based methodologies, Fault-Tolerant implementations.
- H. Kopetz, Real-Time Systems: Design Principles for Distributed Embedded Applications, Kluwer Academic Publishers, 1997.
- Frank Vahid and Tony Givargis, Embedded System Design, John Wiley, 2002.
- Balarin et al., Hardware-Software Codesign of Embedded System Design: A POLIS approach, Kluwer, 1997.
- D. Gajski, et al., Specification and Design of Embedded Systems, Prentice-Hall, 1994.
- Stephen A. Edwards. Languages for Digital Embedded Systems. Kluwer, 2000.
- S. Edwards, L. Lavagno, E. A. Lee, and A. Sangiovanni-Vincentelli, Design of Embedded Systems: Formal Methods, Validation and Synthesis, Proceedings of the IEEE, vol. 85, no. 3, pp. 366-390, 1997.
- W. Damm, et al. Mapping task-graphs on distributed ECU networks: Efficient algorithms for feasibility and optimality, in IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), 2006.
- P. Pop, P. Eles, and Z. Peng, Schedulability-driven communication synthesis for time-triggered embedded systems, Real-Time Systems, vol. 26, no. 3, pp. 297-325, 2004.
- K. Tindell and J. Clark, Holistic schedulability analysis for distributed hard real-time systems, Microprocessing and Microprogramming, vol. 40, no. 2-3, pp.117 . 134, 1994.
- K. Tindell, H. Hanssmon, and A. J. Wellings, Analysing real-time communications: Controller Area Network (CAN),in IEEE Real-Time Systems Symposium (RTSS), San Juan, Puerto Rico, 1994.
- R. K. Shyamasundar and S. Ramesh, Real-Time Programming: Semantics and Verification, to be published in World Scientific Press.
- Basic Operating System and Computer Architecture courses at UG Level
Desirable: Software Engineering at UG/PG level
|E0 257 (3:1)
||Raghu Hudli / Y. N. Srikant
Software process and the role of modeling and analysis, software architecture, and software design. Software Modeling and Analysis: analysis modeling and best practices, traditional best practice diagrams such as DFDs and ERDs, UML diagrams and UML analysis modeling, analysis case studies, analysis tools, analysis patterns. Software Architecture: architectural styles, architectural patterns, analysis of architectures, formal descriptions of software architectures, architectural description languages and tools, scalability and interoperability issues, web application architectures, case studies. Software Design: design best practices, design patterns, extreme programming, design case studies, component technology, object oriented frameworks, distributed objects, object request brokers, case studies.
- Booch,G., Rumbaugh, J., Jacobson, I., The Unified Modeling Language User Guide, Addison- Wesley, 1999.
- Gamma, E.,Helm, R. Johnson, R. Vissides, J., Design Patterns, Elements of Reusable Object- Oriented Software, Addison-Wesley, 1995.
- Frank Buschmann et al. Pattern Oriented Software Architecture, Volume 1: A System of Patterns. John Wiley and Sons, 1996.
- Shaw, M., and Garlan, D., Software Architecture: Perspectives on an Emerging Discipline, Prentice-Hall, 1996.
- Len Bass et al. Software Architecture in Practice. Addison Wesley, 1998.
Survey of programming paradigms and computational models for program execution. Programming language examples, syntax description and language semantics Functional programming, lamda calculus, Higher-order functions, currying, recursion. Imperative programming and control structures, invariants, object models, messages, and method dispatch, inheritance, subtypes and subclasses, polymorphism, covariance, and contravariance. Formal aspects of Java. Concurrent programming models and constructs, programming in the multi-core environment. Introduction to Logic programming quantifiers, first order logic, Horn clauses, unification and resolution.
- Daniel Friedman, Mitchel Wand and Christopher Hanes. "Essentials of Programming Langauges", Prentice Hall of India, 2nd Edition, 2001.
- John Reynolds, "Theories of Programming Languages", Cambridge Univ. Press, 1998.
- John Mitchell, "Concepts in Programming Languages", Cambridge Univ. Press, 2003.
- Benjamin Pierce, "Types and and Programming Languages", MIT Press, 2002.
- Selected Chapters from J. an Leeuwen, Ed. "Handbook of Theoretical Computer Science", Vol. B, Elsevier, MIT Press, 1994.
- Kim Bruce, "Foundations of Object Oriented Languages", Prentice Hall of India, 2002.
- Martin Abadi and Luca Cadelli, "A Theory of Objects", Springer, 1996.
- Current research papers and Internet resources
Design of Database Kernels, Query Optimization (Rewriting Techniques, Access Methods, Join Algorithms, Plan Evaluation), Transaction Management (ARIES), Distributed Databases (Query Processing and Optimization, Concurrency Control, Commit Protocols), Object-Relational Databases (Motivation, Design and Implementation), Spatial Databases (Storage, Indexing Techniques, Query Optimization), Data Mining (Association, Classification and Sequence Rules, Integration with Database Engines), Data Warehousing (Star and Snowflake Schemas, Data Cubes, View Maintenance), Semistructured and Web Databases (Data Models, Query Systems, XML, XML-Schema, Relational Storage, Compression), Mobile Databases (Broadcast Disks, Indexing Techniques), Applications to E-commerce.
- Fundamentals of Database Systems R. Elmasri and S. B. Navathe, Addison-Wesley, 3rd ed., 1999.
- Database Management Systems R. Ramakrishnan and J. Gehrke, McGraw-Hill, 2nd ed., 1999.
- Readings in Database Systems M. Stonebraker and J. Hellerstein, Morgan Kaufmann, 3rd ed., 1998.
- Object-Relational DBMSs M. Stonebraker, Morgan Kaufmann, 1996 .
- Data Warehousing (Strategies, Technologies and Techniques) R. Mattison, IEEE Press, 1998.
- Data Mining R. Groth, Prentice Hall, 1998.
- Recent Conference and Journal papers.
- Data Structures, C or C++, Undergraduate course in DBMS
|E0 262 (3:0)
||Multimedia Information Systems
||P Venkataram / Anandi Giridharan
Multimedia information, delay-sensitive and time-based media data modeling, multimedia storage and retrieval techniques, multimedia communications: synchronization, delay compensation, QoS management and negotiation protocols, architectures and issues for distributed multimedia systems, prototype multimedia systems: video-on-demand, video conferencing, wireless multimedia.
- P. Venkataram, Design Aspects of Multimedia Information Systems, Pearson Publishers, 2009.
- W. I. Grosky, R. Jain and R. Mehrotra, The Hand Book of Multimedia Information Management, Prentice-Hall, 1997.
- J. F. Koegel Buford, Multimedia Systems, Addison-Wesley, 1994.
- Relevant Research Papers from the Journals/Conferences.
Fundamental Issues in Distributed Systems, Distributed System Models and Architectures; Classification of Failures in Distributed Systems, Basic Techniques for Handling Faults in Distributed Systems; Logical Clocks and Virtual Time; Physical Clocks and Clock Synchronization Algorithms; Security Issues in Clock Synchronization; Secure RPC and Group Communication; Secure Group Membership Protocols; Naming Service and Security Issues in Naming Service; Distributed Mutual Exclusion and Coordination Algorithms; Leader Election; Global State, Termination and Distributed Deadlock Detection Algorithms; Distributed Scheduling and Load Balancing; Distributed File Systems and Distributed Shared Memory; Secure Distributed File Systems; Distributed Commit and Recovery Protocols; Security Issues in Commit Protocols; Checkpointing and Recovery Protocols; Secure Checkpointing; Fault-Tolerant Systems, Tolerating Crash and Omission Failures; Distributed Consensus and Agreement Protocols; Replicated Data Management; Self-Stabilizing Systems; Design Issues in Specialized Distributed Systems.
- Randy Chow, and Theodore Johnson, "Distributed Operating Systems and Algorithms", Addison-Wesley, 1997.
- Sukumar Ghosh, "Distributed Systems: An Algorithmic Approach", CRC Press, 2006.
- Kenneth P. Birman, "Reliable Distributed Systems: Technologies, Web Services, and Applications", Springer New York, 2005.
- G. Coulouris, J. Dollimore, and T. Kindberg, "Distributed Systems: Concepts and Designs", Fourth Edition, Pearson Education Ltd., 2011.
- Current Literature
- Network and Distributed Systems Security (E0 254) or equivalent course.
Introduction: video, Audio. Image compression: JPEG, GIF. Video compression: MPEG-1, -2, -4, and -7, H.261. MPEG audio compression, AC 3, content based retrieval, multimedia networking: ATM, RTP, RSVP, RTSP; multicasting: storage and server issues, multimedia processors, mobile multimedia, watermarking, multimedia systems: VoD, video and conferencing, HDTV.
- Raghavan, S. V. and Tripathi, S. K., Networked Multimedia Systems: Concepts, Architecture and Design.
- Raif Steinmetz, Klara Nahrtedt, Multimedia: Computing, Communication and Application, Prentice Hall, 1995.
- Basic knowledge of DSP and Programming.
Definition and scope of ubiquitous computing, essential elements of ubiquitous networks, architecture for ubiquitous computing: new devices and communications; and software architectures. Integrating the physical and the virtual worlds: sensing and actuation; ontology and modeling the world; awareness and perception. Interactions between humans and (ubiquitous) computers: situated (context-aware) computing; multimodal and natural interaction; disambiguation and proactivity. Social aspects of ubiquitous computing: implications on privacy, security and autonomy; system and legal safeguards; cost-benefit and market focus. Ubiquitous applications: the appropriate design; Weiserâ€™s vision of ubiquitous computing; context awareness; mixed reality and sensible design. Illustration of some existing application domains for ubiquitous computing in such areas as gaming, workplaces, domestic spaces, museums and educational communities.
- Research papers on Ubiquitous Computing.
- Communication Protocols/Computer Networks.
Introduction to data mining. Data preprocessing and cleaning. Data visualization and exploratory data analysis. Data mining techniques. Performance evaluation. Finding patterns and rules. Predictive and descriptive modeling. Issues relating to large data sets. Applications to Web Mining and Bioinformatics.
- Tan P.-N, Steinbach M. and Kumar V.: Introduction to Data Mining, Addison-Wesley, 2006.
- Current Literature.
|E0 269 (3:1)
||Probabilistic Graphical Models
Graph types : conditional independence; directed, undirected, and actor models; algorithms for conditional independence (e.g., Bayes-ball,d-separation, Markov properties on graphs, factorization,Hammersley-Clifford theorems). Static Models : linear Gaussian models, mixture models, factor analysis, probabilistic decision trees, Markov Random Fields, Gibbs distributions, static conditional random fields (CRFs), multivariate Gaussians as graphical models, Exponential family, generalized linear models, factored exponential families. Dynamic (temporal) models : Hidden Markov Models, Kalman filtering and linear-Gaussian HMMs, linear dynamic models, dynamic Bayesian networks (DBNs), label and observation bias in natural language processing, dynamic conditional random fields (CRFs), and general dynamic graphical models. Chordal Graph Theory : moralization; triangulated, decomposable, and intersection graphs, Tree-width and path-width parameters of a graph. Exact Probabilistic Inference : The elimination family of algorithms. Relation to dynamic programming. Generality (such as Viterbi, MPE, the fast Fourier transform). junction trees, belief propagation, optimal triangulations. NP hardness results. Approximate Probabilistic Inference : loopy belief propagation (BP), expectation propagation (EP), Sampling (markov chains, metropolis hastings, gibbs, convergence and implementaional issues) particle filtering. Structure Learning : Chow Liu algorithm. Latent Dirichlet Allocation (1 wk): Exchangeability, de Finetti Theorem, Inference using collapsed Gibbs sampling, Dirichlet compound multinomial model.
- Probabilistic Graphical Models: Principles and Techniques", Daphne Koller and Nir Friedman
- Relevant papers
- Introduction to Probability and Statistics and Consent of Instructor
Introduction to machine learning. Classification: nearest neighbour, decision trees, perceptron, support vector machines, VC-dimension. Regression: linear least squares regression, support vector regression. Additional learning problems: multiclass classification, ordinal regression, ranking. Ensemble methods: boosting. Probabilistic models: classification, regression, mixture models (unconditional and conditional), parameter estimation, EM algorithm. Beyond IID, directed graphical models: hidden Markov models, Bayesian networks. Beyond IID, undirected graphical models: Markov random fields, conditional random fields. Learning and inference in Bayesian networks and MRFs: parameter estimation, exact inference (variable elimination, belief propagation), approximate inference (loopy belief propagation, sampling). Additional topics: semi-supervised learning, active learning, structured prediction.
- Bishop. C M, Pattern Recognition and Machine Learning. Springer, 2006.
- Duda, R O, Hart P E and Stork D G. Pattern Classification. Wiley-Interscience, 2nd Edition, 2000.
- Hastie T, Tibshirani R and Friedman J, The Elements of Statistical Learning: Data Mining, Inference and Prediction. Springer, 2nd Edition, 2009.
- Mitchell T, Machine Learning. McGraw Hill, 1997.
- Current literature.
- Probability and Statistics (or equivalent course elsewhere). Some background in linear algebra and optimization will be helpful.
Principles of computer graphics; graphics pipeline; graphics hardware; transformations; viewing; lighting; shading; modeling; selected topics in meshing, subdivision techniques, multi-resolution methods, visualization, ray tracing; individual projects.
- Edward S. Angel. Interactive Computer Graphics, A top-down approach with OpenGL. Addison-Wesley, 2005.
- OpenGL Architecture Review Board, Dave Shreiner, Mason Woo, Jackie Neider, and Tom Davis.
- OpenGL Programming Guide: The Official Guide to Learning OpenGL. Addison-Wesley, 2005.
- Donald Hearn and M. Pauline Baker. Computer Graphics with OpenGL. Prentice Hall, 2003.
- Courses in linear algebra, data structures, algorithms, and programming.
Domain modeling using first-order predicate logic and relational calculus -- the tools Alloy and Event-B. Verification of finite-state systems, and concurrent systems -- Sal and Spin. Code development using refactoring -- Eclipse Refactorings. Identifying errors in code during development using dataflow analysis and logical reasoning -- FindBugs and SpecSharp. Testing and bounded-exploration of applications -- Pex.
- Logic in Computer Science: Modelling and Reasoning about Systems, by Michael Huth and Mark Ryan.
- Software Abstractions: Logic, Language, and Analysis, by Daniel Jackson.
- Model Checking, by Edmund M. Clarke, Orna Grumberg, and Doron Peled.
- Specifying software: A Hands-On Introduction, by R. D. Tennent.
- Research papers.
Introduction to reinforcement learning, introduction to stochastic dynamic programming, finite and infinite horizon models, the dynamic programming algorithm, infinite horizon discounted cost and average cost problems, numerical solution methodologies, full state representations, function approximation techniques, approximate dynamic programming, partially observable Markov decision processes, Q-learning, temporal difference learning, actor-critic algorithms
- D. P. Bertsekas and J. N. Tsitsiklis, "Neuro-Dynamic Programming", Athena Scientific, 1996
- R. S. Sutton and A. G. Barto, "Reinforcement Learning: An Introduction", MIT Press, 1998
- D. P. Bertsekas, "Dynamic Programming and Optimal Control", Vol. I, Athena Scientific, 2005
Introduction to MOS transistor theory, circuit characterization & simulation, theory of logical effort, interconnect design and analysis combinational circuit design, sequential circuit design. Design methodology & tools, testing & verification, datapath subsystems, array subsystems, power and clock distribution, introduction to packaging.
- N.Weste and D. Harris, CMOS VLSI Design. A Circuits and Systems Perspective, Addison Weley, 2005.
- J. M. Rabaey, A. Chandrakasan, and B. Nikolic, Digital Integrated Circuits.
|E0 285 (3:0)
||Computer Aided Design of VLSI systems
||Virendra Singh / S. K. Nandy
Introduction to VLSI CAD: Motivating factors and some trends; Digital hardware modeling: Logic and system level modeling, hardware description languages (VHDL and Verilog), RTL simulation; synchronous and asynchronous system design; verification methodology: Simulatin, BDD, Formal methods; logic synthesis: technology mapping, ASIC design methodology, FPGA based designs and prototyping; Layout synthesis: The physical design, Timing analysis; Graph Algorithms and their applications in IC design; CAD tools and their use; Design for testability; system level design: may have a brief mention of system C and system Verilog.
|E0 290 (3:1)
||Mathematical Foundations for Modern Computing
High-Dimensional Data. Modeling of data in a high dimensional space. High dimensional Euclidean geometry. Random projection theorem. Random Graphs. Erdos-Renyi model, Properties of random graphs, Giant component and threshold phenomena. Random satisfiability problems. Singular Value Decomposition and its applications. Random Walks: Connections to electrical networks, convergence using eigen values and conductance measures. Foundations of Learning Theory. The perceptron algorithm, margins and support vector machines and Vapnik-Chervonenkis theorem and applications. Clustering algorithms and criteria. Provable results and algorithms for k-means and other criteria. Recent work on finding local communities using random walks. Massive Data Computations including streaming algorithms. Fast approximations to matrices such as the CUR approximation. Games and Economic related models and algorithms, the notion of equilibrium, its existence and computation, markets and market equilibria.
- John Hopcroft and Ravi Kannan. Mathematics for Modern Computing. Forthcoming chapters will be made available.
- Ravi Kannan and Santosh Vempala. Spectral Algorithms, Now Publishers, 2009.
1. Introduction, Motivation: Application Domains of Geographical Information Systems (GIS), Common GIS data types and analysis, OGC standards and reference geometry model 2. Models of Spatial Data : Conceptual Data Models for spatial databases (e.g. pictogram enhanced ERDs). Logical data models for spatial databases: raster model (map algebra), vector model (OGIS/SQL1999) 3. Spatial query languages : Need for spatial operators and relations, SQL3 and ADT. Spatial operators, OGIS queries. 4. Spatial storage Methods : Clustering methods (space filling curves), Storage methods (R-tree, Grid files), Concurrency control (R-link trees), Compression methods for raster and vector data, Spatial indexing 5. Spatio-temporal and moving object databases : Spatio Bitemporal objects and operations. Querying, Event models. Spatio temporal indexes 6. Processing spatial queries : Spatial selection, joins, aggregates, nested queries, buffers 7. Query processing and optimization : strategies for range query, nearest neighbor query, spatial joins (e.g. tree matching), cost models for new strategies, impact on rule based optimization, selectivity estimation 8. Spatial networks : Road network databases and connectivity graphs. Topology storage, query for spatial networks. 9. Mining spatial databases : Clustering, Spatial classification, Co-location patterns, Spatial outliers, 10. Geosensor databases
- Spatial Databases: A Tour, S. Shekhar and S. Chawla, Prentice Hall, 2003
- Moving Objects Databases, by Ralf Hartmut Guting, Markus SchneiderMorgan kaufman, 2005
- Spatial Databases with Applications to GIS, P. Rigaux, M. Scholl, A. Voisard, Morgan Kaufmann, 2002
- Spatio-Temporal Database, M. Koubarakis, T. Selles at al (ed.), Springer 2003
- Selected papers (see the bibliography available at: http://www.spatial.cs.umn.edu/Courses/Fall07/8715/paperList.html)
This course will cover topics on developing applications on mobile smartphone platforms. Primary emphasis will be on Android development, while students will also learn the basics of developing applications for iOS. The course will include a project that will be defined and executed by student groups.
- The Android and iOS developer documentation.
- Lecture notes handed out in class.
- Papers from recent conferences and journals.
Reinforcement learning is a paradigm that aims to model the trial-and-error learning process that is needed in many problem situations where explicit instructive signals are not available. It has roots in operations research, behavioral psychology and AI. The goal of the course is to introduce the basic mathematical foundations of reinforcement learning, as well as highlight some of the recent directions of research. The Reinforcement Learning problem: evaluative feedback, non-associative learning, Rewards and returns, Markov Decision Processes, Value functions, optimality and approximation. Bandit Problems: Explore-exploit dilemma, Binary Bandits, Learning automata, exploration schemes. Dynamic programming: value iteration, policy iteration, asynchronous DP, generalized policy iteration. Monte-Carlo methods: policy evaluation, roll outs, on policy and off policy learning, importance sampling. Temporal Difference learning: TD prediction, Optimality of TD(0), SARSA, Q-learning, R-learning, Games and after states. Eligibility traces: n-step TD prediction, TD(lambda), forward and backward views, Q(lambda), SARSA(lambda), replacing traces and accumulating traces. Function Approximation: Value prediction, gradient descent methods, linear function approximation, Control algorithms, Fitted Iterative Methods. Policy Gradient methods: non-associative learning - REINFORCE algorithm, exact gradient methods, estimating gradients, approximate policy gradient algorithms, actor-critic methods. Hierarchical RL: MAXQ framework, Options framework, HAM framework, Option discovery algorithms. Case studies: Elevator dispatching, Samuel's checker player, TD-gammon, Acrobot, Helicopter piloting, Computational Neuroscience.
- R. S. Sutton and A. G. Barto. Reinforcement Learning - An Introduction. MIT Press. 1998.
- D. P. Bertsikas and J. N. Tsitsiklis. Neuro-dynamic programming. Athena Scientific. 1996.
- K. S. Narendra and M. A. L. Thathachar. Learning Automata - An Introduction. Prentice-Hall, USA. 1989.
- A. G. Barto and S. Mahadevan, Recent Advances in Hierarchical Reinforcement Learning, Discrete Event Systems Journal, Volume 13, Special Issue on Reinforcement Learning, pp. 41-77. 2003.
- R. J. Williams, Simple Statistical Gradient-following algorithms for Connectionist Reinforcement Learning, Machine Learning, 8:229-256. 1992.
- J. Baxter, P. L. Bartlett, Infinite-Horizon Gradient-Based Policy Search, Journal of Artificial Intelligence Research, 15: 319-350. 2001.
- V. R. Konda and J. N. Tsitsiklis, "Actor-Critic Algorithms", SIAM Journal on Control and Optimization, Vol. 42, No. 4, pp. 1143-1166. 2003.
- Basic probability theory and linear algebra, Familiarity with regression and non-linear optimization.
The theme of this course in the Jan-Apr 2016 semester is arithmetic circuit complexity. Arithmetic circuits are algebraic analogue of boolean circuits that naturally compute multivariate polynomials. The quest for a thorough understanding of the power and limitation of the model of arithmetic circuits (and its connection to boolean circuits) has lead researchers to several intriguing structural, lower bound and algorithmic results. These results have bolstered our knowledge by providing crucial insights into the nature of arithmetic circuits. Still, many of the fundamental questions/problems on arithmetic circuits have remained open till date.The aim of this course is to provide an introduction to this area of computational complexity theory. We plan to discuss several classical and contemporary results and learn about a wealth of mathematical (particularly, algebraic and combinatorial) techniques that form the heart of this subject.
- Current literature on Arithmetic circuit complexity.
- Familiarity with basic abstract algebra, linear algebra, probability theory and algorithms will be helpful. More importantly, we expect some mathematical maturity with an inclination towards theoretical computer science.
The course is composed of two parts; the first part will introduce the fundamentals of writing concurrent programs, its applicability in the context of building large scale software systems, different models of concurrency, introduction to various bug patterns. The second part will study the recent trends in designing program analysis techniques to detect bugs with a special emphasis on scalable approaches. A course project will help familiarize all the concepts learned as part of the lectures.
- Java Concurrency in Practice by Brian Goetz, Tim Peierls, Joshua Bloch, Joseph Bowbeer, David Holmes, Doug Lea, Addison-Wesley, (2006).
- Slides and research papers listed on the course webpage.
- Previous experience with building a system will be helpful but not essential.
Tools from combinatorics is used in several areas of computer science. This course aims to teach some advanced techniques and topics in combinatorics. In particular, we would like to cover probabilistic method which is not covered in the introductory course `graph theory and combinatorics'. Moreover the course would aim to cover to some extent the linear algebraic methods used in combinatorics. We will also discuss some topics from extremal combinatorics.
Linear Algebraic methods: Basic techniques, polynomial space method, higher incidence matrices, applications to combinatorial and geometric problems. Probabilistic Methods: Basic techniques, entropy based method, martingales, random graphs. Extremal Combinatorics: Sun flowers, intersecting families, Chains and antichains, Ramsey theory.
- L. Babai and P. Frankl: Linear algebra methods in combinatorics with applications to Geometry and Computer Science, Unpublished manuscript.
- N. Alon and J. Spenser: Probabilistic Method, Wiley Inter-science publication.
- Stasys Jukna: Extremal Combinatorics with applications in computer science, Springer.
- Basic familiarity with probability theory, linear algebra, and graph theory and combinatorics.
Various models of secure computation, Computational/statistical indistinguishability Notions, Real/Ideal World security notions, Secret Sharing, Oblivious Transfer and its extension, ThreshÂold Encryption, Secure computation with semi-honest security, Verifiable Secret Sharing, Commitment Schemes, Zero-knowledge Proofs, Secure computation with Active security, Broadcast & Byzantine Agreement (BA), Secure computation for the Cloud.
- Book: â€œEfficient Two-part Protocols- Techniques and Constructionsâ€ by Carmit Hazay and Yehuda Lindell.
- Book Draft: â€œSecure Multiparty Computation and Secret Sharing - An Information Theoretic Appoachâ€ by Ronald Cramer, Ivan Damgaard and Jesper Buus Nielsen.
- Recent Research Papers.
- Mathematical maturity.
- Basic level crypto course.
Minors: Introduction - properties which causes dense minors in graphs: average degree, girth, Wagner's characterisation of graphs without K5 minors. Tree Decompositions: treewidth, pathwidth, upper and lower bounds for treewidth, relation of treewidth and minors, influence on algorithmic graph problems. Hadwiger's conjecture - its relation with the four colour theorem, related work.
- Graph Theory (Chapters 8 and 12), Reinhard Diestel, Springer, 2000.
- Current Literature
The course will consist of two parts: Computational aspects of algebra & number theory ; Use of algebraic methods in theoretical computer science. Part 1: Chinese remaindering, Discrete Fourier Transform, Resultant of polynomials, Hensel lifting, Automorphisms of rings, Short vectors in Lattices, Smooth numbers etc. - and show how these tools are used to design algorithms for certain fundamental problems like integer & polynomial factoring, integer & matrix multiplication, fast linear algebra, root finding, primality testing, discrete logarithm etc. Part 2: This will deal with certain applications of algebraic methods/algorithms in cryptography (RSA cryptosystem, Diffie-Hellman), coding theory (Reed-Solomon & Reed-Muller codes, locally decodable codes), analysis of boolean functions (Fourier analysis), and construction of expander graphs.
- Modern Computer Algebra by von zur Gathen and Gerhard.
- Introduction to Finite Fields by Lidl & Niederreiter.
- Relevant research papers and online lecture notes.
- Basic familiarity with linear algebra and properties of finite fields (as in the Chapter 1-3 of the book 'Introduction to finite fields and their applications' by Rudolf Lidl and Harald Niederreiter). Alternatively, an undergraduate course in algebra. Most importantly, some mathematical maturity with an inclination towards theoretical computer science.
In this course, we aim to study algorithmic approaches for automating 1. Synthesis of programs, 2. Discovering specifications of programs, 3. Selection of domain-specific algorithms. Along with presentations by course instructors, every participant will be assigned a few papers to be presented in the class. The exchange of knowledge will be mainly through open discussions in the classes. An optional course project will be offered for interested participants. The evaluation will be based on quality of presentations, understanding of material, and participation in the class discussions.
- A number of classic as well as recent research papers have been identified carefully. The list can be made available if required. There are no specific text book references for the course.
- Program Analysis and Verification (E0 227) or Automated Verification (E0 223); in other cases, you can seek permission from the instructors.
Basic Parameterized Algorithms: Depth-bounded search trees, iterative compression, color coding, treewidth and dynamic programming over graphs of bounded treewidth. Advanced themes: MSO logic, tree automata, courcelle's theorem (a practical perspective). Influence of randomization on parameterized algorithms. Applications of parameterized algorithms in computational biology, information security, and learning.
- Niedermier, An Invitation to Fixed-Parameter Algorithms.
- Downey and Fellows, Parameterized Complexity
Dataflow analysis: applications in program verification and transformation. Type systems: applications in software development and verification. Program slicing: Applications in software development. Techniques for points-to analysis. Symbolic execution: Applications in program testing. Model checking of software using abstractions. Program logics: applications in program verification. Techniques for testing and verification of concurrent programs.
- Program Analysis and Verification (E0 227)
Convex sets and functions, Convex Optimization Problems, Duality, Approximation and fitting, Statistical Estimation, Geometric Problems, Unconstrained minimization, Interior-point methods.
- S. Boyd and L. Vandenberghe: Convex Optimization, Cambridge University Press, 2004.
Convex Optimization - Introduction, Incremental Gradient, Subgradient and Proximal Methods. Nonsmooth Convex Optimization, DC (Difference of Convex functions) Programming, Lagrangian Relaxation â€“ Dual Decomposition. Augmented Lagrangian Methods, Cutting Plane Methods, Large-Scale Learning - Approximate Optimization.Application/Measure Centric Optimization: distributed learning algorithms for linear and non-linear classifiers, optimization of performance measures such as precision@k, F-measure, AUC and partial AUC.
- Optimization for Machine Learning, Suvrit Sra, Sebastian Nowozin and Stephen Wright (Editors), The MIT Press, Dec. 2011.
- Recent Literature
- A course in Machine Learning or Data Mining
Probability spaces and measure theory, Borel Sigma-Algebras and Random Variables, Lebesgue theory of integration, expectation, Radon Nikodym theorem, Shannon entropy and I-divergence, GYP-theorem for I-divergence, Pinsker inequality, stochastic process and entropy rate, product spaces and Fubiniâ€™s Theorem, probability on metric spaces, conditional expectation, martingales, introduction to stochastic calculus.
- Billingsley, P., Convergence of Probability Measures, Wiley-interscience, 1999.
- Borkar, V. S., Probability Theory : An Advanced Course, Springer-Verlag, 1995.
- K. R. Parthasarathy, Coding Theorems of Classical and Quantum Information theory TRIM publication, 2007.
- I. Karatzas and S.E. Shreve, Brownian Motion and Stochastic Calculus, Springer; 2nd edition 1991.
- Any basic course in Probability.
|E0 335 (3:1)
||Topics in Cryptology: Emerging asymmetric cryptosystems
- Emerging encryption primitives like identity-based encryption, attribute-based encryption, predicate encryption, functional encryption etc. Cryptographic protocols for privacy preserving computation, secure storage and cloud. Revisiting the security definition and security reduction with an emphasis on concrete security and the interplay of functionality, security and efficiency of cryptographic protocols. Cryptanalysis of provable security.
- A selection of research papers from journals and conference proceedings.
Entropy notions such as min-entropy, shannon entropy etc. Computational variants of these notions and the challenges in analyzing them. Randomness extractors, privacy amplification protocols, leakage-resilient Cryptography. Design of error correcting codes with specialized properties (motivated by various cryptographic applications) - e.g., non-malleable codes, updatable codes etc.
- An undergraduate course on Probability Theory will be helpful.
Architecture and harware description languages (RTL, ISPS, vhdl). Processor architecture, Instruction level parallelism, Latency tolerance, multithreading, interconnection networks, Standards (bus, SCI), architectures, routing, Cache coherency, protocol specification, correctness, performance. Memory consistency models, synchronization primitives, parallel programming paradigms, I/O systems, Interface standards, parallel I/O, performance evaluation, analytical methods, simulation algorithms and techniques, benchmarking.
- Computer Architecture, Operating Systems, Some Familiarity with Analytical Performance Evaluation Techniques
Regression, feature selection, ensemble methods (boosting, bagging, etc) and HMM models. Selected topics in OS (related to the papers under discussion and including, as necessary, some review of required background)
- Current Literature (Conference proceedings of SOSP, SysML, etc)
- Background in atleast one computer systems area like OS, Databases, Compilers etc. and Instructors' consent.
Selected topics in operating systems of topical interest. Design, implementation, correctness and performance related aspects. Past offerings included study of subsystems such as process, storage and network subsystems.
- Consent of instructor and a course in Operating Systems, Computer Architecture with some familiarity of the internals of Linux/Unix
Dynamic and Just-In-Time compilation. Compilation for embedded systems: performance, memory, and energy considerations. Static analysis: points-to analysis, abstract interpretation. WCET estimation. Type systems. Optimizations for O-O languages. Compilation for multi-core systems.
This course will be based on seminars and mini projects.
- Y.N. Srikant and Priti Shankar (ed.), The Compiler Design Handbook: Optimizations and Machine Code Generation, 2nd ed., CRC Press, 2008.
- Good knowledge of dataflow analysis and compiler optimizations
Parallel architectures: a brief history, design, Auto-parallelization for multicores, GPUs, and distributed Memory clusters Lock-free and wait-free data structures/algorithms for parallel programming Study of existing languages and models for parallel and high performance programming; issues in design of new ones.
- Aho, Lam, Sethi, and Ullman, Compilers: Principles, Techniques, and Tools, 2nd edition
- Herlihy and Shavit, The Art of MultiProcessor Programming
- Ananth Grama, Introduction to Parallel Computing
- List of research papers and other material which will be the primary reference material will be available on course web page.
- Knowledge of "E0 255 Compiler Design" course content (especially on parallelization) will be very useful, but not absolutely necessary.
- Knowledge of microprocessor architecture and some basic understanding of parallel programming models.
Object-oriented Databases, Distributed and Parallel Databases, Multi-databases, Access Methods, Transaction Management, Query Processing, Deductive Databases, multimedia Databases, Real- Time Databases, Active Databases, Temporal Databases, Mobile Databases, Database Benchmarks, Database Security, Data Mining and Data Warehousing.
- Readings in Database Systems edited by M. Stonebraker, Morgan Kaufmann, 2nd ed., 1994.
- Conference and Journal papers
|E0 367 (3:1)
||Topics in Mobile Computing Technologies
||L. M. Patnaik
Wireless Technologies: Land Mobile Vs. Satellite Vs. In-building Communications Systems, Cellular Telephony, Personal Communication Systems/Networks. Wireless Architectures for Mobile Computing. Applications. Wireless LANs, Wireless Networking, Hand-off, Media Access Methods, Mobile IP, Unicast and Multicast Communication, Wireless TCP, Security Issues. Mobile Computing Models, System-Level Support, Disconnected Operation, Mobility, Failure Recovery. Information Management, Broadcast, Caching, Querying Location Data. Location and Data Management for Mobile Computing, Hierarchical Schemes, Performance Evaluation. Case Studies.
- Current Literature from IEEE Transactions, Journals,and Conference Proceedings.
- Abdelsalam A. Helal et al, Any Time, Anywhere Computing : Mobile Computing Concepts and Technology, Kluwer International Series in Engineering and Computer Science, 1999.
- Evaggelia Pitoura and Geaorge Samaras, Data Management for Mobile Computing, Kluwer International Series on Advances in Database Management,October 1997.
- Consent of the Instructor
Theoretical foundations of modern machine learning. Kernel methods: support vector machines. Ensemble methods: boosting. Generalization analysis: VC-dimension bounds, covering numbers, margin analysis, Rademacher averages, algorithmic stability. Statistical consistency analysis. PAC learning. Online learning and regret bounds. Selected additional topics of current interest.
- Devroye, L, Gyorfi L, and Lugosi G, A Probabilistic Theory of Pattern Recognition. Springer, 1996.
- Anthony M, and Bartlett P L, Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999.
- Vapnik V N, Statistical Learning Theory. Wiley-Interscience, 1998.
- Current literature.
- A strong foundation in probability and statistics, and some previous exposure to machine learning. Some background in linear algebra and optimization will be helpful.
|E0 371 (3:1)
||Topics in Machine Learning - Non-parametric Bayesian Methods and Approximate Inference
Review of Directed Graphical Models: Semantics; Exact Inference using Junction Tree Algorithm, Complexity Analysis; Parameter Estimation. Approximate Inference: Loopy Belief Propagation & Generalized Belief Propagation; Sampling techniques, Variational Techniques. Case Study: Latent Dirichlet Allocation. Non parametric Bayesian Models: Dirichlet Processes, Chinese Restaurant Processes and Polya Urn; Hierarchical Dirichlet Processes and Chinese Restaurant Franchise; Infinite Mixture Models and Indian Buffet Processes; Sequential models, Hidden Markov Dirichlet Processes and Hierarchical Dirichlet Process HMM; Hierarchical models, Nested Chinese Restaurant Processes; Dynamic models, Recurrent Chinese Restaurant Processes. Efficient Inference: Parallel, distributed and online algorithms.
- Textbooks: Current literature.
- Machine Learning, Consent of the instructor.
Sequence Alignment, Global and Local Alignment, Hidden Markov Models and their Applications in sequence processing, Phylogenetics, Bayesian Statistics, Sampling Algorithms, Clustering, Classification of Gene expression datasets, Support vector machines, Optimization, Principal Component Analysis.
- R. Durbin, S. Eddy, A. Krogh, G. Mitchison, Biological Sequence Analysis Cambridge University Press, 1998.
- M.S. Waterman, Introduction to Computational Biology Maps, Sequences and Genomes, Chapman and Hall - CRC Press, 1995.
- Current Literature
- Consent of the Instructor.
Topological methods for analyzing scientific data; efficient combinatorial algorithms in Morse theory; topological data structures including contour trees, Reeb graphs, Morse-Smale complexes, Jacobi sets, and alpha shapes; robustness and application to sampled data from simulations and experiments; multi-scale representations for data analysis and feature extraction; application to data exploration and visualization.
- Textbooks: Course material will consist of current literature and lecture notes.
- Basic familiarity with fundamental algorithms and data structures is desirable (E0 225 or E0 251). Familiarity with the basics of scientific visualization will be useful but not essential. Interested students with a non-CS background may also register for the course after consent of instructor.
Fundamental Theorems: Radon's theorem, Helly's theorem. Geometric graphs: Proximity graphs, geometric results on planar graphs. Geometric incidences: Incidence bounds using cuttings technique, crossing lemma. Distance based problems: Bounds on repeated distances and distinct distances. Epsilon Nets: Epsilon Net theorem using random sampling and discrepency theory, epsilon nets for simple geometric spaces, weak epsilon nets.
- Janos Pach and Pankaj K. Agarwal: Combinatorial Geometry, Wiley, 1st edition, 1995.
- J. Matousek: Lectures on Discrete Geometry, Springer-Verlag, 1st edition, 2002.
- Current literature
- The registrants should have preferably completed the "Design and Analysis of Algorithms" or "Discrete Structures" course.
Verification using classical automata, Automata-theoretic techniques for shape analysis, Reachability in pushdown systems. Automata over distributed alphabets, and Message sequence charts. Automata over trees, XML data / Regular tree language compression, Automata on nested words. Automata and logics over signals, Automata-based techniques for timed logics, Approximate regular behaviour of hybrid automata.
- Wolfgang Thomas: Applied Automata Theory (Electronic notes, RWTH Aachen)
- Current Literature
- A course on Automata Theory equivalent to E0 222.
Probability and basic information theory, universal data compression, I-projections and iterative algorithms for estimation with applications to statistics, large deviations and hypothesis testing, probabilities on metric spaces and information topology, Kolmogorov complexity, Applications of IT to other areas such as ergodic theory, gambling, biology.
- Information theory and Statistics: A Tutorial by I. Csisz_ar and P. Shields, Now Publications, 2008.
- Elements of Information Theory, by T. M. Cover and J. A. Thomas, John Wiley and Sons, 2nd edition, 2006.
- Information and Distribution: Occam's Razor in Action by P. Harremoes and A. Dukkipati, (in preparation) 2008.
- Coding Theorems of Classical and Quantum Information theory by K. R. Parthasarathy, TRIM publication, 2007.
- Information Theory, Inference, and Learning Algorithms by D.J.C. MacKay, Cambridge University Press, 2003.
- Basic probability theory or consent of instructor.
Preliminaries, polynomials, factorization of polynomials, Finite Fields, Berlekamp's algorithm, Hensel's lifting, LLL algorithm, applications to error correcting codes, the turnpike problem, some group theory, special cases of graph isomorphism, algorithms for primality testing.
- Joachim von zur Gathen and JÃ¼rgen Gerhard: Modern Computer Algebra
- Relevant research papers and online notes.
|E0 392 (2:0)
||Models and Algorithms for modern data
Representing processing data as high-dimensional points, Random graphs and other random models, Probability Concentration phenomena, Eigen Values, Eigen vectors, Singular Value Decomposition and Algorithmic applications, Massive Matrix Computations using randomized algorithms, Learning Algorithms, Optimization.
- A solid undergrad background in Calculus, Linear Algebra, Probability and exposure to Algorithms.
Graph Theory: Connectivity, Matchings, Hamiltonian Cycles, Coloring Problems; Network flows, special classes of graphs. Introduction to Graph Minor theory. Combinatorics: Basic Combinatorial Numbers, Recurrence Relations, Inclusion-Exclusion Principle, Introduction to Polya Theory. Probabilistic Method in Graph theory: Basic Method, Expectation, Chernoff bound, Lovasz Local Lemma.
- J. H. Van Lint, R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 1993.
- N. Alon and J. Spenser, "Probabilistic Methods", John Wiley and Sons, 2nd edition, 2000.
- R. Diestel, "Graph Theory", Springer-Verlag, 2nd edition, 2000.
|E0 394 (3:1)
||Performance Management of Internet Applications
Part I: Performance Analysis
Introduction to multi-tier application performance characteristics, Measurement-based performance analysis of distributed applications, Analytical Performance modeling of multi-tier applications, Layered Queueing models (generic) Case studies of performance analysis of specific technologies (E.g. web server, virtual machines).
Part II: Performance Management
Overload control mechanims, QoS guarantee mechanisms, Dynamic resource provisioning mechanisms (e.g. in virtualized platforms), Power-aware performance management.
- Scaling for e-business: technologies, models, performance, and capacity planning, Daniel A. MenascÃ©, Virgilio A. F. Almeida, Prentice-Hall, 2000.
- Woodside, Neilson, Petriu, Majumdar, The Stochastic Rendezvous Network Model for Performance of Synchronous Client-Server-like Distributed Software, IEEE Trans. On Computers, January 1995 (vol. 44 no. 1) pp. 20-34.
- Rolia and Sevcik, The Method of Layers, IEEE Transactions on Software Engineering, Volume 21 , Issue 8 (August 1995), Pages: 689 - 700.
- John Dilley, Rich Friedrich, Tai Jin, Jerome Rolia, Web server performance measurement and modeling techniques, Performance Evaluation, Volume 33 , Issue 1 (June 1998), Special issue on tools for performance evaluation, Pages: 5 - 26
- Paul Barford, Mark Crovella, Generating representative Web workloads for network and server performance evaluation, ACM SIGMETRICS Performance Evaluation Review, Volume 26, Issue 1 (June 1998), Pages: 151 - 160.
- TF Abdelzaher, KG Shin, N Bhatti, Performance guarantees for web server endsystems: A control-theoretical approach, IEEE Transactions on Parallel and Distributed Systems, 2002.
- Comparison of the three CPU schedulers in Xen, L Cherkasova, D Gupta, A Vahdat - Performance Evaluation Review, 2007.
- B Urgaonkar, P Shenoy, A Chandra, P Goyal, Agile dynamic provisioning of multi-tier Internet applications, ACM Transactions on Autonomous and Adaptive Systems (TAAS), Volume 3 , Issue 1 (March 2008).
- Jeffrey S. Chase, Darrell C. Anderson, Prachi N. Thakar, Amin M. Vahdat, Ronald P. Doyle, Managing energy and server resources in hosting centers, December 2001, SOSP '01: Proceedings of the eighteenth ACM symposium on Operating systems principles.
- It will be very useful to have a background in queuing systems (as provided in course E0 241, or any equivalent course from other departments). Undergraduate level background in Operating Systems and Computer Networking will be assumed. Students should be comfortable with a broad range of quantitative methods generally required in engineering.
|E0 397 (3:1)
||Performance and Resource Management in Virtualization and Cloud Computing
Application performance characteristics; Performance metrics, their fundamental behaviour with respect to allocated resources, offered load, etc; Overview of virtualization, Virtual Machines (e.g. Xen, KVM, VMware), Performance Isolation in virtual machines, Xen CPU Schedulers, schedulers in other VMs., Live migration; Understanding energy as a resource, Energy consumption behaviour of server machines, how power consumption can be controlled; Cloud Computing: overview, brief case studies , Dynamic and autonomic resource management in clouds, Resource allocation within one physical machine , Methods based on control theory, reinforcement learning, and other methods; Resource Management of a virtualized cluster â€“ specifically approaches for power usage reduction; Methods based on control theory, reinforcement learning, and other methods.
- The Definitive Guide To The Xen Hypervisor (Series - Prentice Hall Open Source Software Development) by David Chisnall
- Running Xen: A Hands-on Guide To The Art Of Virtualization by Jeanna Matthews, Eli M. Dow, Todd Deshane. Prentice Hall.
- Undergraduate level background in Operating Systems and Computer Networking will be assumed.
|E1 213 (3:1)
||Pattern Recognition and Neural Networks
||P. S. Sastry
Introduction to pattern recognition, Bayesian decision theory, supervised learning from data, parametric and non parametric estimation of density functions, Bayes and nearest neighbor classifiers, introduction to statistical learning theory, empirical risk minimization, discriminant functions, learning linear discriminant functions, Perceptron, linear least squares regression, LMS algorithm, artificial neural networks for pattern classification and function learning, multilayer feed forward networks, backpropagation, RBF networks, support vector machines, kernel based methods, feature selection and dimensionality reduction methods.
- R. O Dudo, P.E. Hart & D. G. Stork, Pattern Classification John Wiley & sons, 2002.
- C.M Bishop, Neural Network & Pattern Recognition, Oxford University Press(Indian Edition) 2003.
- Knowledge of Probability theory.
This course will present a broad, introductory survey intended to develop familiarity with the approaches to modeling and solving problems in computer vision. Mathematical modeling and algorithmic solutions for vision tasks will be emphasized. Image formation: camera geometry, radiometry, colour; Image features : points, lines, edges, contours, texture; Shape: object geometry, stereo, shape from cues; Motion: calibration, registration, Multiview geometry, optical Flow; approaches to grouping and segmentation; representation and methods for object recognition; applications.
- Computer Vision: A Modern Approach by David Forsyth and Jean Ponce, Prentice-Hall India, 2003.
- Multiple View Geometry in Computer Vision by R. Hartley and A. Zisserman, Second Edition, Cambridge University Press, 2004.
- Current literature.
|E1 222 (3:0)
||Stochastic Models and Applications
||P. S. Sastry
Probability spaces, conditional probability, independence, random variables, distribution functions, multiple random variables and joint distributions. Expectations, moments, characteristic functions and moment generating functions, sequence of random variables and convergence concepts. Law of large numbers, central limit theorem, stochastic processes, Markov chains, stationary distribution of Markov chains, Poisson and birth and death processes.
- S. M. Ross, Introduction to Probability Models, (6th Edition), Academic Press and Harcourt Asia, 2000
- Hoel, P. G., Port, S. C., and Stone, C. J., Introduction to Probability Theory, Indian Edition, Universal Book Stall, New Delhi, 1998.
- Hoel, P. G., Port, S. C., and Stone, C. J., Introduction to Stochastic Process, Indian Edition, Universal Book Stall, New Delhi, 1981.
Background material on matrix algebra, differential equations. Representation of dynamic systems, equilibrium points and linearization. Natural and forced response of state equations, state space descriptions, canonical realizations. Observability and controllability, minimal realization. Linear state variable feedback, stabilization, modal controllability, Jordan form, functions of matrices, pole-placement, Lyapunov matrix equations. Asymptotic observers, compensator design, and separation principle. Preliminary quadratic regulator theory.
- Chi-Tsong Chen, Linear Systems Theory and Design, HBJ 1984.
- Kailath T., Linear System Theory, Prentice Hall, 1980.
|E1 244 (3:0)
||Detection and Estimation Theory
||Chandra R Murthy
Hypothesis testing, Neyman Pearson theorem, LRT and GLRT, UMP test, multiple-decision problem, detection of deterministic and random signals in Gaussian noise, detection in non-Gaussian noise. Sequential detection. Parameter estimation: unbiasedness, consistency, Cramer-Rao bound, sufficient statistics, Rao-Blackwell theorem, best linear unbiased estimation, maximum likelihood estimation, method of moments. Bayesian estimation: MMSE and MAP estimators, Wiener filter, Kalman filter, Levinson-Durbin and innovation algorithms.
- H. V. Poor, An Introduction to Signal Detection and Estimation, Springer-Verlag, 1994.
This course provides a modern and statistical perspective on natural language processing. The course will enable the student to: acquire fundamentals of language technology; understand, implement, and apply state-of-the-art techniques to novel problems involving natural language data; and be able to read and understand current research literature. Necessary machine learning concepts will be covered along the way.
- Morphology, Parts-of-Speech, Language Models, Word Sense Disambiguation, Anaphora Resolution, Finite State Transducers, Basics of Supervised and Semi-supervised Learning, Hidden Markov Models, EM Algorithm, Structured Prediction, CFG Parsing, Dependency Parsing, Discourse Processing, Lexical Semantics, Distributional Semantics, Representation Learning for NLP, Semantic Parsing, Knowledge Bases, Topic Models, Machine Translation, Information Extraction, Sentiment analysis.
- Chris Manning and Hinrich Schütze, Foundations of Statistical Natural Language Processing, MIT Press, May 1999.
- Emily Bender, Linguistic Fundamental for NLP, Morgan Claypool Publishes, June 2013.
- Jurafsky D, and Martin J H, Speech and language processing: an introduction to natural language processing, computational linguistics and speech recognition, Pearson Education,2003.
- Allen J, Natural language understanding, Pearson Education, 1995, 2003.
- Research Literature.
|E1 247 (2:1)
||Incremental Motion Control
||N. S. Dinesh and J. E. Diwakar
Introduction to various incremental motion systems. Principles of operation and classification of various types of steeper motors, control and drive circuits. Improved control and drive techniques in open and closed loop. Use of DC motors in incremental motion systems and related control techniques.
- Kuo BC, Step Motors and Control Systems, SRL Publishing Co., Illinois, 1979
- Proceedings of Annual Symposium on Incremental Motion Control Systems and Devices, from 1974 onwards published by IMCSS Champain
- Srinivasan, M. P., Stepping Motors: Lecture Notes CEDT/IISc, Publication 1983
|E1 251 (3:0)
||Linear and Nonlinear Optimization
||K. R. Ramakrishnan
Necessary and sufficient conditions for optima; convex analysis; unconstrained optimization; descent methods; steepest descent, Newtonâ€™s method, quasi Newton methods, conjugate direction methods; constrained optimization; Kuhn-Tucker conditions, quadratic programming problems; algorithms for constrained optimization; gradient projection method, penalty and barrier function methods, linear programming, simplex methods; duality in optimization, duals of linear and quadratic programming problems.
- J.Luenberger D.G. Introduction to Linear and Nonlinear Programming, 2nd edition, Addison Wesley, 1984.
- Fletcher. R: Practical methods of Optimization John Wiley, 1980.
Introduction: rationality, intelligence, common knowledge, von Neumann - Morgenstern utilities; Noncooperative Game Theory: strategic form games, dominant strategy equilibria, pure strategy nash equilibrium, mixed strategy Nash equilibrium, existence of Nash equilibrium, computation of Nash equilibrium, matrix games, minimax theorem, extensive form games, subgame perfect equilibrium, games with incomplete information, Bayesian games. Mechanism Design: Social choice functions and properties, incentive compatibility, revelation theorem, Gibbard-Satterthwaite Theorem, Arrow's impossibility theorem, Vickrey-Clarke-Groves mechanisms, dAGVA mechanisms, Revenue equivalence theorem, optimal auctions. Cooperative Game Theory: Correlated equilibrium, two person bargaining problem, coalitional games, The core, The Shapley value, other solution concepts in cooperative game theory.
- Roger B. Myerson, Game Theory: Analysis of Conflict, Harvard University Press, September 1997.
- Martin J. Osborne, An Introduction to Game Theory, Oxford University Press, 2003.
- Y. Narahari, Dinesh Garg, Ramasuri Narayanam, Hastagiri Prakash. Game Theoretic Problems in Network Economics and Mechanism Design Solutions. Springer, 2009.
Introduction to reinforcement learning, introduction to stochastic dynamic programming, finite and infinite horizon models, the dynamic programming algorithm, infinite horizon discounted cost and average cost problems, numerical solution methodologies, full state representations, function approximation techniques, approximate dynamic programming, partially observable Markov decision processes, Q-learning, temporal difference learning, actor-critic algorithms.
- D.P.Bertsekas and J.N.Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1996.
- R.S.Sutton and A.G.Barto, Reinforcement Learning: An Introduction, MIT Press, 1998.
- D.P.Bertsekas, Dynamic Programming and Optimal Control, Vol.I, Athena Scientific, 2005.
Foundations of pattern recognition. Soft computing paradigms for classification and clustering. Knowledge-based clustering. Association rules and frequent itemsets for pattern recognition. Large-scale pattern recognition.
- R. O. Duda, P. E. Hart, and D.G. Stork, Pattern Classification, John Wiley & Sons (Asia), Singapore, 2002
- Recent Literature.
|E1 335 (3:1)
||Cognition and Machine Intelligence
||C.E. Veni Madhavan
Biological cerses computational dichotomy, critical computer - anatomy of neocortex, 100 steps at 5 msec rule, symbolic architecture, connectionist approach, multi-sensory-motor information, hierarchical, network, pyramidal models, spatio-temporal pattern matching, pattern representation and storage, invariant representations, sequences of sequences, autoassociative, content addressable memory retrieval, memory prediction paradigm, domains: language acquiaition, vision and attention, mental models, design and development of thought experiments and simulation.
- Posner M I, Foundations of Cognitive Science, The MIT Press, 1993.
- Books and Survey Articles by: M. Minsky, A. Newell, H.A. Simon, D.E. Rumelhart, T. Sejnowski, J. Barwise, N. Chomsky, S. Pinker, V.S. Ramachandran and others
Foundational results in game theory and mechanism design: Nash's existence theorem, Arrow's impossibility theorem, Gibbard Satterthwaite theorem, etc.; Selected topics in repeated games, evolutionary games, dynamic games, and stochastic games; Selected topics at the interface between game theory, mechanism design, and machine learning; Selected topics in algorithmic game theory; Modern applications of game theory and mechanism design: incentive compatible learning, social network analysis, etc.
- Roger B. Myerson, Game Theory: Analysis of Conflict, Harvard University Press, September 1997.
- Rakesh V. Vohra: Advanced Mathematical Economics. Routledge, New York, NY, 2005.
- Andreu Mas-Colell, Michael D. Whinston, and Jerry R. Green: Microeconomic Theory. Oxford University Press, New York, 1995.
- Current Literature
- Elementary knowledge of linear algebra, linear programming, algorithms, game theory is useful for this course.
Markov decision processes, finite horizon models, infinite horizon models under discounted and long-run average cost criteria, classical solution techniques -- policy iteration, value iteration, problems with perfect and imperfect state information. Reinforcement learning, solution algorithms -- Q-learning, TD(lambda), actor-critic algorithms.
- D.P.Bertsekas, Dynamic Programming and Optimal Control, Vol.I and II, Athena Scientific, 2005.
- D.P.Bertsekas and J.N.Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1996.
- R.S.Sutton and A.G.Barto, Reinforcement Learning: An Introduction, MIT Press, 1998.
- Selected Research Papers.
- A course on probability theory and stochastic processes. Knowledge of nonlinear programming is desirable.
Introduction to Stochastic approximation algorithms, ordinary differential equation based convergence analysis, stability of iterates, multi-timescale stochastic approximation, asynchronous update algorithms, gradient search based techniques, topics in stochastic control, infinite horizon discounted and long run average cost criteria, algorithms for reinforcement learning.
- H.J.Kushner and G.Yin, Stochastic approximation and recursive algorithms and applications (2nd edition), Springer Verlag, New York, 2003.
- A.Benveniste, M.Metiview and P.Priouret, Adaptive algorithms and stochastic approximation, Springer-Verlag,1990.
- V.S.Borkar,Stochastic Approximation: A Dynamical Systems Viewpoint, Hindustan Book Agency, 2008.
- D.P.Bertsekas and J.N.Tsitsiklis, Neuro-dynamic programming, Athena Scientific, 1996.
- Relevant research papers
- A basic course on probability theory and stochastic processes.