Unit 1
Logic and Proofs: Propositional logic, propositional equivalences, quantifiers, Introduction to proof,
direct proof,proof by contraposition, vacuous and trivial proof, proof strategy, proof by contradiction,
proof of equivalence and counterexamples, mistakes in proof
Unit 2:
Recurrence relations recurrence relation, modelling with recurrence relations, homogeneous linear
recurrence relations with constant coefficients, Method of inverse operator to solve the non
homogeneous recurrence relation with constant coefficient, generating functions, solution of
recurrence relation using generating functions
Unit 3:
Counting principles and relations principle of Inclusion-Exclusion, Pigeonhole, generalized
pigeonhole principle, relations and their properties, combining relation, composition, representing
relation using matrices and graph, equivalence relations, partial and total ordering relations, lattice,
sub lattice, Hasse diagram and its components
Unit 4:
Graphs theory I: graph terminologies, special types of graphs(complete, cycle, regular, wheel, cube, bipartite and complete bipartite), representing graphs, adjacency and incidence matrix, graph
Isomorphism, path and connectivity for undirected and digraphs, Dijkstra's algorithm for shortest path
problem
Unit 5:
Graphs theory II: planner graphs, Euler formula, colouring of a graph and chromatic number, tree graph and its properties, rooted tree, spanning and minimum spanning tree, decision tree, infix, prefix, and postfix notation
Unit 6:
Number theory and its application in cryptography: divisibility and modular arithmetic, primes, greatest common divisors and least common multiples, Euclidean algorithm, Bezout's lemme, linear congruence, inverse of (a modulo m), Chinese remainder theorem, encryption and decryption by
Ceasar cipher and affine transformation, Fermat's little theorem