Details


1) Set Theory
Introduction to the theory of sets; combination of sets; power sets; finite and infinite sets; principle of inclusion and exclusion; selected problems from each topic.

2)Logic
Proposition, predicate logic, logic operators, logic proposition and proof, method of proofs.

3)Mathematical Induction 
Different forms of the principle of mathematical induction. selected problems on mathematical induction.

4)Discrete Probability 
Counting principles. Random experiment; sample space; events; axioms of probability; conditional probability. Theorem of total probability; Bayes' theorem. Application to information theory: information and mutual information.

5)Graph theory
Path, cycles, handshaking theorem, bipartite graphs, sub-graphs, graph isomorphism, operations on graphs, Eulerian graphs and Hamiltonian graphs, planar graphs, Euler formula, traveling salesman problem, shortest path algorithms.

6)Relations 
Definitions and properties; Equivalence relations and equivalence classes. Representations of relations by binary matrices and digraphs; operations on relations. Closure of a relations; reflexive, symmetric and transitive closures. Warshall's algorithm to compute transitive closure of a relation.

7)Partially Ordered Sets and Lattices 
Partial order relations; POSETS; lattices

8)Boolean Algebra and Boolean Functions Introduction to Boolean algebra and Boolean functions. Different representations of Boolean functions. Application of Boolean functions to synthesis of circuits

9)Discrete Numeric Functions
Introduction of discrete numeric functions; asymptotic behaviour; generating functions.

10)Recurrence Relations 
Linear recurrence relations with constant coefficients (homogeneous case); discussion of all the three sub-cases. Linear recurrence relations with constant coefficients (non-homogeneous case); discussion of several special cases to obtain particular solutions. Solution of linear recurrence relations using generating functions.