Mathematical Foundations for Computer Science

Credit: 3

 

Objective

  • Study the fundamental concepts of logic, abstract algebra, linear algebra, probability and statistics, graph theory etc.

 

Unit I

Functional Logic: Proposition Logic, Resolution Proof system, Predicate logic. Congruences, Fermat's theorem, Euler function, Chinese remainder theorem.

 

Unit II

Groups, homomorphism theorems, cosets and normal subgroups, Lagrange’s theorem, Ring. Field. Linear algebra: Vector Space, Basis, Matrices and Linear Transformations, Eigen values, Orthogonality.

 

Unit III

Counting, Probability, Discrete random variable, Continuous random variable, Moment generating function, Markov’s inequality, Chebyshev’s inequality, The geometric and binomial distributions, The tail of the binomial distribution.

 

Unit IV

Graphs, Euler tours, planar graphs, Hamiltonian graphs, Euler's formula, applications of Kuratowski's theorem, graph colouring, chromatic polynomials, trees, weighted trees, the max-flow min-cut theorem.

 

Unit V

Turing Machines, Recursive and Recursively Enumerable languages. Cantor’s Diagonalization theorem. Complexity classes - NP-Hard and NP-complete Problems - Cook's theorem NP completeness reductions. Approximation algorithms.

 

Outcome

  • Will be able to use mathematical foundations in many areas of computer science like algorithms, computer networks, cryptography, etc.

 

Text Books

 

  1. Donald F. Stanat and David F. McAllister, Discrete mathematics in Computer Science.

  2. Thomas Koshy, Elementary number theory with Applications, Elsevier

  3. I.N.Herstein, Topics in Algebra.JOHN Wiley & SONS. 1990.

  4. Sheldon M. Ross, Introduction to Probability Models, Elsevier.

  5. H. Cormen, C. E. Leiserson, R. L. Rivest, C Stein, Introduction to Algorithms, Prentice Hall India.

  6. Sara Baase and Alan Van Van Gelder. Computer Algorithms: Introduction to Design and Analysis. Addison – Wiley, 2000.

  7. G. Chartrand and P. Zhang, Introduction to Graph Theory, McGraw-Hill Companies,

  8. Douglas B. West, Introduction to Graph Theory, Prentice Hall of India.

  9. Linear Algebra 2nd Edition (Paperback) by Kenneth Hoffman, Ray Kunze, PHI Learning, 2009.