Discrete Structures
0%
Course Title: Discrete Structures
Course No: CSC165
Nature of the Course: Theory + Lab
Semester: 2
Full Marks: 60 + 20 + 20
Pass Marks: 24 + 8 + 8
Credit Hours: 3
Course Description
Course Objectives
Course Contents
1.1. Sets
- Sets and Subsets
- Power Set
- Cartesian Product
- Set Operations
- Venn Diagram
- Inclusion-Exclusion Principle
- Computer Representation of Sets
1.2. 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
1.3. Sequences and Summations
- Basic Concept of Sequences
- Geometric and Arithmetic Progression
- Single and Double Summation
2.1. 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)
2.2. Matrices
- Zero-One Matrices
- Boolean Matrix Operations
3.1. Logic
- Propositional Logic
- Propositional Equivalences
- Predicates and Quantifiers
- Negation of Quantified Statements
- Proof of quantified statements
- Nested Quantifiers
- Rules of Inferences
3.2. Proof Methods
- Basic Terminologies
- Direct Proof
- Indirect Proof
- Proof by Contradiction
- Proof By Contraposition
- Exhaustive Proofs and Proof by Cases
- Mistakes in Proof
4.1. Induction
- Mathematical Induction
- Strong Induction and Well Ordering
- Induction in General
4.2. Recursion
- Recursive Definitions and Structural Induction
- Recursive Algorithms
- Proving Correctness of Recursive Algorithms
5.1. 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
5.2. Discrete Probability
- Introduction to Discrete Probability
- Probability Theory
- Probability Calculation in Hashing
- Expected Value and Variance
- Randomized Algorithms
5.3. Advanced Counting
- Recurrence Relations
- Solving Recurrence Relations (Homogeneous and Non-Homogeneous equations)
- Introduction to Divide and Conquer Recurrence Relations
6. Relations and Graphs
12 hrs
6.1. Relations
- Relations and their Properties
- N-ary Relations with Applications
- Representing Relations
- Closure of Relations
- Equivalence Relations
- Partial Ordering
6.2. 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
6.3. Trees
- Introduction and Applications
- Tree Traversals
- Spanning Trees
- Minimum Spanning Trees (Kruskal's Algorithm)
6.4. Network Flows
- Graph as Models of Flow of Commodities
- Flows
- Maximal Flows and Minimal Cuts
- The Max Flow-Min Cut Theorem
Laboratory Works
- 1.Set Operations and Boolean Matrix Operations
- 2.Primality Testing, Number Theory Algorithms, and Operations on Integers
- 3.Counting and Some Recursive Algorithms
- 4.Algorithms for Relations, Graphs
Text Books
- 1.Kenneth H. Rosen, Discrete mathematics and its applications, Seventh Edition McGraw Hill Publication, 2012
- 2.Bernard Kolman, Robert Busby, Sharon C. Ross, Discrete Mathematical Structures, Sixth Edition Pearson Publications, 2015
- 3.Joe L Mott, Abraham Kandel, Theodore P Baker, Discrete Mathematics for Computer Scientists and Mathematicians, Prentice Hall of India, Second Edition, 2008
Reference Books
- 1.Ken Bogart, Scot Drysdale, Cliff Stein, Discrete Mathematics for Computer Scientists, First Edition Addison-Wesley, 2010