Discrete Structure
0%
Course Title: Discrete Structure
Course No: BIT152
Nature of the Course: Theory + Lab
Semester: 2
Full Marks: 60 + 20 + 20
Pass Marks: 24 + 8 + 8
Credit Hours: 3
Course Description
Course Objectives
Course Contents
1.1. Propositional Logic
- Propositional Logic
- Propositional Equivalences
- Rule of inferences
- Valid Arguments
1.2. Predicate Logics
- Predicates and Quantifiers
- Negation of Quantified Statements
- Proof of quantified statements
- Nested Quantifiers
- Rules of Inferences
- Translating English Sentence to predicate logic expressions
1.3. Proof Methods
- Basic Terminologies
- Direct Proof
- Indirect Proof
- Proof by Contradiction
- Proof By Contraposition
- Exhaustive Proofs and Proof by Cases
- Mistakes in Proof
2.1. Sets
- Sets and Subsets
- Power Set
- Cartesian Product
- Set Operations
- Venn Diagram
- Inclusion-Exclusion Principle
- Computer Representation of Sets
2.2. Relations
- Relations and their Properties
- N-ary Relations with Applications
- Representing Relations
- Closure of Relations
- Equivalence Relations
- Partial Ordering
2.3. Functions
- Basic Concept
- Injective and Bijective Functions
- Inverse and Composite Functions
- Graph of Functions
- Functions for Computer Science (Ceiling Function, Floor Function, Boolean Function, Exponential Function)
3.1. Induction
- Mathematical Induction
- Strong Induction and Well Ordering
- Induction in General
4. Number Theory
6 hrs
4.1. Integers
- Integers and Division
- Primes and Greatest Common Divisor
- Extended Euclidean Algorithm
- Integers and Algorithms
- Applications of Number Theory (Linear Congruencies, Chinese Remainder Theorem, Computer Arithmetic with Large Integers)
4.2. Matrices
- Zero-One Matrices
- Boolean Matrix Operations
- Prime Number and its applications
5.1. Counting
- Basics of Counting
- Pigeonhole Principle
- Permutations and Combinations
- Two Element Subsets
- Counting Subsets of a Set
- Binomial Coefficients
- Generalized Permutations and Combinations
- Generating Permutations and Combinations with examples
5.2. Discrete Probability
- Introduction to Discrete Probability
- Probability Theory
- Probability Calculation in Hashing
- Expected Value and Variance
- Randomized Algorithms
5.3. Advanced Counting
- Recurrence Relations
- Solving Recurrence Relations (Homogeneous and Non-Homogeneous equations)
6. Tree and Graphs
11 hrs
6.1. Graphs
- Graphs Basics
- Graph Types
- Graph Models
- Graph Representation
- Graph Isomorphism
- Connectivity in Graphs
- Euler and Hamiltonian Path and Circuits
- Matching Theory
- Shortest Path Algorithm (Dijkstra's Algorithm)
- Travelling Salesman Problem
- Graph Coloring
6.2. Trees
- Introduction and Applications
- Tree Traversals
- Spanning Trees
- Minimum Spanning Trees (Kruskal's Algorithm)
Laboratory Works
- 1.Set Operations, Relations and Functions
- 2.Primality Testing, Number Theory Algorithms, and Operations on Integers
- 3.Counting and Some Recursive Algorithms
- 4.Predicate Logic
- 5.Algorithms for Tree and Graphs
Text Books
- 1.Kenneth H. Rosen, Discrete mathematics and its applications, Seventh Edition McGraw Hill Publication, 2012.
- 2.Bernard Kolman, Robert Busby, Sharon C. Ross, Discrete Mathematical Structures, Sixth Edition Pearson Publications, 2015
- 3.Joe L Mott, Abraham Kandel, Theodore P Baker, Discrete Mathematics for Computer Scientists and Mathematicians, Printice Hall of India, Second Edition, 2008