**Basic Programming Laboratory**The course will be based on the programming language Haskell.

- Function definitions: pattern matching, induction
- Basic data types, tuples, lists
- Higher order functions
- Polymorphism
- Reduction as computation, lazy evaluation
- Measuring computational complexity
- Basic algorithms: sorting, backtracking, dynamic programming
- User-defined datatypes: enumerated, recursive and polymorphic types
- Input/output

**Recommended Texts**-
R. Bird and P. Wadler,
*Introduction to Functional Programming*Prentice Hall, 1988. -
R. Bird,
*Introduction to Functional Programming using Haskell*, Prentice Hall, 1998. -
Paul Hudak,
*The Haskell school of expression*, Cambridge University Press, 2000. -
Graham Hutton,
*Programming in Haskell*, Cambridge University Press, 2007. -
Bryan O'Sullivan, John Georzen and Don Stewart,
*Real World Haskell*, O'Reilly, 2007.

- Object oriented-programming
- Event driven programming
- Exception handling
- Concurrent programming
- Foundations of functional programming: λ-calculus, type checking
- Logic programming
- Scripting languages
- John C Mitchell,
*Concepts in Programming Languages*, Cambridge University Press, 2003. - Ravi Sethi,
*Programming Languages*, Addison Wesley, 1996. **Theory of Computation**Finite automata---regular languages---pumping lemma--- stack automata---context free languages---applications to compilers---Turing machines---universal Turing machines--- halting problem---non deterministic Turing machines--- complexity classes---P v/s NP.

**Recommended Texts**- J. E. Hopcroft and J. D. Ullman: Introduction to Automata theory, Languages and Computation, Narosa.
- D. Kozen: Automata and Computability, Springer.

**Design and Analysis of Algorithms**Big O notation — sorting and searching — algorithm analysis techniques, recurrences — graph algorithms: DFS, BFS, shortest paths, spanning trees — divide and conquer — greedy algorithms — dynamic programming — data structures: heaps, binary search trees, union-finde — advanced topics: LP, network flows

**Recommended Texts**- T.H. Cormen, C.E. Leiserson, and R.L. Rivest:
*Introduction to algorithms*, Prentice-Hall (1998). - J. Kleinberg and E. Tardos:
*Algorithm design*, Pearson/Addison-Welsey (2006).

- T.H. Cormen, C.E. Leiserson, and R.L. Rivest:
**Mathematical Logic**Propositional and Predicate Logic: syntax, semantics, axiomatic systems, completeness, compactness --- resolution, automated reasoning --- introduction to modal and temporal logics and their use in system specifications.

**Recommended Texts**- D. Ebbinghaus, J. Flum and W. Thomas: Mathematical Logic, Springer-Verlag.
- M. Fitting: First Order Logic and Automated Theorem Proving, Springer Verlag.
- Z. Manna and A. Pnueli: The Temporal Logic of Reactive and Concurrent Systems -- Specification, Springer Verlag.

### Electives

**Discrete Mathematics**Principles of Counting---binomial coefficients---partitions---graphs and algorithms---paths---trees---minimum spanning trees---depth first search ---breadth first search---shortest paths---matchings---generating functions---symmetry and counting---Polya theory.**Recommended Texts**- N. L. Biggs: Discrete Mathematics, Oxford Science Publications.
- J. Nesetril, J. Matousek: Invitation to Discrete Mathematics, Clarendon Press.

**Distributed Systems**Communication models: handshake synchronization, message-passing, shared memory --- Semaphores, monitors, co-routines --- distributed algorithms: leader election, distributed consensus --- clock synchronization --- byzantine agreement --- models: Petri Nets, I/O-automata.

**Recommended Texts**- G. Tel: Introduction to Distributed Algorithms, Cambridge University Press.
- M. Ben-Ari: Principles of Concurrent Programming, Prentice-Hall.
- P. Brinch Hansen: Operating Systems Principles, Prentice-Hall.
- N. Lynch: Distributed Algorithms, Morgan Kaufmann.

