Discrete Structure

Course Title: Discrete Structure

Course No: BIT123

Nature of the Course: Theory + Lab

Semester: 2

Full Marks: 60 + 20 + 20

Pass Marks: 24 + 8 + 8

Credit Hours: 3

Course Description

This course introduces the mathematical foundations required in information technology. The topics include logic, set theory, relations, functions, combinatorics, graph theory, and discrete probability, with an emphasis on applications in information technology.

Course Objectives

The main objective of the course is to: Introduce basic concepts of discrete mathematics; Use set and relations; Implement functions; Understand induction and recursion; Get familiar with combinations and permutations; Acquaint with graph and tree; Understand number theory and modular arithmetic; Explore applications of discrete mathematics in information technology.

Course Contents

1. Mathematical Logic and Proof Methods

8 hrs

1.1. Introduction

Mathematical logic

Statements and Notations

Connectives

Well-formed Formulas

Truth Tables

1.2. Propositional Logic

Propositional Logic

Propositional Equivalences

Rule of Inferences

Well-formed Formula

Valid Arguments

1.3. Predicate Logics

Predicates and Quantifiers

Negation of Quantified Statements

Proof of quantified statements

Nested Quantifiers

Rules of Inference: Propositional Logic and Quantified Statements

Translating English Sentence to predicate logic expressions

1.4. Proof Methods

Basic Terminologies

Proof Methods: Direct Proof, Indirect Proof, Proof by Contradiction, Proof by Contraposition

Exhaustive Proofs and Proof by Cases

Common Errors in Proofs

2. Sets, Relations and Functions

9 hrs

2.1. Set Theory

Sets and Subsets

Power Sets

Set Operations: Union, Intersection, Difference, Complement

Venn Diagrams

Inclusion-Exclusion Principle

Cartesian Product

Representation of Sets in Computer

2.2. Relations

Relations and their Properties

N-ary Relations with Applications

Representing Relations

Closure of Relations

Equivalence Relations

Partial Orderings

2.3. Functions

Introduction

Injective and Bijective Functions

Inverse and Composite Functions

Graph of Functions

Functions for Information Technology: Ceiling Function, Floor Function, Boolean Function, and Exponential Function

3. Induction and Recursion

8 hrs

3.1. Mathematical Induction

3.2. Strong Induction

3.3. Structural Induction

3.4. Recurrence Relation

3.5. Recursive Algorithms

3.6. Growth of Functions

3.7. Solving Homogeneous and Non-homogeneous Recurrences

4. Elementary Combinatorics

7 hrs

4.1. Basis of Counting: Product Rule and Sum Rule

4.2. Combinations & Permutations, with repetitions

4.3. Constrained Repetitions

4.4. Binomial Coefficients

4.5. Binomial Multinomial Theorems

4.6. Principle of Inclusion – Exclusion

4.7. Pigeonhole Principle and Its Application

5. Graphs and Trees

9 hrs

5.1. Graphs

Definitions and Terminology

Types of Graphs: Simple, Directed, Undirected, Weighted

Handshaking Theorem

Graph Representations: Adjacency List, Adjacency Matrix

Graph Traversal Algorithms: DFS, BFS

Isomorphism

Euler and Hamiltonian Path and Circuits

Planar Graphs and Graph Coloring

5.2. Tree

Introduction

Tree Traversals

Spanning Trees

Minimum Spanning Trees: Kruskal's Algorithm, Prim's Algorithm

6. Number Theory, Modular Arithmetic, and Discrete Probability

4 hrs

6.1. Modular Arithmetic

6.2. Primes

6.3. Greatest Common Divisor and Least Common Multiples

6.4. Euclidean Algorithm

6.5. Congruences

6.6. Chinese Remainder Theorem

6.7. Fermat's Little Theorem

6.8. Discrete Probability

6.9. Probability Theory

Laboratory Works

The lab work involves applying the algorithms and concepts covered in above units. Students are expected to solve problems using the following concepts.

1.Set operations, relations, and functions
2.Number theory algorithms
3.Counting techniques and recursive algorithms
4.Predicate logic
5.Algorithms for trees and graphs

Text Books

1.Rosen, Kenneth H., Discrete Mathematics & Applications, McGraw-Hill
2.Graham, Ronald, Donald Knuth, and Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley Publishing Company
3.Graham, Knuth, and Patashnik, Concrete Mathematics: A Foundation for Computer Science
4.Kolman, Bernard, Robert C. Busby, and Sharon Ross., Discrete Mathematical Structures, Prentice-Hall, Inc., 2014
5.E.G. Goodaire & M M Parmenter, Discrete Mathematics with Graph Theory, 2nd Ed, Pearson

Notes:

university_short_name left empty: not stated on source document. marking_scheme component/mark_type labeling (THEORY FINAL 60/24, THEORY INTERNAL 20/8, PRACTICAL FINAL 20/8) is a standard-pattern best fit since the source only lists combined totals '60+20+20' and '24+8+8' without labeling each component. Text/Reference Books were listed as a single undifferentiated list in the source and have all been placed under text_books.

Discrete Structure

Discrete Structure

Select University

Select Program

TabFlux . Discrete Structure . FWU . BIT