Sr. No.

Content

Total 
Weightage 

Set Theory:

Basic Concepts of Set Theory: Definitions, Inclusion, Equality of Sets,
Cartesian product, The Power Set, Some operations on Sets, Venn Diagrams, Some
Basic Set Identities

Functions:

Introduction & definition, Co-domain, range, image, value of a function;
Examples, surjective, injective, bijective; examples; Composition of functions,
examples; Inverse function, Identity map, condition of a function to be invertible,
examples; Inverse of composite functions, Properties of Composition of functions;

Counting:

The Basics of Counting, The Pigeonhole Principle, Permutations and
Combinations, Binomial Coefficients, Generalized Permutations and Combinations,
Generating Permutations and Combinations

Propositional Logic:

Definition, Statements & Notation, Truth Values, Connectives,
Statement Formulas & Truth Tables, Well-formed Formulas, Tautologies,
Equivalence of Formulas, Duality Law, Tautological Implications, Examples

Predicate Logic:

Definition of Predicates; Statement functions, Variables,
Quantifiers, Predicate Formulas, Free & Bound Variables; The Universe of Discourse,
Examples, Valid Formulas & Equivalences, Examples

Relations:

Definition, Binary Relation, Representation, Domain, Range, Universal
Relation, Void Relation, Union, Intersection, and Complement Operations on
Relations, Properties of Binary Relations in a Set: Reflexive, Symmetric, Transitive,
Anti-symmetric Relations, Relation Matrix and Graph of a Relation; Partition and
Covering of a Set, Equivalence Relation, Equivalence Classes, Compatibility Relation,
Maximum Compatibility Block, Composite Relation, Converse of a Relation, Transitive Closure of a Relation R in Set X

Partial Ordering:

Definition, Examples, Simple or Linear Ordering, Totally Ordered Set (Chain), Frequently Used Partially Ordered Relations, Representation of Partially Ordered Sets, Hesse Diagrams, Least & Greatest Members, Minimal & Maximal Members, Least Upper Bound (Supremum), Greatest Lower Bound (infimum), Well- ordered Partially Ordered Sets (Posets). Lattice as Posets, complete, distributive modular and complemented lattices Boolean and pseudo Boolean lattices. (Definitions and simple examples only)

Recurrence Relation:

Introduction, Recursion, Recurrence Relation, Solving,
Recurrence Relation

Algebraic Structures:

Algebraic structures with one binary operation- Semigroup, Monoid, Group, Subgroup, normal subgroup, group Permutations, Coset, homomorphic subgroups, Lagrange’s theorem, Congruence relation and quotient structures. Algebraic structures (Definitions and simple examples only) with two binary operation- Ring, Integral domain and field.

Graphs:

Introduction, definition, examples; Nodes, edges, adjacent nodes, directed and undirected edge, Directed graph, undirected graph, examples; Initiating and terminating nodes, Loop (sling), Distinct edges, Parallel edges, Multi-graph, simple graph, weighted graphs, examples, Isolated nodes, Null graph; Isomorphic graphs, examples; Degree, Indegree, out-degree, total degree of a node, examples; Subgraphs: definition, examples; Converse (reversal or directional dual) of a digraph, examples;

Path:

Definition, Paths of a given graph, length of path, examples; Simple path (edgesimple), elementary path (node simple), examples; Cycle (circuit), elementary cycle, examples;

Reachability:

Definition, geodesic, distance, examples; Properties of reachability, the triangle inequality; Reachable set of a given node, examples, Node base, examples;

Connectedness:

Definition, weakly connected, strongly connected,
unilaterally connected, examples; Strong, weak, and unilateral components of a graph, examples, Applications to represent Resource allocation status of an operating system, and detection and correction of deadlocks; Matrix representation of graph: Definition,
Adjacency matrix, boolean (or bit) matrix, examples; Determine number of paths of length n through Adjacency matrix, examples; Path (Reachability) matrix of a graph, examples; Warshall’s algorithm to produce Path matrix, Flowchart.

Trees:

Definition, branch nodes, leaf (terminal) nodes, root, examples; Different representations of a tree, examples; Binary tree, m-ary tree, Full (or complete) binary
tree, examples; Converting any m-ary tree to a binary tree, examples; Representation of a binary tree: Linked-list; Tree traversal: Pre-order, in-order, post-order traversal,examples, algorithms; Applications of List structures and graphs