# Discrete Mathematics

### Instructor :  B Srivathsan

TAs :   Ashwani Anand (M.Sc CS 2),  Satya Prakash Nayak (M.Sc CS 2),   Aditya Prakash (B.Sc CS 3)

### Course description

This is a half-semester course for M. Sc Data Science students.

The plan of the course is given below.
• Part 1: Counting

• Part 2: Logic

• Part 3: Graph theory

• Part 4: Regular expressions

Previous versions: 2019

### Lecture hours

Tuesdays and Thursdays 15:30 - 16:45 via Zoom

Join the Moodle course page for the meeting link. Links to recorded videos will be posted on this webpage after the lecture.

### References

[1] Kenneth Rosen:   Discrete Mathematics and its Applications (Seventh edition)

[2] Michael Huth and Mark Ryan:   Logic in Computer Science (Second edition)

[3] Jiři Matoušek and Jaroslav Nešetřil:   Invitation to Discrete Mathematics (Second edition),   Oxford University Press.

[4] Michael Sipser: Introduction to the theory of computation (Third edition)

### Lectures

 Lecture Date Topic Video and slides Reference 1 15 December 2020 Basic counting rules, Pigeon-hole principle Video    Slides Sections 6.1 and 6.2 of [1] 2 22 December 2020 Permutations, Combinations, Binomial Theorem Video    Slides Sections 6.3 and 6.4 of [1] 3 24 December 2020 Permutations and combinations with repetitions, Distributing objects into boxes Video    Slides Sections 6.5 of [1] 4 29 December 2020 Principle of inclusion-exclusion, Number of onto functions, Derangements Video    Slides Sections 8.5, 8.6 of [1] 3 January 2021 Tutorial 1 Video Problem Sheet 1 4 January 2021 Tutorial 2 Video Problem Sheet 2 5 January 2021 Quiz 1 5 7 January 2021 Introduction to propositional logic and natural deduction rules Video    Slides Sections 1.1 and introduction of 1.2, 1.2.1 of [2] Extra read Sections 1.1 and 1.2 of [1] 6 12 January 2021 Some logic puzzles Video    Slides 7 14 January 2021 Natural Deduction rules - Part I Video    Slides Section 1.2.1 from [2] 8 19 January 2021 Natural Deduction rules - Part II Video    Slides Section 1.2.1 from [2] 9 21 January 2021 Regular Expressions Video    Slides Pages 13-14 and Section 1.3 of [4] 24 January 2021 Tutorial 3 Video Problem Sheet 3 10 26 January 2021 Deterministic Finite Automata Video    Slides    Solutions Section 1.1 of [4] 27 January 2021 Quiz 2 11 28 January 2021 Non-deterministic Finite Automata Video    Slides Section 1.2 of [4] 12 30 January 2021 Regular expressions to NFA, NFA to DFA Video    Slides Section 1.2, 1.3 of [4]