CS21001 Discrete Structures Autumn 2020, L-T-P: 3-1-0

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], Sat 03:30pm–05:00pm [Slot D(A)]
† (Doubt-clearance and tutorial sessions)
Venue     Online
Teaching Assistants     Bijoy Das, Debranjan Pal, Md Rasid Ali, Paritosh Sinha, Pritam Pallab, Rahul Roy, Shramona Chakraborty, Souvik Sur

Notices and Announcements

August 31, 2020
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. No new requests will be entertained irrespective of CGPA.

August 16, 2020
Non-CSE students may apply for this course in ERP. We can accommodate 20 non-CSE students. If the number of applicants is more than that, shortlisting will be done based on CGPA. We will wait until August 30, 2020. We will freeze our decisions on August 31, 2020. No further requests will be entertained after that (irrespective of CGPA).

August 16, 2020
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

TopicDetailsYouTube video
Week 1
Introduction

Discrete versus continuous mathematics. Relevance to Computer Science.

Single part
Basic counting

Sum and product rules.
Permutations and combinations with and without repetition.
Binomial and multinomial theorems.
Catalan Numbers.

Part 1 | Part 2
Query form
Week 2
Propositional logic

Encoding, reasoning and deductions.
Truth tables, satisfiability and validity.

Single part (slides)
First-order logic

Predicates, quantifiers and interpretations.
Logical deduction, Rules and proofs.

Part 1 | Part 2 (slides)

Applications in program verification.

Single part (slides)
Query form
Week 3
Proof techniques

Direct proofs, proof by contradiction and contraposition, proof by cases, cycle of proofs.

Single part (scribes)

Mathematical Induction: Weak and strong forms, well-ordering principle.

Part 1 (scribes) | Part 2 (scribes)

Recursive constructions

Single part (scribes)
Query form
Week 4
Proof techniques

Loop invariance.

Single part (scribes)

Properties of Integers: Divisibility, primes, GCDs, factorizations.

Single part (scribes)

The pigeon-hole principle and its applications.

Single part (scribes)
Query form
Week 5
Sets, relations and functions

Sets, subsets, and power sets, counting using sets, set operations, index sets and partitions.

Single part (slides)

Relations: Definition and properties, equivalence relations and partitions, partial orders, lattices.

Part 1 | Part 2 (slides)

Functions: Definition and properties (injective, surjective, bijective), composite and inverse functions.

Part 1
Query form
Week 6
Sets, relations and functions

Functions: Definition and properties (injective, surjective, bijective), composite and inverse functions.

Part 2 (slides)
Size of a set

Finite and infinite sets, countable sets.

Single part (scribes)

Uncountable sets, Cantor's diagonal argument, and the power-set theorem.

Single part (scribes)

Applications in Computer Science. Unsolvability of problems.

Single part (scribes)
Query form
Week 7
Generating functions

Definition, examples, applications to counting and probability distributions.

Single part

Applications to integer compositions and partitions. Exponential generating functions.

Single part

Solving recurrence relations using generating functions, linear recurrences, Catalan numbers (revisited).

Single part (slides)
Query form
Week 8
Recurrences

Formulation and examples: Programming and counting problems, symmetry and fractals.
Linear recurrences: Characteristic equations, homogeneous and particular solutions.

Part 1 | Part 2 | Part 3 | Part 4 (Slides)
Query form
Week 9
Recurrences

Divide-and-conquer recurrences and the master theorem.

Part 1 | Part 2 (Slides)
Query form
Week 10
Algebraic structures

Rings and fields: Definitions and properties, homomorphisms and isomorphisms, units, subrings.

Single part (slides)

Groups: Definitions and properties, homomorphisms and isomorphisms, cyclic groups, subgroups and cosets.

Part 1 (scribes) | Part 2 (scribes)
Query form
Week 11 (Extra)
Algebraic structures

Modular arithmetic, applications to cryptography

Single part (slides)
Query form

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

Previous course pages: 2019 | 2007 | 2006 | 2005

 CS21001 Discrete Structures Autumn 2020, L-T-P: 3-1-0