Discrete Structure

Course Title: Discrete Structure

Course No: BCA 151

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 is designed to build a strong foundation in discrete mathematics—the kind of math that powers the world of computer science. It sharpens logical thinking, introduces techniques for writing solid mathematical proofs, and strengthens problem-solving skills needed in programming, algorithm design, and system development. Students will dive into key topics like logic, sets, functions, relations, combinatorics, graphs, trees, and Boolean algebra, learning not just the theory but also how these concepts apply in real tech scenarios like databases, circuits, and code structure. Through hands-on practice with tools like Python, Jupyter Notebooks, NetworkX, and Graphviz, students will bring these abstract ideas to life by building models, writing logic-based programs, and exploring how mathematics directly supports computing.

Course Objectives

Upon completion of this course, the students will be able to: develop the ability to think logically and construct valid mathematical arguments; apply set theory concepts such as set operations, Venn diagrams, Cartesian products, and power sets to solve problems in databases, programming, and decision-making structures; analyze relations and functions using matrix and graph representations and understand applications in modeling data and structures; use combinatorial techniques to solve real-life counting and arrangement problems; explore graph and tree structures, implement traversal algorithms (DFS, BFS, etc.), and apply these concepts in computer science domains such as networking, compiler design, and operating systems.

Course Contents

1. Set Theory

6 hrs

1.1. Basic Concepts: Sets, elements, roster and set-builder notation, cardinality

1.2. Set Relationships

Subsets

Proper subsets

Universal set

Complement

Disjoint sets

1.3. Set Operations

Union

Intersection

Difference

Complement

Symmetric difference

1.4. Venn Diagrams: Visual representation of set relatîonships and operations.

1.5. Set Identities: Proof of identities using algebraic and Venu diagram methods.

1.6. Cartesian Products: Ordered pairs, cross product of two or more sets.

1.7. Power Sets: Definition and computation of power sets.

1.8. Applications: Use of sets in databases. computer programming, and decision structures.

2. Logic and Propositional Calculus

8 hrs

2.1. Propositions and Logical Operators: Definition of propositions, types (simple, compound), logical connectives: AND, OR, NOT, IMPLICATION, BICONDITIONAL.

2.2. Truth Tables: Constructing truth tables for expressions involving logical operators.

2.3. Tautologies, Contradictions, and Contingencies: Identifying always true/fa1se/logical expressions.

2.4. Logical Equivalence and Implications: Laws of logic (De Morgan's, distributive, associative, etc.), verifying equivalences.

2.5. Predicate Logic and Quantifiers: lntroduction to predicates, universal and existential quantifiers.

2.6. Rules of Inference: Modus ponens, modus Pollens, hypothetical syllogism, and others.

2.7. Proof Methods: Direct, indirect, contradiction, contrapositive, and proof by cases.

3. Relations and Functions

8 hrs

3.1. Relations: Definition, Binary Relation, Representation, Domain, Range, Universal Relation, Void Relation, Union, Intersection, and Complement Operations on Relations

3.2. Properties of Binary Relations in a Set : Reflexive, Symmetric, Transitive, Anti-symmetric Relations

3.3. Relation Matrix and Graph of a Relation; Partition and Covering of n Set, Equivalence Relation, Equivalence Classes, Compatibility Relation, Maximum Compatibility Block, Composite Relation, Converse of a Relation,

3.4. Transitive Closure of a Relation R in Set X, examples from real-world scenarios.

3.5. Representation of Relations: Using matrices and directed graphs (digraphs).

3.6. Equivalence and Partial Order Relations

Posets and Order Properties

Hasse Diagram and Bounds

Lattices

3.7. Functions

3.8. Types of Functions

3.9. Inverse and Composition

3.10. Applications

4. Mathematical Reasoning

6 hrs

4.1. Mathematical Reasoning

4.2. Mathematical Induction

4.3. Strong Induction

4.4. Recursive Definitions

4.5. Structural Induction

4.6. Applications

5. Combinatorics

5 hrs

5.1. Counting Principles

5.2. Permutations and Combinations

5.3. Pigeonhole Principle

5.4. Inclusion-Exclusion Principle

6. Graph Theory and Trees

12 hrs

6.6. Matrix Representation

6.7. Types of Graphs

6.8. Graph Traversal

6.9. Trees

6.10. Tree Representation

6.11. m-ary to Binary Tree Conversion

6.12. Binary Trees

6.13. Tree Traversals

6.14. Applications

7. Algebraic Structures

3 hrs

7.1. Binary Operations

7.2. Algebraic Systems

7.3. Group Theory Basics

7.4. Boolean Algebra

7.5. Logic Circuits

7.6. Applications

Laboratory Works

Practical sessions of 48 hours using Python, Jupyter Notebooks, NetworkX, and Graphviz...

1.Truth Tables
2.Set Operations
3.Relations
4.Functions
5.Recursion
6.Combinatorics
7.Graphs
8.Graph Traversal
9.Trees
10.Boolean Algebra
11.Mini Project

Text Books

1.Grimaldi - Discrete Mathematics
2.Kolman - Discrete Structures
3.Liu - Discrete Mathematics
4.Rosen - Discrete Mathematics
5.Stein & Drysdale - Discrete Mathematics

Reference Books

1.Cormen - Introduction to Algorithms
2.Hopcroft & Tarjan - Graph Algorithms
3.Knuth - Art of Computer Programming
4.Pippenger - Computation Theory

Notes:

Instructor should encourage the use of open-source tools like Python, Jupyter Notebooks, NetworkX, and Graphviz for practical sessions. Practical Report Contents: Theory, Source code, Output, Conclusion.

Discrete Structure

Discrete Structure

Select University

Select Program

TabFlux . Discrete Structure . TU . BCA-NEW