1. Set Theory : Basic Concepts of Set Theory: Definitions. lnclusion, Equality of Sets, Cartesian product, The Power Set, Some operations οη Sets, Venn Diagrams. Some Basic Set ldentities. Functions : Introduction & definition, Co-domain, range, image, value of a function: Examples, surjective, injective, bijective: examples; Composition of functions, examples; Inverse function, ldentity 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 (Chapter - ι. 2, 3) 2. 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 (Chapter - 4, 5) 3. Relations : Definition, Binary Relation, Representation, Domain, Range, Universal Relation, Void Relation, Union, Intersection, and Complement Operations οη Relations, Properties of Binary Relations ίη 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 ίη Set Χ (iv) Partial Ordering : Definition, Examples, Simple or Linear Orderinq, Totally Ordered Set (Chain). Frequently Used Partia!Iy Ordered Relations, Representation of Partially Ordered Sets, Hesse Diaqrams, Least & Greatest Members, Minimal & Maximal Members, Least Upper Bound (Supremum). Greatest Lower Bound (infimum). We!I-ordered Partia!Iy Ordered Sets (Posets). Lattice as Posets, complete, distributive modular and complemented Iattices Boolean and pseudo Boolean Iattices. (Definitions and simple examples only) Recurrence Relation : Introduction, Recursion, Recurrence Relation, Solvinq, Recurrence Relation. (Chapter - 6, 7, 8) 4. Algebraic Structures : Alqebraic structures with one binary operation Semiqroup, Monoid, Group, Subqroup, normal subqroup, qroup Permutations. Coset, homomorphic subqroups, Laqranqe's theorem. Conqruence relation and quotient structures. Alqebraic structures (Definitions and simple examples only) with two binary operation- Rinq, Inteqral domain and field. (Chapter - 9) 5. Graphs : Introduction, definition, examples; Nodes, edqes, adjacent nodes. directed and undirected edqe, Directed qraph, undirected qraph, examples; lnitiatinq and terminatinq nodes, Loop (slinq), Distinct edqes, Para!Iel edqes, Multi-qraph, simple qraph, weiqhted qraphs. examples, Isolated nodes, Nu!I qraph; Isomorphic qraphs, examples; Deqree, lndeqree, out-deqree. total deqree of a node, examples; Subqraphs, definition, examples; Converse (reversal or directional duaI) of a diqraph, examples; Path : Definition. Paths of a qiven qraph, lenqth of path. examples; Simple path (edqe simple). elementary path (node simple). examples; Cycle (circuit), elementary cycle, examples; Reachability : Definition. qeodesic, distance. examples; Properties of reachability, the trianqle inequality; Reachable set of a qiven node, examples, Node base, examples; Connectedness : Definition. weaRly connected, stronqly connected. unilatera!Iy connected. examples; Stronq, weaR, and unilateral components of a qraph, examples, Applications to represent Resource allocation status of an operatinq system, and detection and correction of deadlocRs; Matrix representation of qraph : Definition, Adjacency matrix, boolean (or bit) matrix, examples; Determine number of paths of Ienqth η throuqh Adjacency matrix, examples; Path (Reachability) matrix of a qraph, examples; Warsha!I's alqorithm to produce Path matrix, Flowchart. Trees : Definition, branch nodes, leaf (terminaI) nodes, root, examples: Different representations of a tree, examples; Binary tree, m-ary tree, Fu!I (or complete) binary tree, examples; Convertinq any m-ary tree to a binary tree. examples; Representation of a binary tree : LinRed-list; Tree traversal : Pre-order. in-order. post-order traversal, examples, alqorithms; Applications of List structures and qraphs. (Chapters - 10, 11)
