BITM Discrete Structure
bitmsemester 2
Discrete Structure
Subject Code: ITM153
Course Title: Discrete Structure
Course No: ITM153
Nature of Course: Theory & Practical
Full Marks: 60
Pass Marks: 30
Credit Hours: 3
Course Description
This course introduces students to the concepts of mathematical structures that are fundamentally countable. It provides the toolkit to handle discrete data, things that cannot be divided. Students learn to know about the mathematical background of the pure computing like logic, number theory, set theory, counting techniques, proof techniques, graphs and tree.
Course Objective
By the end of this course, students will be able to
Design truth tables and logical connectives in business contracts
Design Venn diagram to show market segmentation
Design implicative business rules and identifying logical fallacies in marketing
Use counting principles for product bundling
Use binomial theorem in quality control and discrete probability in financial forecasting
Use graph theories in modeling supply chain codes, delivery cost reduction, identifying critical paths in project timelines, analyzing influence within a market
Course Contents
| Course Contents | Teaching Methodology | Teaching Hours |
|---|---|---|
| Unit 1: Logic and Proofs (10 Hrs.) | ||
| Propositional logic | Lecture/Lab | |
| 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 | ||
| Unit 2: Set Theory and Functions (2 Hrs.) | ||
| Sets | Lecture/Lab | |
| 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 | ||
| Unit 3: Number Theory (5 Hrs.) | ||
| The division algorithm | Lecture/Lab | |
| Modular Arithmetic | ||
| Representation of Integers | ||
| Algorithms for Integer Operations | ||
| Primes | ||
| Greatest Common Divisors | ||
| Linear Congruences | ||
| The Chinese Remainder Theorem | ||
| Computer Arithmetic with Large Integers | ||
| Unit 4: Mathematical Induction and Recursion (4 Hrs.) | ||
| Introduction to Mathematical Induction | Lecture/Lab | |
| 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 | ||
| Unit 5: Basics of Counting (4 Hrs.) | ||
| Sum Rule | Lecture/Lab | |
| 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 | ||
| Unit 6: Discrete Probability (4 Hrs.) | ||
| Introduction | Lecture/Lab | |
| Finite Probability | ||
| Probabilities of Complements and Unions of Events | ||
| Assigning Probabilities | ||
| Conditional Probability | ||
| Independence | ||
| Random Variable | ||
| The Birthday Problem | ||
| Expected Value | ||
| Unit 7: Advanced Counting Techniques (5 Hrs.) | ||
| Recurrence Relations | Lecture/Lab | |
| 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) | ||
| Unit 8: Relations (3 Hrs.) | ||
| Relation and its Properties | Lecture/Lab | |
| 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 | ||
| Unit 9: Graph Theory (8 Hrs.) | ||
| Graph Models | Lecture/Lab | |
| 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 | ||
| Unit 10: Trees (3 Hrs.) | ||
| Introduction to Trees | Lecture/Lab | |
| 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 |
Text Books
1. Kenneth H. Rosen (2019), Discrete Mathematics and Its Applications, Eighth Edition, McGraw Hill Education.
2. Susanna S. Epp (2020), Discrete Mathematics with Applications, Fifth Edition
Lab Works
The laboratory work includes writing programs for implementing the concepts of logic gates, boolean matrix operations, floor and ceiling value of given positive as well as negative real numbers, set theory, number theory and graph theory using a programming language like C.