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