E0 Computer Science and Automation
E0 219 (AUG) 3:1
Linear Algebra and Applications
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.
R Vittal Rao
Strang, G., Linear Algebra and Applications,
Thomson-Brooks/Cole, Fourth Edn, 2006.
E0 220 (JAN) 3:1
Graph Theory and Combinatorics
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.
L
Sunil Chandran
Van Lint, J.H., and
Alon,
N., and Spenser, J., Probabilistic Methods, John Wiley and Sons, Second Edn, 2000.
Diestel,
R., Graph Theory, Springer Verlag, Second Edn, 2000.
E0 221 (AUG) 3:1
Discrete Structures
Review of Set Theory: Relations, Equivalence relations,
Order relations, Partially ordered sets Finite sets, Glb,
Lub, Minimal and maximal elements. Cardinal
arithmetic. Combinatorics and Recurrences: Basic theorems on
permutation and combinations, Pigeon principle, Inclusion-Exclusion principle. Discrete Probability: Basic concepts
and examples. Groups: Definitions and Examples. Finite groups, Lagrange's
Theorem, Cyclic Groups. Groups actions. Rings:
Polynomial rings, Zeros of polynomials, Resultants and Discriminants,
Hilbert basis theorem, Euclidean rings, Fundamental theorem on symmetric
functions. Fields: Finite
Fields, Finite and Algebraic extensions. Algebraic closure, Algebraically
closed fields. Proof of Fundamental theorem of Algebra. Elementary number theory: Prime numbers, Fundamental Theorem of
Arithmetic.
Dilip Patil
Jacobson, N., Basic Algebra, Vols. I & II,
Joshi, K.D., Foundations of Discrete Mathematics, New Age
Publishers,
Graham, R.L., Knuth, D.E., and Patashnik,
O., Concrete Mathematics: A Foundation
for Computer Science, Addison-Wesley Professional; Second Edn,
1994.
Hasse,
H., Number Theory (Classics in Mathematics),
Liu, C.L., Elements of Discrete Mathematics, McGraw Hill 1986.
E0 222 (AUG) 3:1
Automata Theory and Computability
Finite-state automata: Myhill-Nerode theorem, ultimate periodicity, Buchi's logical
characterization. Pushdown automata and Context-free languages,
including deterministic PDA's, Parikh’s theorem, Chomsky-Shutzenberger
theorem. Turing machines and undecidability, Rice's
theorem and Godel's incompleteness theorem.
Deepak D'Souza
and Priti Shankar
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.
E0 223 (JAN) 3:1
Automated Verification
Formal models of systems: labeled state transition diagrams
for concurrent processes and protocols, timed and hybrid automata for embedded
and real-time systems. Specification logics: propositional and first-order
logic; temporal logics (CTL, LTL, CTL).
Fixpoint logic: mu-calculus. Algorithmic analysis:
model checking, data structures and algorithms for symbolic model checking, decision
procedures for satisfiability and satisfiability
modulo theories. Tools: Student projects
and assignments involving model checking and satisfiability
tools e.g. zChaff, SPIN, NuSMV,
Uppaal.
Aditya Kanade
Michael Huth and Mark Ryan, Logic in Computer Science: Modelling and Reasoning about Systems,
Clarke,
E.M., Grumberg, O., and Peled,
D., Model Checking, MIT Press, 2001.
Daniel Kroening and Ofer Strichman: Decision Procedures: An Algorithmic Point of
View, Springer, 2008.
Pre-requisites:
Basics of data structures, algorithms, and automata theory.
E0 225 (AUG) 3:1
Design and Analysis of Algorithms
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.
Satish Govindarajan
Cormen,
T.H., Leiserson, C.E., Rivest,
R.L., and Stein, C., Introduction to Algorithms, Second Edn,
Prentice Hall, 2001.
Aho,
A.V., Hopcraft, J.E., and Ullman,
J.D., Design and Analysis of Algorithms, Addison-Wesley, 1974.
Jon Kleinberg and Éva Tardos, Algorithm Design, Addison Wesley, 2005.
E0 227 (AUG)
3:1
Program
Analysis and Verification
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.
Deepak D'Souza and K V Raghavan
Nielson,
F., Nielson, H.R., and Hankin, C., Principles of
Program Analysis, Springer, (Corrected 2nd printing, 452 pages, ISBN 3-540-65410-0),
2005.
Pierce,
C.P., Types and Programming Languages, Prentice Hall
Research
papers.
E0 230 (AUG) 3:1
Computational Methods of Optimization
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.
Chiranjib Bhattacharyya
Fletcher, R., Practical Methods of Optimization, John Wiley, 2000.
E0 231 (JAN) 3:1
Algorthmic
Algebra
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.
Ambedkar Dukkipati
Cox,
D., and O’Shea, Ideals, Varieties and Algorithms, Springer, Second Edn, 1997.
Mishra, B., Algorithmic Algebra, Springer, 1993.
E0 232 (AUG) 3:1
Probability and Statistics
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.
Ambedkar
Dukkipati and Indrajit Bhattacharya
Rohatgi, V.K.,
Allen Gut, An Intermediate course in
Probability, Springer, 2008.
E0 233 (AUG) 3:1
Information Theory, Inference and Learning
Algorithms
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.
Ambedkar
Dukkipati
Cover, T.M., and Thomas, J.A., Elements
of Information Theory, John Wiley and Sons, Second Edn,
2006.
MacKay, D.J.C., Information Theory,
Inference and Learning Algorithms,
E0 235 ( AUG ) 3:1
Cryptography
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.
C
Koblitz,
N., Course on Number Theory and Cryptography, Springer Verlag,
1986.
Menezes,
A, et. al., Handbook of Applied Cryptography, CRC Press, 1996.
Current Literature
E0 236
(JAN) 3:1
Information Retrieval
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.
M Narasimha Murthy
Manning, C.D., Raghavan, P., and Schutze, H., Introduction to Information Retrieval,
Recent Literature
E0 238 (JAN) 3:1
Artificial Intelligence
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.
V Susheela
Devi
Russel,
S., and Norvig, P., Artificial Intelligence – A
Modern Approach, Prentice Hall, 1995.
Luger, G.F., Artificial Intelligence, Pearson Education, 2001.
E0 241 (JAN) 3:1
Computer Communication Networks
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,
Varsha Apte And Shalabh Bhatnagar
Mitrani,
I., Modelling of Computer and Communication Systems,
Walrand,
J., and Varaiya, P., High Performance Communication
Networks, Harcourt Asia (Morgan Kaufmann), 2000.
Keshav,
S., An Engineering Approach to Computer Networking, Pearson Education, 1997.
Bertsekas,
D., and Gallager, R., Data Networks, Prentice Hall of
India, 1999.
Kurose, J.F., and Ross, K.W., Computer Networking: A Top-Down Approach
Featuring the Internet, Pearson Education, 2001.
E0 242
(JAN) 3:1
Probabilistic Models for Learning
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.
Chiranjib Bhattacharyya
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
E0 243 (AUG) 3:1
Computer Architecture
Processor architecture,
pipelining, vector processing, superscalar processors, hardware and compiler support for branch prediction,
out-of-order Instruction issue, speculative execution and other techniques for high-performance.
Instruction and data cache organizations, multilevel caches, parallel memory
systems, support for virtual memory, multiple processor systems, taxonomy, programming models, message passing
systems, Interconnection networks, shared
memory system, memory models, cache coherence, I/O systems, parallel
disk organisations,
Introduction to advanced topics.
T
Matthew Jacob
Hennessy, J.L., and Patterson, D.A., Computer Architecture, A
quantitative Approach, Morgan Kaufmann.
Stone, H.S., High-Performance Computer Architecture, Addison-Wesley.
Current Literature
E0 245 (JAN) 3:0
Fault Tolerant Computing
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.
Pre-requisite: E0 241
Siework, C.P., and Swartz, R.S., Theory and Practice of
Reliable System Design, McGraw Hill, 1982.
Current Literature.
E0 246 (AUG) 3:0
Real-time Systems
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.
Liu, J.W.S., Real-Time Systems, Pearson Education,
Current literature.
E0 247 (AUG/JAN) 3:0
Sensor Networks
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.
Pre-requisite: Consent of Instructor
Raghavendra, C.S., Shivalingam, K.M., and
Znati, T., Wireless Sensor Networks, Springer,
F. Zhao and L.Guibas, Wireless Sensor
Networks, An Information processing Approach, Morgan Kauffmann, San Fransisco 2004.
Current Literature.
E0 251 (AUG) 3:1
Data Structures and Algorithms
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.
V Susheela
Devi
Aho,
A.V., Hopcroft, J.E., and Ullman,
J.D., Data Structures and Algorithms, Addison Wesley,
Cormen,
T.H., Leiserson, C.E., and Rivest,
R.L., Introduction to Algorithms, The MIT Press,
Weiss, M.A., Data Structures and Algorithms Analysis in C++,
Benjamin/Cummins,
E0 253 (AUG) 3:1
Operating Systems
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.
K GOPINATH
Tanenbaum,
A.S., Modern Operating Systems, Second Edn, Pearson
Education, Inc., 2001.
Uresh
Vahalia, UNIX Internals, The New Frontiers, Prentice Hall,
1996.
Mauro, J., and McDougall, R., Solaris Internals: Core Kernel Architecture,
Sun Microsystems Press, 2001.
Daniel P. Bovet and Marco Cesati, Understanding
the Linux kernel", Second Edn, O'Reilly &
Associates, Inc., 2003.
E0
254 (AUG) 3:1
Network
and Distributed Systems Security
Security violations and goals, security requirements and services,
attack on security and security mechanisms, shared secret key and
Public-Private key pair; discrete logs,
Encryption/Decryption functions, Hash functions, MAC functions, security requirements and algorithmic implementation of
one-way functions; OS security violations
and techniques to prevent them. Access control models, secure programming techniques, authenticated Diffie-Hellman key establishment protocols, group key establishment protocols, block
ciphers and stream ciphers, modes of encryption, Nonce, Timestamps and
Authentication Protocols. Digital signatures and source non-repudiation
protocols. PKI and X.509 Authentication Service, BAN logic, 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.
R C Hansdah
Stallings, W.,
Cryptography and Network Security: Principles and Practices, Fourth Edn, Prentice Hall, 2006.
Daswani, N., Kern, C., and Kesavan, A., 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.
Prerequisites:
Knowledge of Java is desirable, but not necessary.
E0
255 (JAN) 3:1
Compiler Design
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.
Y
Aho,
A.V., Sethi, R., and Ullman,
J.D., Compilers – Principles, Techniques and Tools, Addison Wesley, 1988.
S. Muchnick., Advanced Compiler Design
and Implementation, Morgan Kauffman, 1998.
Selected Papers.
E0 261
(AUG) 3:1
Database Management Systems
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.
Jayant Haritsa
Elmasri,
R., and Navathe, S.B., Fundamentals of Database
Systems Addison-Wesley, Third ed., 1999.
Ramakrishnan,
R., and Gehrke, J., Database Management Systems,
McGraw Hill, Second Edn, 1999.
Stonebraker,
M., and Hellerstein, J.,
Stonebraker,
M., Object-Relational DBMSs, Morgan Kaufmann, 1996 .
Mattison,
R., Data Warehousing (Strategies,Technologies and
Techniques), IEEE Press, 1998.
R. Groth, Data Mining, Prentice Hall,
1998.
Recent Conference and Journal papers.
Prerequisites: Data
Structures, C or C++, Undergraduate course in DBMS
E0
262 (JAN) 3:0
Multimedia Information Systems
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 Venkataraman/Anandi Giridharan
Venkataram,
P., Design Aspects of Multimedia Information Systems, Pearson Publishers, 2008.
Grosky,
W.I., Jain, R., and Mehrotra, R., The Hand Book of
Multimedia Information Management, Prentice-Hall, 1997.
Buford, J.F.K., Multimedia
Systems, Addison-Wesley, 1994.
Relevant Research Papers from the Journals/Conferences
E0 264 (JAN) 3:1
Distributed Computing Systems
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. Group membership protocols and security issues in group membership
problems. 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. Implications of security issues in distributed consensus
and agreement protocols, replicated data
management, self-stabilizing systems. Design
issues in specialized distributed systems.
R C Hansdah
Chow, R.,
and Johnson, T., Distributed Operating Systems and Algorithms, Addison-Wesley,
1997.
Ghosh,
S., Distributed Systems: An Algorithmic Approach, CRC Press, 2006.
Birman,
K.P., Reliable Distributed Systems: Technologies, Web Services, and Applications, Springer
Coulouris,
G., Dollimore, J., and Kindberg,
T., Distributed Systems: Concepts and Designs,
Fourth Edn,
Pearson Education Ltd., 2005.
Current
Literature
Prerequisites:
NDSS (E0 254) or equivalent course
E0 265 (JAN) 3:0
Multimedia Systems
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.
K R Ramakrishnan
Pre-requisites: Basic knowledge of DSP and Programming
Raghavan, S.V., and Tripathi, S.K.,
Networked Multimedia Systems: Concepts, Architecture and Design.
Steinmetz, R., and Klara Nahrtedt,
Multimedia: Computing, Communication and Application, Prentice Hall, 1995.
E0 266 (AUG) 3:0
Topics in Ubiquitous Computing
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.
P Venkataraman
Prerequisite: Communication
Protocols/Computer
Networks
Research papers on
Ubiquitous Computing.
E0 268 (JAN) 3:1
Data Mining
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.
S K Shevade
Tan P-N, Steinbach, M., and Kumar, V., Introduction to Data
Mining, Addison-Wesley, 2006.
Current Literature.
E0 271 (AUG) 3:1
Computer Graphics
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.
Vijay Natarajan
Angel, E.S., Interactive Computer Graphics, A top-down
approach with OpenGL, Addison-Wesley, 2005.
Shreiner,
D., Woo, M., Neider, J., and Davis, T., OpenGL
Architecture Review Board, OpenGL Programming Guide: The Official Guide to
Learning OpenGL, Addison-Wesley, 2005.
Hearn, D.,
and Baker, M.P., Computer Graphics with OpenGL, Prentice Hall, 2003.
Prerequisites:
Courses in linear algebra, data structures, algorithms, and programming.
E0 284 (AUG) 2:1
Digital VLSI Circuits
Introduction to MOS
transistor theory, circuit characterization and simulation, theory of logical
effort, interconnect design and analysis combinational circuit design,
sequential circuit design. Design
methodology and tools, testing and verification, datapath
subsystems, array subsystems, power and clock distribution. Introduction to
packaging.
Bharadwaj
Amrutur
Weste, N., and Harris, D., CMOS VLSI
Design – A Circuits and Systems Perspective, Addison Weley,
2005.
Rabaey, J.M., Chandrakasan,
A., and Nikolic, B., Digital Integrated Circuits.
E0 285 (JAN) 3:0
Computer Aided Design of
VLSI systems
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.
Virendra Singh and S K Nandy
References?
E0 320 (AUG) 3:1
Topics in Graph Theory
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.
L Sunil Chandran
Reinhard
Diestel, Graph Theory (Chapters 8 and 12), Springer,
2000.
Current Literature.
E0 323 (AUG) 3:1
Topics in Verification
Abstraction refinement techniques, softwafe
model checking, applications of machine learning to program verification,
static analysis and type checking, program logics, programming language design,
design procedures.
Aditya
Kanade
Selected Papers and recent
literature
E0 330 (AUG)
3:1
Convex Optimization
Convex sets and functions, Convex Optimization Problems, Duality,
Approximation and fitting, Statistical
Estimation, Geometric Problems, Unconstrained minimization, Equality constrained minimization, Interior-point
methods.
S K Shevade
Boyd, S., and Vandenberghe, L., Convex
Optimization,
E0 343 (JAN) 3:1
Topics in Computer Architecture
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.
T Matthew Jacob
Pre-requisites: Computer Architecture, Operating Systems, Some
Familiarity with Analytical Performance Evaluation Techniques.
E0 355
(Aug) 3:1
Topics in
Compiler Design
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
Srikant, Y.N., and Priti
Shankar (ed.), The Compiler Design Handbook: Optimizations and Machine Code
Generation, Second Edn, CRC Press, 2008.
Prerequistes: Good knowledge of dataflow analysis and
compiler optimizations
E0 361 (JAN) 3:1
Topics in Database Systems
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.
Jayant Haritsa
Stonebraker,
M. (ed.),
Conference and Journal papers.
E0 374 (JAN) 3:1
Topics in Combinatorial Geometry
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.
Satish Govindarajan
Pach,
J., and Agarwal, P.K., Combinatorial Geometry, Wiley,
1995.
Matousek,
J., Lectures on Discrete Geometry, Springer Verlag,
2002.
Current Literature.
Prerequisites: The registrants should have preferably completed
the "Design and Analysis of
Algorithms" or "Discrete Structures" course.
E0 375 (JAN)
3:1
Modern
Applications of Automata Theory
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.
Deepak D’Souza and Priti Shankar
Wolfgang
Thomas, Applied Automata Theory (Electronic notes, RWTH Aachen).
Current
literature.
Prerequisites: A course on Automata Theory equivalent to E0
222.