Discrete Mathematics - MATH F213

Mathematic Core Course: Semester I 2024- 2025


Instructor: Dr. Yasmeen Akhtar

Audience: 2nd, 3rd, and 4th Year B.E. students at BITS Pilani K K Birla Goa Campus

Tutors: Vedant Kamath and Sidak Chhabra (Informal TA) 

Schedule: Monday, Wednesday, Friday 9:00-9:50 AM at A602 (Lecture)

                        Thursday 8:00-8:50 AM at C405 (Tutorial)

Course Handout: Available on Quanta.

Evaluation: Quizzes-30%, Midsemester Exam-30%, Comprehensive Exam-40%

There will be one evaluation each month: 

August- Quiz 1, September-Quiz 2, October-Midsem, November-Quiz 3, December-Comprehensive

Lecture:

02/08/24 -  Introduction and instructions related to the course, Propositional Logic, Operators, Tautology, Contradiction, Contingency, Logical Equivalences

05/08/24 -Satisfiability,  Normal Forms: DNF, CNF, PDNF, and PCNF. How can they be used to determine if it is a Tautology, Contradiction, or Contingency?

07/08/24 - More on PDNF and PCNF, Predicate Logic, Quantifiers: Universal, Existential, Uniqueness 

08/08/24 - Tutorial 

09/08/24 - Logical Equivalence involving quantifiers, Negating a quantifier, Argument: Valid, Fallacy, Rules of Inference

12/08/24 - Rules of Inference involving quantifiers, Introduction to Proof: Vacuous and Trivial proofs

14/08/24 - Direct Proof, Proof by Contraposition, Proof by Contradiction 

15/08/24 - Holiday

16/08/24 - Proof by Cases, Exhaustive Proof, Proof by Elimination of Cases

19/08/24 - Holiday

21/08/24 - Conditional Proof, Proof of Equivalence, Existence Proof: Constructive, Nonconstructive, Uniqueness Proof, Counter Example

22/08/24 - Tutorial 

23/08/24 - Mathematical Induction: Weak, Strong 

26/08/24 - Holiday

28/08/24 - Basic Principles of Counting: Sum Rule, Product Rule, Subtraction Rule, Division Rule

29/08/24 - Quiz 1 (DLT 5 and DLT 6)

30/08/24 - Permutation and Combination

02/09/24 - Binomial theorem, Pascal's Triangle, Combinatorial Proof of Identities, Pigeonhole Principle

04/09/24 - Applications of Pigeonhole Principle and Generalization, The Ramsey Number

05/09/24 - Tutorial 

06/09/24 - The Generalized Principle of  Inclusion-Exclusion

09/09/24 -Examples,  Derangement

11/09/24 - Permutations and Combinations with Repetition

12/09/24 - Tutorial

13/09/24 - Distribution of objects into boxes, Multinomial Theorem, Stirling Number of Second kind

16/09/24 - Holiday

18/09/24 -  Stirling Number of First kind (Stirling Cycle Number), Bell Numbers

19/09/24 - Tutorial

20/09/24 - Catalan Numbers

23/09/24 - Recurrence Relation 

25/09/24 - Solving Linear Homogeneous Recurrence Relation with Constant Coefficient of Degree Two

26/09/24 - Tutorial

27/09/24 - Quiz 2 (LT 4)

30/09/24 - Method of Characteristic Roots

02/10/24 - Holiday

09/10/24 - Midsem Exam

10/10/24 - Tutorial

11/10/24 - Solving Linear Nonhomogeneous Recurrence Relation with Constant Coefficients

14/10/24 - Method of Differences, Solving Nonlinear Recurrence Relation

16/10/24 - Divide-and-conquer Algorithm,  its complexity using the divide-and-conquer recurrence relation

17/10/24 - Tutorial 

18/10/24 - Generating Functions and solving counting problems using generating functions

21/10/24 - Solving Recurrence Relation using Generating Functions

23/10/24 - Introduction to Relations and Digraphs

24/10/24 - Tutorial, Directed path, cycle, complete graph, graph isomorphism, etc.   

25/10/24 - Properties of Relations and counting the relations

31/10/24 - Holiday

01/11/24 - Holiday

04/11/24 - Counting the transitive relations, Operations on relations, and combining the relations

06/11/24 - Closure of relations, Connectivity relation

07/11/24 - Tutorial, Computing the Transitive closure, Warshall's algorithm, Equivalence relation  

08/11/24 - Waves

11/11/24 - Non-Instructional Day by the Institute

13/11/24 - Partial Ordering, Hasse Diagram, Properties of elements  in a post, Chain, Antichain, Total Ordering, Application:  Topological Sorting 

14/11/24 - Tutorial 

15/11/24 - Lattice, Sublattice, Bounded Lattice, Complemented Lattice, Complete Lattice

18/11/24 - Modular Lattice, Distributive lattice and its characterization

20/11/24 - Dual Lattice, Enumeration, Boolean algebra

21/11/24 - Tutorial 

22/11/24 - Quiz 3 (LT 4)

25/11/24 -  Functionally complete set of operators, NAND, NOR, XOR Gates 

27/11/24 - Applications: Combinatorial Circuit, Minimization of Circuits

28/11/24 - Tutorial 

08/12/24 - Comprehensive Exam