Course Structure and Syllabus for MSc in Mathematics and Computing (to be applicable from 2011 batch onwards)
Semester-1
Course No.	Course Name	L	T	P	C
MA 501	Discrete Mathematics	4	0	0	8
MA 511	Computer Programming	3	0	2	8
MA 521	Modern Algebra	3	1	0	8
MA 522	Linear Algebra	3	1	0	8
MA 541	Real Analysis	3	1	0	8
		15	4	2	40
Semester-2
Course No.	Course Name	L	T	P	C
MA 512	Data Structures and Algorithms	3	0	0	6
MA 513	Formal Languages and Automata Theory	3	0	0	6
MA 542	Differential Equations	4	0	0	8
MA 547	Complex Analysis	3	1	0	8
MA 591	Optimization Techniques	3	1	0	8
MA 515	Data Structures Lab with Object-Oriented Programming*	0	1	2	4
		16	3	2	40
Semester-3
Course No.	Course Name	L	T	P	C
MA 514	Theory of Computation	3	0	0	6
MA 543	Functional Analysis	3	1	0	8
MA 572	Numerical Analysis	3	0	2	8
MA 590	Probability Theory and Random Processes	3	1	0	8
MA XXX	Elective – I	3	0	0	6
MA 697	Seminar	0	0	3	3
		15	2	5	39
Semester-4:
Course No.	Course Name	L	T	P	C
MA 571	Numerical Linear Algebra	3	0	2	8
MA 573	Numerics of Partial Differential Equations	3	0	2	8
MA XXX	Elective – II	3	0	0	6
MA XXX	Elective-III	3	0	0	6
MA 699	Project	0	0	12	12
		12	0	16	40
Total No. of Credits: 159

MA 501 Discrete Mathematics (4-0-0-8)

Set theory – sets, relations, functions, countability; Logic – formulae, interpretations, methods of proof, soundness and completeness in propositional and predicate logic; Number theory – division algorithm, Euclid's algorithm, fundamental theorem of arithmetic, Chinese remainder theorem, special numbers like Catalan, Fibonacci, harmonic and Stirling; Combinatorics – permutations, combinations, partitions, recurrences, generating functions; Graph Theory – paths, connectivity, subgraphs, isomorphism, trees, complete graphs, bipartite graphs, matchings, colourability, planarity, digraphs; Algebraic Structures – semigroups, groups, subgroups, homomorphisms, rings, integral domains, fields, lattices and Boolean algebras.

Texts:

1. C. L. Liu, Elements of Discrete Mathematics, 2^nd Ed., Tata McGraw-Hill, 2000.

2. R. C. Penner, Discrete Mathematics: Proof Techniques and Mathematical Structures, World Scientific, 1999.

References:

1. R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, 2^nd Ed., Addison-Wesley, 1994.

2. K. H. Rosen, Discrete Mathematics & its Applications, 6^th Ed., Tata McGraw-Hill, 2007.

3. J. L. Hein, Discrete Structures, Logic, and Computability, 3^rd Ed., Jones and Bartlett, 2010.

4. N. Deo, Graph Theory, Prentice Hall of India, 1974.

5. S. Lipschutz and M. L. Lipson, Schaum's Outline of Theory and Problems of Discrete Mathematics, 2^nd Ed., Tata McGraw-Hill, 1999.

6. J. P. Tremblay and R. P. Manohar, Discrete Mathematics with Applications to Computer Science, Tata McGraw-Hill, 1997.

MA 511 Computer Programming ( 3-0-2-8 )

Introduction – the von Neumann architecture, machine language, assembly language, high level programming languages, compiler, interpreter, loader, linker, text editors, operating systems, flowchart; Basic features of programming (Using C) – data types, variables, operators, expressions, statements, control structures, functions; Advance programming features – arrays and pointers, recursion, records (structures), memory management, files, input/output, standard library functions, programming tools, testing and debugging; Fundamental operations on data – insert, delete, search, traverse and modify; Fundamental data structures – arrays, stacks, queues, linked lists; Searching and sorting – linear search, binary search, insertion-sort, bubble-sort, selection-sort; Introduction to object oriented programming.

Programming laboratory will be set in consonance with the material covered in lectures. This will include assignments in a programming language like C and C++ in GNU Linux environment.

Texts:

1. A. Kelly and I. Pohl, A Book on C, 4^th Ed., Pearson Education, 1999.

