Discrete Structure(DS) Syllabus

Course Description: The course introduces the basic concepts of discrete mathematics such as

introductory logic, proofs, sets, relations, functions, counting and probability, with an emphasis on

applications in information technology.

Course Objectives: The main objective of the course is to introduce basic concepts of discrete

mathematics, understand the concepts of graphs, functions, relations and number theory

respectively and explore applications of discrete mathematics in information technology.

1. Logic and Proof Methods

teaching hours: 6 hrs

Propositional Logic (Introduction, Propositions, Logical Connectives/Operators, Precedence of Logical Operators, Translating English Sentences to Propositional Logic)

Propositional Equivalences (Introduction, Logical Equivalences, Proving Logical Equivalences using Truth Table and Symbolic Derivation)

Predicate Logics (Introduction, Predicates and Quantifiers, Precedence of Quantifiers, Binding Variables, Negation of Quantified Statements, Translating English Sentence to Logical Expressions, Nested Quantifiers)

Rules of Inferences (Introduction, Rules of Inference for Propositional Logic, Fallacies, Valid Arguments for Propositional Logic, Rules of Inference for Quantified Statements)

Proof Methods (Introduction and Terminologies, Direct Proof, Indirect Proof, Vacuous and Trivial Proof, Proof by Contradiction, Exhaustive and Proof by Cases, Proof of Equivalence, Existence and Uniqueness Proofs, Proofs by Counter Example), Mistakes in Proofs

2. Sets, Relations and Functions

teaching hours: 7 hrs

Sets (Definition, Notation; Some Important Sets; Equal Sets; Empty Set; Venn Diagram; Subsets; Size of a Set; Power Sets; Cartesian Product; Set Operations – Union, Intersection, Difference and Complement; Computer Representation of Sets – Complement, Union and Intersection)

Functions (Definition and Terminologies; Equal Functions; Real Valued and Integer Valued Functions; Image of Subset of Domain; One-to-One, Onto, and One-to-One Correspondence; Inverse and Composite Functions; Graph of Functions; Ceiling Function, Floor Function, Boolean Function and Exponential Function)

Relations (Introduction; Functions as Relations; Relation on a Set; Properties of Relations – Reflexive, Symmetric, Antisymmetric, and Transitive; Combining Relations; n-Ary Relations and Applications – Database and Relations, Operations; Representing Relations using Matrices and Diagraphs; Closure of Relations – Reflexive, Symmetric and Transitive; Equivalence Relations and Classes; Partial Orderings)

3. Induction and Recursion

teaching hours: 5 hrs

Mathematical Induction (Introduction; Proofs by Mathematical Induction; Examples – Proving Summation Formula, Proving Inequalities and Proving Divisibility Results)

Strong Induction and Well Ordering (Introduction and Examples of Strong Induction; Proofs using Well Ordering Property)

Recursive Definitions and Structural Induction (Introduction; Recursively Defined Functions, Sets and Structures; Structural Induction)

Recursive Algorithms and Proving Correctness of Recursive Algorithms

4. Number Theory

teaching hours: 6 hrs

Integers and Division (Division Algorithm; Modular Arithmetic; Arithmetic Modulo m) Primes and Greatest Common Division (Primes; Trial Division; Prime Factorization; GCD and LCM; Relatively Prime, Pairwise Relatively Prime; Using Prime Factorization to find GCD and LCM)

Extended Euclidian Algorithm (Euclidian Algorithm; GCDs as Linear Combinations; Extended Euclidian Algorithm)

Integers and Algorithms (Integer Representations – Binary, Octal, Hexadecimal, and Conversions; Addition, Multiplication, Division, Modulus Algorithms)

Applications of Number Theory (Linear Congruencies, Chinese Remainder Theorem, Computer Arithmetic with Large Integers)

Matrices (Zero-One Matrices, Boolean Matrix Operations – Join, Meet, Product, and Power); Prime Number and its applications

5. Counting and Discrete Probability

teaching hours: 9 hrs

Counting (Basics of Counting – Product Rule, Sum Rule and Subtraction Rule; Pigeonhole Principle and Generalized Pigeonhole Principle; Permutations and Combinations; Two Element Subsets and Counting Subsets of a Set; Binomial Coefficients and Identity; Pascal’s Identity and Triangle; Generalized Permutations and Combinations – Permutation and Combinations with Repetition, Permutations with Indistinguishable Objects; Generating Permutations and Combinations with Examples)

Discrete Probability (Finite Probability; Probabilities of Complements and Unions; Probability Theory – Assigning Probability, Conditional Probability, Independence, Random Variables, Expected Value and Variance, Randomized Algorithms, Probability Calculation in Hashing)

Advanced Counting (Recurrence Relations; Solving Recurrence Relations - Homogeneous and Non-Homogeneous equations, Theorems without Proof)