**Computer Systems Verification**Specification and verification of concurrent and reactive programs --- Reactive systems: syntax and semantics, fairness requirements --- Specification language -- temporal logic; state, future, and past formulas; deductive systems Program properties: safety, guarantee, obligation, response, persistence, and reactivity --- Verification of programs: proof systems, algorithmic verification of finite-state programs.

**Recommended Texts**- Z. Manna and A. Pnueli: The Temporal Logic of Reactive and Concurrent Systems -- Specification, Springer Verlag.
- E. Clarke, O. Grumberg and D. Peled: Model Checking, MIT Press.

**Complexity Theory:**Turing machines; determinism and non-determinism --- time and space hierarchy theorems; speed-up and tape compression; Blum axioms --- structure of complexity classes NP, P, NL, L, PSPACE; complete problems --- randomness and complexity classes RP, RL, BPP --- alternation, polynomial-time hierarchy --- circuit complexity --- parallel complexity, NC, RNC --- relativized computational complexity --- time-space trade-offs --- Introduction to Interactive Proofs --- Arthur-Merlin Games, IP = PSPACE.

**Recommended Texts**- C. H. Papadimitrou: Computational Complexity, Addison Wesley.
- J. Radhkrishnan, S. Saluja: Interactive Proof Systems, TCS lecture notes, TIFR.

**Operations Research**Linear equations---Gaussian elimination---integral solutions ---Smith normal form---linear functionals--- duality---cones --- Simplex method---introduction to queueing theory--- Elementary Game theory.

**Recommended Texts**- V. Chvatal: Linear Programming, Freeman.
- A. Schrijver: Theory of Integer and Linear Programming, John Wiley.
- K. S. Trivedi: Probability and Statistics with Queuing, Reliability and Computer Science Applications, Prentice-Hall.

**Data Mining and Machine Learning**Association rules, frequent itemsets; Finding high-correlation with low-support; Classifiers -- Bayesian, Nearest Neighbour; Decision Trees; Clustering techniques; Vector space (TF-IDF) model; Stop words and stemming; Supervised learning : Bayesian Networks, Support Vector Machines; Semisupervised learning: Expectation maximization; Web search: HITS and PageRank;**Suggested Textbooks**- Jiawei Han, Micheline Kamber:
*Data mining: concepts and techniques (2nd ed)*, Morgan Kaufman (2006). - Bing Liu:
*Web Data Mining: Exploring Hyperlinks, Contents and Usage Data*, Springer (2006). - Soumen Chakrabarti:
*Mining the Web: Discovering knowledge from hypertext data*, Elsevier (2003). - Christopher D Manning, Prabhakar Raghavan and
Hinrich Schütze :
*An Introduction to Information Retrieval*, Cambridge University Press (2009).

- Jiawei Han, Micheline Kamber:
**Cryptography and Computer Security**Elementary number theory --- Pseudo-random bit generation --- elementary cryptosystems --- number theoretic algorithms (RSA) --- symmetric key cryptosystems - DESIDEA, AES, --- authentication --- digital signatures, electronic commerce (anonymous cash, micropayments), key management--- PGP --- zero-knowledge protocols --- fairness.

**Recommended Texts**- N. Koblitz: A course in number theory and cryptography, GTM, Springer.
- S. C. Coutinho: The Mathematics of Ciphers, A. K. Peters.
- D. Welch: Codes and Cryptography.
- W. Stallings: Cryptography and Network Security.

**Probability and Statistics**discrete probability --- simple random variables --- the law of large numbers---Binomial, Poisson and normal distributions--- central limit theorem---random variables --- expectations and moments --- Markov chains.

**Recommended Texts**- W. Feller, W: An Introduction to Probability Theory and its Applications, Vol.1, John Wiley.
- G. R. Grimmett and D. R. Stirzaker: Probability and Random Processes, Oxford Science Publications.
- K. S. Trivedi: Probability and Statistics with Queuing, Reliability and Computer Science Applications. Prentice-Hall.

**Recommended Texts**