References:

1. H. Schildt, C: The Complete Reference, 4^th Ed., Tata Mcgraw Hill, 2000.

2. B. Kernighan and D. Ritchie, The C Programming Language, 2^nd Ed., Prentice Hall of India, 1988.

3. B. Gottfried and J. Chhabra, Programming With C, Tata Mcgraw Hill, 2005.

MA 521 Modern Algebra (3 1 0 8)

Prerequisites: Nil

Review of Groups, Subgroups, Homomorphisms, Group actions, Sylow theorems, Generators and Relations, Free groups, Solvable and Nilpotent groups. Rings, Ideals and Quotient rings, Maximal, Prime and Principal ideals, Euclidean and Polynomial rings, Modules. Field extensions, Finite fields, Algebraically closed fields.

 Texts / References:

1. M. Artin, Algebra, Prentice Hall India, 1994.

2. I. N. Herstein, Topics in Algebra, 2^nd Ed, Wiley Eastern, 1975.

3. C. Musili, Introduction to Rings and Modules, 2^nd Ed, Narosa, 1992.

4. F. Loonstra, Introduction to Algebra, McGraw Hill, London, 1969.

MA 522 Linear Algebra (3 1 0 8)

 Prerequisites: Nil

Systems of linear equations, Vector spaces, Bases and dimensions, Change of bases and change of coordinates, Sums and direct sums, Quotient spaces. Linear transformations, Representation of linear transformations by matrices, The rank and nullity theorem, Dual spaces, Transposes of linear transformations. Trace and determinant, Eigenvalues and eigenvectors, Invariant subspaces, Direct-Sum decomposition, Cyclic subspaces and Annihilators, The minimal polynomial, The Jordan canonical form. Inner product spaces, Orthonormal bases, Gram-Schmidt process. Adjoint operators, Normal, Unitary, and Self-adjoint operators, Spectral theorem for normal operators.

Texts / References:

1.        K. Hoffman and R. Kunze, Linear Algebra, Prentice Hall India, 1996.

2.        G. Schay, Introduction to Linear Algebra, Narosa, 1997.

3.        G. C. Cullen, Linear Algebra with Applications, 2^nd Ed, Addison Wesley, 1997.

4.        S. Axler, Linear Algebra Done Right, 2^nd ed, UTM, Springer, 1997.

5.        K. Janich, Linear Algebra, UTM, Springer, 1994

MA 541 Real Analysis (3 1 0 8)

 Prerequisites: Nil

Sequences and Series of functions, Uniform convergence, Equicontinuity, Ascoli’s theorem, Weierstrass approximation theorem. Functions of several variables, Inverse and Implicit function theorems, Multiple integration, Change of variables. Lebesgue measure, Lebesgue integral, Introduction to Lp spaces. Fourier Series.

Texts / References:

1.        W. Rudin, Principles of Mathematical Analysis, 3^rd Ed, McGraw Hill, 1976.

2.        T. M. Apostol, Mathematical Analysis, 2^nd Ed, Narosa, 1985.

3.        H. L. Royden, Real Analysis, 3^rd edition, Prentice Hall India, 1995.

MA 512 Data Structures and Algorithms (3-0-0-6)

Pre-requisite: MA 511 or equivalent.

Asymptotic notation; Sorting – merge sort, heap sort, priortiy queue, quick sort, sorting in linear time, order statistics; Data structures – heap, hash tables, binary search tree, balanced trees (red-black tree, AVL tree); Algorithm design techniques – divide and conquer, dynamic programming, greedy algorithm, amortized analysis; Elementary graph algorithms, minimum spanning tree, shortest path algorithms.

Texts:

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 2^nd Ed.,

Prentice-Hall of India, 2007.

References:

1.M. T. Goodrich and R. Tamassia, Data Structures and Algorithms in Java, Wiley, 2006.

2.A.V. Aho and J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley, 1983.

3.S. Sahni, Data Structures, Algorithms and Applications in C++, 2^nd Ed., Universities Press, 2005.

MA 513 Formal Languages and Automata Theory (3 0 0 6)

Prerequisite: MA 501 or equivalent.

Alphabets, languages, grammars; Finite automata, regular languages, regular expressions; Context-free languages, pushdown automata, DCFLs; Context sensitive languages, linear bounded automata; Turing machines, recursively enumerable languages; Operations on formal languages and their properties; Chomsky hierarchy; Decision questions on languages.

