Discrete Mathematical Structures

Unit 1 : Sets, Functions, Sequences and Summations and Relations

• What are Set Operations
• Computer Representation of Sets
• Countable and Uncountable Sets
• Principle of Inclusion and Exclusion
• Multisets
• Functions: One-to-one and Onto Functions
• Inverse Functions and Compositions of Function
• Graphs of Functions
• Sequences and Summations: Sequences
• Special Integer Sequences
• Summations; Relations: Properties of Binary Relations
• Equivalence relations and Partitions
• Partial Ordering Relations and Lattices

Unit 2 : Logic and Proofs

• Propositional Logic
• Propositional Equivalences
• Use of first-order logic to express natural language predicates
• Quantifiers
• Nested Quantifiers
• Rules of Inference
• Introduction to Proofs
• Proof Methods and Strategies
• Mathematical Induction

Unit 3 : Number Theory

• Division and Integers
• Primes and Greatest Common Divisors
• Representation of Integers
• Algorithms for Integer Operations
• Modular Exponentiation
• Application of number theory

Unit 4: Combinatorics/Counting

• The Pigeonhole Principle
• Permutations and Combinations
• Binomial Coefficients
• Generalized Permutations and Combinations
• Generating Permutations and Combinations

Unit 5: Graph and Tree

• Basic Terminology of Graphs
• Multigraphs and Weighted Graphs
• Paths and Circuits of Graphs
• Eulerian Paths and Circuits of Graphs
• Hamiltonian Paths and Circuits of Graphs
• Shortest Paths of Graphs
• Spanning Trees
• Graph Isomorphism
• Planar Graphs
• Introduction to Trees
• Rooted Trees
• Path Lengths in Rooted Trees.

Unit 6: Recurrence

• Recurrence Relations
• Generating Functions
• Linear Recurrence Relations with Constant Coefficients and their solution