Mathematical Foundations of Computer Science

Course Name: 

Mathematical Foundations of Computer Science (MA714)

Programme: 

M.Tech (CSE)

Semester: 

First

Category: 

Programme Core (PC)

Credits (L-T-P): 

03 (3-0-0)

Content: 

Divisibility, gcd, prime numbers, fundamental theorem of arithmetic, Congruences, Fermat's theorem, Euler function, primality testing, solution of congruences, Chinese remainder theorem, Wilson’s theorem. Groups and subgroups, homomorphism theorems, cosets and normal subgroups, Lagrange’s theorem, rings, finite fields, polynomial arithmetic, quadratic residues, reciprocity, discrete logarithms, elliptic curve arithmetic. Fundamental principles of counting, pigeonhole principle, countable and uncountable sets, principle of inclusion and exclusion, derangements, equivalence relations and partitions, partial order, lattices and Boolean algebra, generating functions, recurrence relations, solution of recurrences. Graphs, Euler tours, planar graphs, Hamiltonian graphs, Euler's formula, applications of Kuratowski's theorem, graph colouring, chromatic polynomials, trees, weighted trees, shortest path algorithms, spanning trees, the max-flow min-cut theorem.

References: 

1.Niven, H.S. Zuckerman and Montgomery, "An Introduction to the Theory of Numbers", Third Edition, John Wiley and Sons.
2.R. P. Grimaldi, "Discrete and Combinatorial Mathematics: An Applied Introduction", Third Edition, Addison-Wesley.
3.B. Kolman and R.C. Busby, "Discrete Mathematical Structures for Computer Science", PHI, New Delhi.

Department: 

Computer Science and Engineering
 

Contact us

Dr. Manu Basavaraju
Head of the Department
Department of CSE, NITK, Surathkal
P. O. Srinivasnagar, Mangalore - 575 025
Karnataka, India.
Hot line: +91-0824-2474053
Email: hodcse[AT]nitk[DOT]ac[DOT]in
            hodcse[AT]nitk[DOT]edu[DOT]in

                      

Connect with us

We're on Social Networks. Follow us & get in touch.