Schedule

Instructors		Abhijit Das and Aritra Hazra
Timing		Allocated hours: Mon 12:00–12:55, Tue 10:00–11.55 †, Thu 08:00–08:55 [Slot D4] † (Doubt-clearance and tutorial sessions)
Venue		Online
Teaching Assistants		Anshul Goel, Anupam Modal, Bijoy Das, Debranjan Pal, Imandi Deepak, Sayani Sinha, Souvik Sur

Notices and Announcements

August 09, 2021, 1:00pm

We have frozen, in ERP, our decisions about the acceptance of non-CSE students. The accepted students may now proceed to register for the course. There are a few pending cases (because of ERP issues). All these students have been communicated personally by the teachers. No other/new requests will be entertained irrespective of CGPA.

August 08, 2021

Non-CSE students may apply for this course in ERP. We can accommodate a few non-CSE students. If the number of applicants is large, shortlisting will be done based on CGPA. We will wait until 12 noon of August 09, 2021 before finalizing our decisions. No further requests will be entertained after that (irrespective of CGPA).

August 08, 2021

The two theory teachers will handle mutually disjoint topics. The recorded videos will be posted, and the links will be supplied in this page. Meeting links will be sent to the students before the sessions.

Coverage

Basic Counting	Week 1 (Aug 12 – Aug 17)
	Sum and product rules. Permutations and combinations with and without repetition. Binomial and multinomial theorems. Catalan Numbers.	Part 1 | Part 2
	Query form
Propositional Logic First-Order Logic	Week 2 (Aug 18 – Aug 24)
	Encoding, reasoning and deductions, truth tables, satisfiability and validity. Predicates, quantifiers and interpretations, logical deduction, rules and proofs.	Single Part Part 1 | Part 2
	Query form
First-Order Logic Proof Techniques	Week 3 (Aug 25 – Aug 31)
	Applications in program verification. Direct proofs, proof by contradiction and contraposition, proof by cases, cycle of proofs. Mathematical induction.	Single Part Single part Part 1
	Query form
Proof Techniques	Week 4 (Sep 01 – Sep 07)
	Mathematical induction. Recursive constructions. Loop invariance.	Part 2 Single part Single part
	Query form
Proof Techniques	Week 5 (Sep 08 – Sep 14)
	Properties of Integers: Divisibility, primes, GCDs, factorizations.	Single part
	Query form
Proof Techniques Set Theory	Week 6 (Sep 15 – Sep 21)
	The pigeon-hole principle and its applications. Sets, subsets, and power sets, counting using sets, set operations, index sets and partitions. Relations: Definition and properties, equivalence relations and partitions.	Single part Single part Part 1
	Query form
Set Theory	Week 7 (Sep 22 – Sep 28)
	Relations: Partial orders, lattices. Functions: Definition and properties (injective, surjective, bijective), composite and inverse functions.	Part 2 Part 1 | Part 2
	Query form
Sizes of Sets	Week 8 (Sep 29 – Oct 05)
	Finite and infinite sets, countable sets. Uncountable sets, Cantor's diagonal argument, and the power-set theorem. Applications in Computer Science. Unsolvability of problems.	Single part Single part Single part
	Query form
Generating Functions	Week 9 (Oct 20 – Oct 26)
	Definition, examples, applications to counting and probability distributions. Applications to integer compositions and partitions. Exponential generating functions. Solving recurrence relations using generating functions, Catalan numbers (revisited).	Single part Single part Single part
	Query form
Recurrences	Week 10 (Oct 27 – Nov 02)
	Formulation and examples. Linear recurrences.	Part 1 | Part 2 | Part 3 | Part 4
	Query form
Recurrences Algebraic Structures	Week 11 (Nov 03 – Nov 09)
	Divide-and-conquer recurrences. The master theorem. Rings and fields: Definitions and properties, homomorphisms and isomorphisms, units, subrings.	Part 1 | Part 2 Single part
	Query form
Algebraic Structures	Week 12 (Nov 10 – Nov 16)
	Groups: Definitions and properties, homomorphisms and isomorphisms, cyclic groups, subgroups and cosets. Extra: Modular arithmetic, applications to cryptography.	Part 1 | Part 2 Single part
	Query form

Tutorials

1. Elementary counting techniques
2. Propositional and predicate logic
3. Proof techniques, mathematical induction
4. Recursive constructions, loop invariance, properties of integers
5. Pigeon-hole principle
6. Sets, functions, and relations
7. Sizes of sets
8. Generating functions
9. Recurrence relations
10. Rings and fields
11. A note on identities

Books and References

We will mostly follow this textbook. Supplementary materials will be provided on topics not covered by this book.

Ralph P Grimaldi, Discrete and Combinatorial Mathematics, 5th Edition, Pearson, 2004.

Some other references are listed below.

1. Michel O Albertson and Joan P Hutchinson, Discrete Mathematics with Algorithms, Wiley.
2. Norman L Biggs, Discrete Mathematics, Oxford University Press.
3. Winfried Karl Grassmann and Jean-Paul Tremblay, Logic and Discrete Mathematics, Pearson.
4. Richard Johnsonbaugh, Discrete Mathematics, 8th Edition, Pearson.
5. Bernard Kolman, Robert C Busby, and Sharon Cutler Ross, Discrete Mathematical Structures, 6th Edition, Pearson.
6. Thomas Koshy, Discrete Mathematics with Applications, Elsevier.
7. C L Liu, Elements of Discrete Mathematics, 4th Edition, Tata McGraw-Hill.
8. Kenneth H Rosen (Editor-in-chief), Handbook of Discrete and Combinatorial Mathematics, 2nd Edition, CRC Press.
9. Cliff L Stein, Robert Drysdale, and Kenneth Bogart, Discrete Mathematics for Computer Scientists, Pearson.
10. Jean-Paul Tremblay and R Manohar, Discrete Mathematical Structures with Applications to Computer Science, Tata McGraw-Hill.

Tests

• First Test (07-Sep-2021): Questions with solutions
• Second Test (05-Oct-2021): Questions with solutions
• Third Test (16-Nov-2021): Questions with solutions

Previous course pages: 2020 | 2019 | 2007 | 2006 | 2005