## Mathematical Foundations of Computer Science

### Course Name:

Mathematical Foundations of Computer Science (MA714)

### Programme:

### Semester:

### Category:

### Credits (L-T-P):

### 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.