Texts:

1. J. E. Hopcroft, and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Narosa, 1979.

References:

1. M. Sipser, Introduction to the Theory of Computation, Thomson, 2004.
2. H. R. Lewis, C. H. Papadimitriou, Elements of the Theory of Computation, Pearson Education Asia, 2001.
3. D. C. Kozen, Automata and Computability, Springer-Verlag, 1997.

MA 542 Differential Equations (4 0 0 8)

Prerequisites: Nil

Review of fundamentals of ODEs, Existence and uniqueness theorems, Power series solutions of ODE, Systems of Linear ODEs, Reduction of higher order linear ODEs to first order linear systems, Stability of linear systems, Sturm-Liouville problems. First order linear and quasi-linear PDEs, The Cauchy problem, Classification of PDEs, Characteristics, Well-posed problems, Solutions of hyperbolic, parabolic and elliptic equations, Dirichlet and Neumann problems, Maximum principles, Greens functions for elliptic, parabolic and hyperbolic equations.

Texts / References:

1.        E. A. Coddington and N. Levinson, Theory of Ordinary Differential Equations, Tata McGraw Hill, 1990.

2.        P.F. Hsieh and Y. Sibuya, Basic Theory of Ordinary Differential Equations, UTX, Springer, 1999.

3.        I. N. Sneddon, Elements of Partial Differential Equations, McGraw Hill, 1957.

4.        F. John, Partial Differential Equations, Springer Verlag, 1982.

5.        W. E. Willams, Partial Differential Equations, Oxford, 1980.

6.        W.A. Strauss, Partial Differential Equations: An Introduction, John Wiley, 1992.

MA 547 Complex Analysis (3 1 0 8)

Prerequisites: Nil

Spherical representation of extended complex plane, Analytic functions, Harmonic functions, Elementary functions, Branches of multiple-valued functions, Mappings of elementary functions, Bilinear transformations, Conformal mappings and Computational aspects. Complex integration, Cauchy’s integral theorem, Cauchy’s integral formula, Theorems of Morera and Liouville, Maximum-Modulus theorem, Power series, Taylor’s theorem and analytic continuation, Zeros of analytic functions, Hurwitz theorem, Singularities, Laurent’s theorem, Casorati-Weierstrass theorem, Argument principle, Theorems of Rouche and Gauss-Lucas, Residue theorem and its applications to evaluate real integrals and to compute the inverse Laplace transform, Contour integration of functions with branch points.

Texts / References:

1.        L. V. Ahlfors, Complex Analysis, 3^rd Ed, McGraw Hill, 1979

2.        R.V. Churchill and J. W. Brown, Complex Variables and Applications, 6^th Ed, McGraw Hill, 1995.

3.        J. H. Mathews and R. W. Howell, Complex Analysis for Mathematics and Engineering, 3^rd Ed, Narosa, 1998.

4.        E. B. Saff and A. D. Snider, Fundamentals of Complex Analysis with Applications to Engineering, Science and Mathematics, 3^rd Ed, Prentice Hall, 2002.

MA 591 Optimization Techniques (3-1-0-8)

Mathematical foundations and basic definitions: concepts from linear algebra, geometry, and multivariable calculus. Linear

optimization: formulation and geometrical ideas of linear programming problems, simplex method, revised simplex

method,duality, sensitivity snalysis, transportation and assignment problems. Nonlinear optimization: basic theory, method of

Lagrange multipliers, Karush-Kuhn-Tucker theory, convex optimization. Numerical optimization techniques: line search

methods, gradient methods, Newton’s method, conjugate direction methods, quasi-Newton methods, projected gradient

methods, penalty methods.

Texts:

1. N. S. Kambo, Mathematical Programming Techniques, East West Press, 1997.

2. E.K.P. Chong and S.H. Zak, An Introduction to Optimization, 2^nd Ed., Wiley, 2001 (WSE, 2004).

References:

1. R. Fletcher, Practical Methods of Optimization, 2^nd Ed., John Wiley, 1987.

2. D. G. Luenberger, Linear and Nonlinear Programming, 2^nd Ed., Kluwer, 2003.

3. M. S. Bazarra, J.J. Jarvis, and H.D. Sherali, Linear Programming and Network Flows, 2^nd Ed.,1990. [Also available as

WSE (2003) edition].

