BIT 2nd Semester
Discrete Structure Syllabus

Propositional Logic: Propositional Logic, Propositional Equivalences, Rule of inferences, Valid Arguments
Predicate Logics: Predicates and Quantifiers, Negation of Quantified Statements, Proof of quantified statements, Nested Quantifiers, Rules of Inferences, Translating English Sentence to predicate logic expressions.
Proof Methods: Basic Terminologies, Proof Methods (Direct Proof, Indirect Proof, Proof by Contradiction, Proof By Contraposition, Exhaustive Proofs and Proof by Cases), Mistakes in Proof

Sets: Sets and Subsets, Power Set, Cartesian Product, Set Operations, Venn Diagram, Inclusion-Exclusion Principle, Computer Representation of Sets.
Relations: Relations and their Properties, N-ary Relations with Applications, Representing Relations, Closure of Relations, Equivalence Relations, Partial Ordering
Functions: Basic Concept, Injective and Bijective Functions, Inverse and Composite Functions, Graph of Functions, Functions for Computer Science (Ceiling Function, Floor Function, Boolean Function, Exponential Function)

Induction: Mathematical Induction, Strong Induction and Well Ordering, Induction in General
Recursive Definitions and Structural Induction, Recursive Algorithms, Proving Correctness of Recursive Algorithms

Integers: Integers and Division, Primes and Greatest Common Divisor, Extended Euclidean Algorithm, Integers and Algorithms
Applications of Number Theory (Linear Congruences, Chinese Remainder Theorem, Computer Arithmetic with Large Integers)
Matrices: Zero-One Matrices, Boolean Matrix Operations

Counting: Basics of Counting, Pigeonhole Principle, Permutations and Combinations, Two Element Subsets, Counting Subsets of a Set, Binomial Coefficients, Generalized Permutations and Combinations, Generating Permutations and Combinations with examples.
Discrete Probability: Introduction to Discrete Probability, Probability Theory, Probability Calculation in Hashing, Expected Value and Variance, Randomized Algorithms
Advanced Counting: Recurrence Relations, Solving Recurrence Relations (Homogeneous and Non-Homogeneous equations)

Graphs: Graphs Basics, Graph Types, Graph Models, Graph Representation, Graph Isomorphism, Connectivity in Graphs, Euler and Hamiltonian Path and Circuits, Matching Theory, Shortest Path Algorithm (Dijkstra’s Algorithm), Travelling Salesman Problem, Graph Coloring
Trees: Introduction and Applications, Tree Traversals, Spanning Trees, Minimum Spanning Trees (Kruskal’s Algorithm)