KTU Mtech Syllabus : Mathematical Concepts for Computer Science (01CS6401).

Syllabus

Techniques for theorem proving, Logic, Principle of mathematical induction, principle of complete induction. Recursive definitions, Generating functions, Fundamental principles of counting, pigeonhole principle, countable and uncountable sets, principle of inclusion and exclusion – applications, derangements, permutation and combination, theory – Properties of Probability, Methods of Enumeration, Conditional Probability, Independent Events, Bayes Theorem, Mathematical Expectation, Random variables, Stochastic Process, Markov chain, Markov Process, Constrained Optimizations, Queuing Theory,Graphs and algorithms, Groups and subgroups, homomorphism theorems, cosets and normal subgroups, Lagrange’s theorem, rings, fields and Vector Spaces, Norms and Inner product.

COURSE PLAN

Module 1

Techniques for theorem proving: Direct Proof, Proof by Contra position, Proof by exhausting cases and proof by contradiction.Linear-time temporal logic and Branching-time logic-Syntax, Semantics, Practical patterns of specifications, Important equivalences, Adequate sets of connectives.

Module 2

Principle of mathematical induction, principle of complete induction. Recursive definitions, Generating functions, function of sequences calculating coefficient of generating function, solving recurrence relation by substitution and generating functions Solution methods.

Module 3

Fundamental principles of counting, pigeonhole principle, countable and uncountable sets, principle of inclusion and exclusion – applications, derangements,relations,equivalence relations, partitions, Po -sets and lattices.permutation and combination,Pascal’s triangles, binomial theorem. Constrained optimizations-LPP-Graphical ,simplex and big M- methods

Module 4

Probability theory – Properties of Probability, Methods of Enumeration, Conditional Probability, Independent Events, Baye’s Theorem, Mathematical Expectation, Random variables.Stochastic Process, Markov chain, Markov Process, transition matrix. Queuing Theory-Models (M/M/1):00/FCFS), (M/M/1):N/FCFS)and (M/M/s):00/FCFS)

Module 5

Graphs, Terminology Matrices, Euler tours, planar graphs, Hamiltonian graphs, Euler’s formula (proof), Warshall’s algorithm, Spanning trees , Decision Trees, weighted trees.Four colour problem (without proof) and the chromatic number of a graph, five colour theorem, chromatic polynomials

Module 6

Groups and subgroups, homomorphism theorems, co-sets and normal subgroups, Lagrange’s theorem, rings, Field, Vectors paces, Dimension of a Vector space, Norm of a vector and inner products.polynomial arithmetic, quadratic residues, reciprocity, discrete logarithms, elliptic curve arithmetic.

Reference Texts

1. J. P. Tremblay, R. Manohar, “Discrete Mathematical Structures with Application to Computer Science”, Tata McGrawHill, 2000. 
2. Kenneth H. Rosen, “Discrete Mathematics and its Applications”, 7/e, McGraw Hill Inc, 2011. 
3. Robert V. Hogg, Elliot A. Tanis, Meda J. M. Rao, “Probability and Statistical Inference”, 7/e,, Pearson Education India, 2006. 
4. J. Truss, “Discrete Mathematics for Computer Scientists”, 2/e, Addison Wesley, 1999. 
5. Bernard Kolman, Robert C Busby, Sharon Kutler Ross, “Discrete Mathematical Structures”, 2/e, Prentice-Hall India Private Limited, 1996. 
6. Linear Algebra and Probability for computer Science Applications. !st ed.Earnest Davis CRC Press(2012) 
7. Graph Theory and its applications. Jonathan L.Grass and Jay Yellen, CRC(2005) 
8. Fundamentals of Queuing Theory 4th ed.Donald Gross,John F. Shortle,James M.Thompson, Carl M.Haris, ISBN, 978-0-471-79127-0