4. U. Faigle, W. Kern, and G. Still, Algorithmic Principles of Mathematical Programming, Kluwe, 2002.

5. D.P. Bertsekas, Nonlinear Programming, 2^nd Ed., Athena Scientific, 1999.

6. M. S. Bazarra, H.D. Sherali, and C. M. Shetty, Nonlinear Programming: Theory and Algorithms, 2^nd Ed., John Wiley, 1993.

(WSE, 2004).

MA 515 Data Structures Lab With Object-Oriented Programming (0-1-2-4 )

The tutorials will be based on object-oriented programming concepts such as classes, objects, methods, interfaces, packages, inheritance, encapsulation, and polymorphism. Programming laboratory will be set in consonance with the material covered in MA 512. This will include assignments in a programming language like C++ in GNU Linux environment.

References:

1. T. Budd, An Introduction to Object-Oriented Programming, Addison-Wesley, 2002.

MA 514 Theory of Computation (3-0-0-6)

Prerequisite: MA 513 or equivalent

Models of computation – Turing machine, RAM, µ-recursive function, grammars; Undecidability – Rice's theorem, Post correspondence problem, logical theories; Complexity classes – P, NP, coNP, EXP, PSPACE, L, NL, ATIME, BPP, RP, ZPP, IP.

Texts:

1. M. Sipser, Introduction to the Theory of Computation, Thomson, 2004.

2. H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation, PHI, 1981.

References:

1. J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Narosa, 1979.
2. S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
3. C. H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, 1994.
4. D. C. Kozen, Theory of Computation, Springer, 2006.
5. D. S. Garey and G. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979.

MA 543 Functional Analysis (3 1 0 8)

 Prerequisites: MA 541 (Real Analysis)

Banach spaces, Continuity of linear maps, Hahn-Banach theorem, Open mapping and closed graph theorems, Uniform boundedness principle. Duals and Transposes. Compact operators and their spectra. Weak and Weak* convergence, Reflexivity. Hilbert spaces, Bounded operators on Hilbert spaces. Adjoint operators, Normal, Unitary, Self-adjoint operators and their spectra. Spectral theorem for compact self-adjoint operators.

Texts / References:

1.        B. V. Limaye, Functional Analysis, 2^nd Ed, Wiley Eastern, 1996.

2.        E. Kreyszig, Introduction to Functional Analysis with Applications, John Wiley and Sons, 1978.

MA572 NUMERICAL ANALYSIS (3-0-2-8)

Prerequisites: Nil

Definition and sources of errors, Propagation of errors, Backward error analysis, Sensitivity and conditioning, Stability and accuracy, Floating-point arithmetic and rounding errors. Nonlinear equations, Bisection method, Newton's method and its variants, Fixed point iterations, Convergence analysis. Newton’s method for non-linear systems. Finite differences, Polynomial interpolation, Hermite interpolation, Spline interpolation, B-splines. Numerical integration, Trapezoidal and Simpson's rules, Newton-Cotes formula,Gaussian quadrature, Richardson Extrapolation. IVP: Taylor series method, Euler and modified Euler

methods, Runge-Kutta methods, Multistep methods, Predictor-Corrector method. Accuracy and stability, Solution for Stiff equations. BVP: Finite difference method, Collocation method, Galerkin method.

Texts / References:

1. M. T. Heath, Scientific Computing: An Introductory Survey, McGraw Hill, 2002.

2. S. D. Conte and Carl de Boor, Elementary Numerical Analysis - An Algorithmic Approach, 3^rd Edition, McGraw Hill, 1980.

3. K. E. Atkinson, Introduction to Numerical Analysis, 2nd Edition, John Wiley, 1989.

4. C. F. Gerald and P. O. Wheatley, Applied Numerical Analysis, 5th edition, Addison Wesley, 1994.

MA 590 Probability Theory and Random Processes (3-1-0-8)

Axiomatic construction of the theory of probability, independence, conditional probability, and basic formulae, random variables, probability distributions, functions of random variables; Standard univariate discrete and continuous distributions and their properties, mathematical expectations, moments, moment generating function, characteristic functions; Random vectors, multivariate distributions, marginal and conditional distributions, conditional expectations; Modes of convergence of sequences of random variables, laws of large numbers, central limit theorems. Definition and classification of random processes, discrete-time Markov chains, Poisson process, continuous-time Markov chains, renewal and semi-Markov processes, stationary processes, Gaussian process, Brownian motion, filtrations and martingales, stopping times and optimal stopping.

