BIT · Semester II
Discrete Structure syllabus
Official TU syllabus for Discrete Structure (BIT152): 10 units, 80 topics. Every unit links to its notes and solved questions.
1
Fundamentals of Logic and Propositions
6 Q- Propositions and non-propositions
- Logical connectives and truth tables
- Tautology and contradiction
- Converse, inverse, and contrapositive
- Logical equivalence
- Quantifiers and predicate logic
- Negation of statements
2
Proof Techniques
14 Q- Direct proof
- Indirect proof
- Proof by contradiction
- Mathematical induction
- Structural induction
- Rules of inference
- Proving correctness of recursive algorithms
3
Set Theory and Relations
10 Q- Set representation and operations
- Bit strings for set operations
- Power set
- Cartesian product
- Venn diagrams
- Relations and their representations
- Relation matrices
- Directed graphs for relations
- Equivalence relations
- Partial ordering
4
Functions and Mappings
7 Q- Function definition and notation
- One-to-one and onto functions
- Identity function
- One-to-one correspondence
- Boolean functions
- Exponential functions
- Ceiling and floor functions
- Function plotting
5
Recurrence Relations and Recursion
6 Q- Recursively defined functions
- Linear homogeneous recurrence relations
- Linear nonhomogeneous recurrence relations
- Solving recurrence relations with initial conditions
- Characteristic equations
- Fibonacci sequence
6
Number Theory and Modular Arithmetic
9 Q- Divisibility and division algorithm
- Greatest common divisor
- Euclidean algorithm
- Extended Euclidean algorithm
- Congruence modulo
- Arithmetic modulo m
- Multiplicative inverse
- Chinese Remainder Theorem
- Prime numbers and trial division
7
Combinatorics and Counting
8 Q- Product rule
- Permutations
- Combinations
- Lexicographic ordering
- Pigeonhole principle
- Generalized pigeonhole principle
- Inclusion and exclusion principle
- Binomial coefficients
8
Graph Theory Fundamentals
8 Q- Graph definition and types
- Simple graphs and pseudographs
- Graph representation using adjacency matrix
- Graph representation using incidence matrix
- Directed graphs
- Graph isomorphism
- Connectivity in graphs
- Bipartite graphs
- Planar graphs
9
Trees and Graph Algorithms
14 Q- Tree definition and properties
- Spanning trees
- Minimum spanning trees
- Kruskal's algorithm
- Tree traversal methods
- Pre-order traversal
- In-order traversal
- Post-order traversal
- Euler paths and circuits
- Hamilton paths and circuits
- Cut vertices and cut edges
- Dijkstra's algorithm for shortest paths
10
Advanced Topics
2 Q- Boolean matrices and operations
- Randomized algorithms
- Computer arithmetic with large integers
- Modular arithmetic applications
Study BIT152 the smart way
Solved questions, flashcards & practice