Discrete Mathematics - MATH F213

Elective Course: Semester II 2022- 2023

Instructor: Dr. Yasmeen Akhtar

Audience: 2nd- and 3rd-year B.E. students at BITS Pilani K K Birla Goa Campus

Tutors: Jaskaran Singh Chhabra, Aneesha Jain

Schedule: Monday, Wednesday, and Thursday 03-03:50 PM at C405

Course Handout: Here.

Lecture:

18/01/23 - Introduction and instructions related to the course, application of discrete mathematics

19/01/23 - Propositional Logic, Operators, Tautology, Contradiction, Contingency, Logical equivalences

23/01/23 - Laws of logic, Logical Dual, Satisfiability

25/01/23 - Norma Forms: DNF, PDNF, CNF, PCNF, How to use them to determine if it is a Tautology, or Contradiction, or Contingency?

30/01/23 - Predicate Logic, Quantifiers: Universal, Existential, Uniqueness 

01/02/23 - Argument: Valid, Fallacy, Rules of Inference

02/02/23 - Introduction to Proof, Vacuous, Trivial, Direct proof, example

06/02/23 - Indirect Proof: Contraposition, Contradiction, Proof by Cases, Proof of Existence and uniqueness, example

08/02/23 - Proof of Equivalence, Examples, forward and backward reasoning, Counterexample, Mathematical Induction

09/02/23 - Examples, Strong Mathematical Induction 

13/02/23 - Addition, Multiplication, Subtraction, and Division Rules for Counting, Generalized Principle of  Inclusion-Exclusion

15/02/23 - Pigeonhole Principle, Generalization, and Application

16/02/23 - Ramsey Number R(3,3), Permutation and Combination, Binomial Theorem

20/02/23 - Pascal's Identity, Vandermonde's Identity, Examples

22/02/23 - Quiz 1

23/02/23 - Permutations and Combinations with Repetition, The signless Stirling Number of first kind, Stirling Number of second kind 

27/02/23 - How to compute Stirling Numbers,  Stirling Number of second kind and it's connection with Number of onto functions, Bell Numbers

01/03/23 - Multinomial Theorem, Permutations with Constrained Repetition, Distribution of Objects into Boxes (4 cases)

02/03/23 - Derangement, Catalan Numbers (Recurrence Formula)

06/03/23 - Catalan Numbers (Explicit formula), Recurrence relation Examples

09/03/23 -Generating function and its application in solving counting problems and recurrence relation

18/03/23 - Midsemester Exam

20/03/23 - Solving Linear Homogeneous Recurrence Relation with Constant Coefficients

22/03/23 - Solving Linear Nonhomogeneous Recurrence Relation with Constant Coefficients

23/03/23 - Midsem solution discussion and answer sheet distribution

27/03/23 - Non-Instructional Day

29/03/23 - Quiz 2

30/03/23 - Extra Class: Relations, Properties, Counting the number of relations with certain properties, Representing the binary  relation, Equivalence relation

03/04/23 - Examples, Equivalence class, Counting the number of Equivalence relations, Union & Intersection of binary relations

06/04/23 - Operations on binary relations, Examples

10/04/23 - Closure of a relation, Examples

12/04/23 - How to find the transitive closure of a relation?, Partial Ordering, Total Ordering, Hasse Diagram 

13/04/23 - Chain and Antichain in a Poset, Special elements in a Poset, Lattice

17/04/23 - Complete lattice, Sub-lattice, Dual lattice

19/04/23 - Bounded Lattice, Distributive lattice and its characterization

20/04/23 - Complemented lattice, Topological Sorting

                       26/04/23 - Boolean Algebra

27/04/23 - Quiz 3

01/05/23 - Boolean functions and how to simplify them?

03/05/23 - Combinatorial Circuit, Applications

04/05/23 - Functionally complete set of operators, NAND, NOR, XOR Gates 

19/05/23 - Comprehensive Exam