Texts/References:

1. G. R. Grimmett and D. R. Stirzaker, Probability and Random Processes, 3rd Edition, Oxford University Press, 2001.

2. P. G. Hoel, S. C. Port and C. J. Stone, Introduction to Probability Theory, Universal Book Stall, 2000.

3. W. Feller, An Introduction to Probability Theory and its Applications, Vol. 1, 3rd Edition, Wiley, 1968 (WSE Edition).

4. K. S. Trivedi, Probability and Statistics with Reliability, Queuing, and Computer Science Applications, 2nd Edition, Wiley, 2001 (WSE Edition).

5. A. Papoulis and S. Unnikrishna Pillai, Probabilities, Random Variables and StochasticProcesses, 4th Edition, Tata McGraw-Hill, 2002.

6. S.M. Ross, Stochastic Processes, 2nd Edition, Wiley, 1996 (WSE Edition).

7. J. Medhi, Stochastic Processes, 3rd Edition, New Age International, 2009.

MA571 Numerical Linear Algebra (3-0-2-8)

Prerequisites: MA522 Linear Algebra

Fundamentals. Linear systems, LU decompositions, Gaussian elimination with partial pivoting, Banded systems, Positive definite systems, Cholesky decomposition. Vector and matrix norms, Perturbation theory of linear systems, Condition numbers, Estimating condition numbers, IEEE floating point arithmetic, Analysis of roundoff errors. Gram-Schmidt orthonormal process, Orthogonal matrices, Householder transformation, Givens rotations, QR factorization, Roundoff error analysis of orthogonal matrices, Stability of QR factorization.

Solution of linear least squares problems, Normal equations, Singular Value Decomposition(SVD), Polar decomposition, Moore-Penrose inverse, Rank deficient least squares problems, Sensitivity analysis of leastsquares problems. Review of eigenvalues and canonical forms of matrices, Sensitivity of eigenvalues and eigenvectors, Reduction to Hessenberg and tridiagonal forms, Power and inverse power methods, Rayleigh quotient iteration, Explicit and implicit QR algorithms for symmetric and non-symmetric matrices, Implementation of implicit QR algorithm. Computing the SVD, Sensitivity analysis of singular values and singular vectors. Overview of iterative methods: Jacobi, Gauss-Seidel and successive overrelaxation methods, Krylov subspace method, The Arnoldi and the Lanczos iterations.

Texts/References:

1. L. N. Trefethen and David Bau, Numerical Linear Algebra, SIAM, 1997.

2. D. S. Watkins, Fundamentals of Matrix Computation, Wiley, 1991.

3. G. H. Golub and C.F.Van Loan, Matrix Computation, John Hopkins U. Press, Baltimore, 1996.

4. G. W. Stewart, Introduction to Matrix Computations, Academic Press, 1973.

5. J.W. Demmel, Applied numerical linear algebra, SIAM, Philadelphia, 1997.

MA573 Numerics of Partial Differential Equations (3-0-2-8)

Prerequisites: Nil

Finite difference methods for Parabolic, Elliptic and Hyperbolic equations. Dirichlet, Neumann and Mixed problems. Sparseness and the ADI method, Iterative methods for Laplace equation. Backward Euler, Crank-Nicolson schemes, Stability and convergence analysis, Lax's equivalence theorem. Method of characteristics, Lax-Wendroff explicit method, CFL conditions, Wendroff implicit approximation. Introduction to FEM.

Texts / References:

1. J. D. Hoffman, Numerical methods for Engineers and Scientists, McGraw Hill, 1993.

2. G. D. Smith, Numerical solutions to Partial Differential Equations, Brunel University, Clarendon Press,Oxford, 1985.

3. C. Johnson, Numerical Solution of Partial Differential Equations by the Finite Element Method, Cambridge University Press, 1987.

4. K. Eriksson, D. Estep, P. Hansbo and C. Johnson, Computational Differential Equations, Cambridge University Press, 1996.

5. L. Lapidus and G. F. Pinder, Numerical Solution of Partial Differential Equations in Science and Engineering, John Wiley, 1982.

6. H. P. Langtangen, Computational Partial Differential Equations Springer Verlag, 1999.