Descrete Mathematics

Course Outline

I. Introduction to Discrete Mathematics
A. Definitions, Scope and Importance of Discrete Mathematics
B. Introduction to Mathematical Logic
C. Propositions and Logical Operations
D. Truth Tables
E. Logical Equivalences and Quantifiers

II. Sets, Relations and Functions
A. Basics of Sets
    1. Definitions
    2. Operations on Sets
B. Relations
    1. Definition and Properties
    2. Representing Relations
    3. Closures
C. Functions
    1. Definition and Properties
    2. Injective, Surjective, and Bijective Functions
    3. Inverse and Compositions of Functions

III. Combinatorics
A. Counting Principles
    1. Fundamental Principles of Counting
    2. Permutations and Combinations
B. Binomial Coefficients
C. Inclusion-Exclusion Principle
D. Pigeonhole Principle
E. Recurrence Relations and Generating Functions

IV. Graph Theory
A. Basics of Graphs
    1. Definitions and Terminology
    2. Types of Graphs
B. Graph Representations (Adjacency Matrix, Incidence Matrix, etc.)
C. Graph Traversal Algorithms (DFS, BFS)
D. Graph Properties and Theorems (Euler, Hamiltonian, etc.)
E. Trees and Spanning Trees

V. Discrete Probability
A. Basic Concepts of Probability
B. Conditional Probability and Bayes’ Theorem
C. Random Variables and Expectation
D. Variance and Standard Deviation

VI. Formal Languages, Automata and Complexity
A. Introduction to Formal Languages
    1. Definitions and Examples
    2. Regular Languages
    3. Context-Free Languages
B. Automata Theory
    1. Finite Automata
    2. Pushdown Automata
    3. Turing Machines
C. Complexity Theory
    1. Time and Space Complexity
    2. P, NP, and NP-Completeness

VII. Boolean Algebra and Logic Gates
A. Basics of Boolean Algebra
    1. Definitions and Properties
    2. Basic Operations
    3. Boolean Functions
B. Logic Gates and Circuits
    1. Basic Gates (AND, OR, NOT, XOR, etc.)
    2. Universal Gates (NAND, NOR)
    3. Designing and Simplifying Circuits

VIII. Mathematical Reasoning and Proof Techniques
A. Proof Techniques
    1. Direct Proofs
    2. Indirect Proofs (Contradiction, Contrapositive)
    3. Mathematical Induction (Weak and Strong)
B. Proof of Correctness for Algorithms
C. Diagonalization and Pigeonhole Principle

IX. Number Theory and Cryptography
A. Basics of Number Theory
    1. Divisibility, Primes, and Greatest Common Divisors
    2. Euclidean Algorithm
    3. Modular Arithmetic
B. Introduction to Cryptography
    1. Classical Cryptosystems
    2. Public-Key Cryptography
    3. RSA Algorithm

​

Textbook: "Discrete Mathematics and Its Applications" by Kenneth H. Rosen.