Course Title: Discrete Structure
Course No: BIT152
Nature of Course: Theory + Lab
Semester: II
Course
Description
This course provides an introduction to discrete mathematics, covering fundamental topics such as logic, proofs, sets, relations, functions, counting, probability, and their applications in information technology.
Course
Objectives
The course aims to:
- Introduce foundational concepts of
discrete mathematics.
- Develop an understanding of graphs,
functions, relations, and number theory.
- Explore practical applications of
discrete mathematics in IT.
Detailed Syllabus
Unit
1: Logic and Proof Methods (6 Hrs.)
- Propositional Logic: Introduction,
propositions, logical operators, precedence rules, and translation of English
sentences into propositional logic.
- Propositional Equivalences: Logical
equivalences, truth tables, and symbolic derivations.
- Predicate Logic: Predicates,
quantifiers, variable binding, negation of quantified statements, nested
quantifiers, and translation of English sentences into logical
expressions.
- Rules of Inference: Inferences for
propositional and predicate logic, fallacies, and valid arguments.
- Proof Methods: Direct, indirect,
contradiction, vacuous, trivial, case-based, equivalence, existence,
uniqueness, and counterexamples.
- Common Proof Mistakes: Identifying
errors in logical proofs.
Unit
2: Induction and Recursion (5 Hrs.)
- Mathematical Induction: Proofs for
summation formulas, inequalities, and divisibility.
- Strong Induction and Well Ordering:
Examples and applications.
- Recursive Definitions: Functions,
sets, structures, and structural induction.
- Recursive Algorithms: Design and
correctness proofs.
Unit
3: Number Theory (6 Hrs.)
- Integers and Division: Division
algorithm, modular arithmetic, arithmetic modulo *m*.
- Primes and GCD: Prime factorization,
GCD, LCM, and their computations.
- Extended Euclidean Algorithm: GCD as
linear combinations.
- Integer Algorithms: Binary, octal,
and hexadecimal representations, arithmetic algorithms.
- Applications: Linear congruencies,
Chinese Remainder Theorem, and large integer computations.
- Matrices: Zero-one matrices and
Boolean matrix operations (join, meet, product, power).
Unit
4: Counting and Discrete Probability (9 Hrs.)
- Counting Techniques: Product, sum,
and subtraction rules; pigeonhole principle; permutations and combinations;
subsets; binomial coefficients; Pascal's triangle; and generalized counting
techniques.
- Discrete Probability: Complementary
and union probabilities, conditional probability, independence, random
variables, expected value, variance, and randomized algorithms.
- Advanced Counting: Recurrence
relations (homogeneous and non-homogeneous).
Unit
5: Trees and Graphs (11 Hrs.)
- Graphs:
- Types: Simple, multigraph, pseudograph, directed, mixed.
- Applications: Social networks, communication systems, transportation
networks, and software design.
- Terminologies: Subgraphs, complete graphs, cycles, bipartite graphs,
and graph isomorphism.
- Algorithms: Euler/Hamilton paths, shortest path (Dijkstra), and graph
coloring.
- Theories: Matching and traveling salesman problem.
- Trees:
- Basics: Rooted trees, binary search trees, decision trees, and prefix
codes.
- Traversals: Preorder, inorder, postorder.
- Spanning Trees: Minimum spanning trees using Kruskal’s algorithm.
Laboratory
Works
The lab sessions involve programming
for various algorithms and concepts covered in the syllabus, including:
- Logical operations.
- Set operations, relations, and
functions.
- Recursive algorithms.
- Number theory algorithms (primality
testing, operations on integers).
- Boolean matrix operations.
- Graph and tree algorithms.
Text
/ Reference Books
1. Kenneth H. Rosen, "Discrete
Mathematics and Its Applications", 7th Edition, McGraw Hill, 2012.
2. Bernard Kolman, Robert Busby, Sharon
C. Ross, "Discrete Mathematical Structures", 6th Edition, Pearson, 2015.
3. Joe L. Mott, Abraham Kandel,
Theodore P. Baker, "Discrete Mathematics for Computer Scientists and
Mathematicians", 2nd Edition, Prentice Hall, 2008.
This course equips students with the
theoretical and practical knowledge of discrete mathematics, enabling them to
apply these concepts in computer science and information technology fields.
