BITM Discrete Structure

Propositional logic. Logical Operators (AND, OR, NOT, IMPLICATION with its variants, BICONDITIONAL). Laws of logical equivalences. Translating English sentences. Predicate and Quantifiers. Nested and Order in quantifiers. Translating English sentences using quantifiers. Rules of inferences for propositional logic. Valid arguments in propositional logic. Fallacies. Rules of inferences for quantified statements. Valid arguments in quantified statements. Methods of Proving Theorems (Direct Proof, Indirect Proof, Proof by Contradiction, Vacuous and Trivial Proof, Proof of Equivalence, Exhaustive Proof, Proof by Cases, Existence Proof, Uniqueness Proof, Counter Example). Mistakes in Proof.

Sets. Ways to describe the sets. Venn diagram. Subset. Size of a set. Power set. Cartesian product. Set operations. Set identities. Computer representations of set. Functions. One to one function. Onto function. Bijection. Inverse functions. Composition of functions. Graph of functions. Floor functions. Ceiling functions. Sequence and Summations. Boolean matrices. Meet and Join operation on Boolean matrices.

The division algorithm. Modular Arithmetic. Representation of Integers. Algorithms for Integer Operations. Primes. Greatest Common Divisors. Linear Congruences. The Chinese Remainder Theorem. Computer Arithmetic with Large Integers.

Introduction to Mathematical Induction. Proof by Mathematical Induction. Strong Induction. Well Ordering Property. Recursively Defined Functions and Sets. Structural Induction. Generalized Induction. Recursive Algorithms. Proving the Correctness of Recursive Algorithms.

Sum Rule. Product Rule. Principle of Inclusion – Exclusion. The Pigeonhole Principle (Generalized as well). Permutations and Combinations. Binomial Theorem. Pascal's Identity and Triangle. Generalized Permutations and Combinations. Permutations with Repetitions. Combinations with Repetitions. Permutations with Indistinguishable Objects.

Introduction. Finite Probability. Probabilities of Complements and Unions of Events. Assigning Probabilities. Conditional Probability. Independence. Random Variable. The Birthday Problem. Expected Value.

Recurrence Relations. Modeling with Recurrence Relations. Solving Linear Homogeneous Recurrence Relations with Constant Coefficients (Without Proving the Theorem). the Degree of Two Case (Two Distinct or Equal Characteristic Roots). the General Case (the Degree may be Greater than Two, where the Characteristic Equation has Distinct Roots or Repeated Roots).

Relation and its Properties. n – ary Relations. Representing Relations (using Matrix and Digraphs). Closure of Relations (Reflexive, Symmetric, Transitive). Warshall's Algorithm to Compute the Transitive Closure of a Relation. Equivalence Relations. Equivalence Classes. Partial Ordering.

Graph Models. Types of Graphs (Simple Graph, Multigraph, Pseduograph, Directed Graph, Null Graph, Bipartite Graph). Graph Terminologies (Adjacent Vertices, Degree of a Vertex, Isolated Vertex, Pendant Vertex). Handshaking Theorem. Representation of Graphs (Adjacency List, Adjacency Matrix, Incidence Matrix). Graph Isomorphism. Graph Connectivity. Euler and Hamilton Path. Necessary and Sufficient Conditions for Euler and Hamilton Path and Circuits (Without Proof). Shortest Path Algorithm (Dijkstra's Algorithm). Planar Graph. Graph Coloring.

Introduction to Trees. Rooted Tree. Terminologies of a Tree (Parent, Child, Sibling, Ancestors, Descendants, Leaf, Internal Nodes). M – ary Tree. Binary Search Tree. Decision Tree. Prefix Codes. Tree Traversal. Spanning Tree. Minimum Spanning Tree. Kruskal's Algorithm.