📐 Discrete Structure BCA 151 | Semester II
📖 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.
🎯 Course Objectives
- Develop the ability to think logically and construct valid mathematical arguments
- Apply set theory concepts to solve problems in databases, programming, and decision structures
- Analyze relations and functions using matrix and graph representations
- Use combinatorial techniques to solve real-life counting and arrangement problems
- Explore graph and tree structures, implement traversal algorithms (DFS, BFS), and apply in networking, compiler design, and OS
📚 Detailed Syllabus
Unit 1: Set Theory
6 hrs
- Basic Concepts: Sets, elements, roster and set-builder notation, cardinality
- Set Relationships: Subsets, proper subsets, universal set, complement, disjoint sets
- Set Operations: Union, intersection, difference, complement, symmetric difference
- Venn Diagrams: Visual representation of set relationships and operations
- Set Identities: Proof using algebraic and Venn diagram methods
- Cartesian Products: Ordered pairs, cross product of two or more sets
- Power Sets: Definition and computation of power sets
- Applications: Use of sets in databases, computer programming, and decision structures
Unit 2: Logic and Propositional Calculus
8 hrs
- Propositions and Logical Operators: Simple, compound, connectives (AND, OR, NOT, IMPLICATION, BICONDITIONAL)
- Truth Tables: Constructing truth tables for logical expressions
- Tautologies, Contradictions, and Contingencies
- Logical Equivalence and Implications: De Morgan’s, distributive, associative laws
- Predicate Logic and Quantifiers: Universal and existential quantifiers
- Rules of Inference: Modus ponens, modus tollens, hypothetical syllogism
- Proof Methods: Direct, indirect, contradiction, contrapositive, proof by cases
Unit 3: Relations and Functions
8 hrs
- Relations: Definition, binary relation, representation, domain, range, operations on relations
- Properties: Reflexive, symmetric, transitive, anti-symmetric
- Relation Matrix and Digraph, Equivalence Relation & Classes, Compatibility Relation
- Transitive Closure, Composite Relation, Converse
- Partial Order Relations: Hesse diagrams, least/greatest members, minimal/maximal, LUB/GLB, posets, lattices (complete, distributive, modular, complemented, Boolean lattices)
- Functions: Definition, domain, co-domain, range
- Types: Injective, surjective, bijective; Inverse and composition of functions
- Applications: Programming, data mapping, relational databases
Unit 4: Mathematical Reasoning and Proof Techniques
6 hrs
- Mathematical Reasoning: Basic structure of arguments, logical flow
- Mathematical Induction: Principle of induction, proof by induction, applications in series and recursive definitions
- Strong Induction: Differences from regular induction, applications
- Recursive Definitions: Defining sequences and structures recursively
- Structural Induction: Proofs involving recursively defined structures like trees and lists
- Applications: Problem-solving and validation of algorithms
Unit 5: Combinatorics and Counting Principles
5 hrs
- Basic Counting Principles: Rule of sum and rule of product, real-world examples
- Permutations and Combinations: Ordered/unordered selections, nPr, nCr, factorial notation — applications in password generation, team selection
- Pigeonhole Principle: Simple and strong pigeonhole principle, birthday paradox, drawer problems
- Inclusion-Exclusion Principle: Set-based approach, solving problems with unions of up to three sets, applications in probability and combinatorics
Unit 6: Graph Theory and Trees
12 hrs
- Graphs: Definition, nodes, edges, directed/undirected, multigraph, weighted, degree, indegree, outdegree
- Subgraphs, Converse digraph, Path, Cycle, Reachability, Distance
- Connectedness: Weakly, strongly, unilaterally connected; components, deadlock detection
- Matrix Representation: Adjacency matrix, path matrix, Warshall’s algorithm
- Types of Graphs: Complete, bipartite, simple, multigraph
- Graph Traversal: Breadth-First Search (BFS), Depth-First Search (DFS)
- Trees: Definition, root, leaf, branch nodes; binary tree, m-ary tree, full binary tree
- Tree Representations: Linked-list, converting m-ary tree to binary tree
- Tree Traversals: Inorder, preorder, postorder
- Applications: Networking, pathfinding, compiler syntax trees, file systems
Unit 7: Algebraic Structures
3 hrs
- Binary Operations: Definition and examples on sets
- Algebraic Systems: Semigroups, monoids, groups — axioms and properties
- Group Theory Basics: Identity, inverse, associativity, examples (integers, matrices)
- Boolean Algebra: Basic postulates and theorems, duality, Boolean functions
- Logic Circuits: Simplification using Boolean expressions
- Applications: Automata theory, logic design, cryptography
🔬 Laboratory Work (48 Hours)
Tools: Python, Jupyter Notebooks, NetworkX, Graphviz
Truth tables, logical operators, tautologies using Python
Set operations and Venn diagram visualization
Relation properties: matrix/digraph representation in code
Function definitions and mapping types
Recursion-based programs (factorial, Fibonacci) validating induction
Permutations and combinations via iteration/recursion
Graph representation: adjacency list/matrix (NetworkX)
Graph traversal: DFS and BFS implementations
Tree structures and traversals (inorder, preorder, postorder)
Boolean algebra simplification and expression evaluation
Mini project: Logical puzzle solver or graph simulation
📌 Practical Report Contents: Theory, Source code, Output, Conclusion
📚 Required Readings & References
- Grimaldi, R. P. – Discrete and Combinatorial Mathematics: An Applied Introduction, Pearson
- Kolman, B., Busby, R. C., & Ross, S. – Discrete Mathematical Structures (3rd ed.), Prentice Hall
- Liu, C. L. – Elements of Discrete Mathematics (2nd ed.), McGraw-Hill
- Rosen, K. H. – Discrete Mathematics and Its Applications (8th ed.), McGraw-Hill
- Stein, C., & Drysdale, R. L. – Discrete Mathematics for Computer Scientists, Pearson
- Cormen, T. H. et al. – Introduction to Algorithms (3rd ed.), MIT Press
- Knuth, D. E. – The Art of Computer Programming: Vol 1, Addison-Wesley
Note: This syllabus follows the TU BCA Second Semester curriculum 2025. Emphasis on hands-on implementation using open-source tools to bridge theory with computational thinking.