BSc CSIT · Semester II
Discrete Structures syllabus
Official TU syllabus for Discrete Structures (CSC165): 6 units, 96 topics, 3 credit hours. Every unit links to its notes and solved questions.
1
Basic Discrete Structures
7h · 9 Q- Sets
- Sets and Subsets
- Power Set
- Cartesian Product
- Set Operations
- Venn Diagram
- Inclusion-Exclusion Principle
- Computer Representation of Sets
- 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)
- Fuzzy Sets and Membership Functions
- Fuzzy Set Operations
- Sequences and Summations
- Basic Concept of Sequences
- Geometric and Arithmetic Progression
- Single and Double Summation
2
Integers and Matrices
6h · 11 Q- Integers
- Integers and Division
- Primes and Greatest Common Divisor
- Extended Euclidean Algorithm
- Integers and Algorithms
- Applications of Number Theory (Linear Congruencies, Chinese Remainder Theorem, Computer Arithmetic with Large Integers)
- Matrices
- Zero-One Matrices
- Boolean Matrix Operations
3
Logic and Proof Methods
6h · 14 Q- Logic
- Propositional Logic
- Propositional Equivalences
- Predicates and Quantifiers
- Negation of Quantified Statements
- Proof of quantified statements
- Nested Quantifiers
- Rules of Inferences
- 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
4
Induction and Recursion
5h · 9 Q- Induction
- mathematical Induction
- Strong Induction and Well Ordering
- Induction in General
- Recursive Definitions and Structural Induction
- Recursive Algorithms
- Proving Correctness of Recursive Algorithms
5
Counting and Discrete Probability
9h · 14 Q- 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
- 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)
- Introduction to Divide and Conquer Recurrence Relations
6
Relations and Graphs
12h · 25 Q- Relations
- Relations and their Properties
- N-ary Relations with Applications
- Representing Relations
- Closure of Relations
- Equivalence Relations
- Partial Ordering
- 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)
- Network Flows
- Graph as Models of Flow of Comodities
- Flows
- Maximal Flows and Minimal Cuts
- The Max Flow-Min Cut Theorem
Textbooks and references
- Kenneth H. Rosen, Discrete mathematics and its applications, Seventh Edition McGraw Hill Publication, 2012.
- Bernard Kolman, Robert Busby, Sharon C. Ross, Discrete Mathematical Structures, Sixth Edition Pearson Publications, 2015
- Joe L Mott, Abraham Kandel, Theodore P Baker, Discrete Mathematics for Computer Scientists and Mathematicians, Printice Hall of India, Second Edition, 2008
- Ken Bogart, Scot Drysdale, Cliff Stein, Discrete Mathematics for Computer Scientists, First Edition Addison-Wesley, 2010
Study CSC165 the smart way
Solved questions, flashcards & practice