# Discrete Mathematics

### August - September 2019

 Instructor : B Srivathsan TAs : Ashwani Anand (M.Sc Computer Science, first year) Ekanshdeep Gupta (B. Sc Mathematics and Computer Science, third year)

### 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

### Hours

 Lectures Wed   09:10 - 10:25 Lecture Hall 5 Thu   09:10 - 10:25 Lecture Hall 6 Tutorial sessions Tue   09:10 - 10:25 Lecture Hall 6

### References

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

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

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

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

### Lectures

 Date Topic Reference 1 06.08.2019 (Tue) Basic counting rules, Pigeon-hole principle Chapters 6.1 and 6.2 of  2 07.08.2019 (Wed) Permutations, Combinations (with and without repetitions) Chapters 6.3, 6.4 and 6.5 of  13.08.2019 (Tue) Tutorial 1 Problems 3 14.08.2019 (Wed) Distributing objects into boxes, Principle of inclusion-exclusion Chapters 6.5 and 8.5 of  4 20.08.2019 (Tue) Number of onto functions, derangements Introduction to logic Chapter 8.6 of  Chapters 1.1 and 1.2 of  5 21.08.2019 (Wed) Propositional logic: Natural deduction rules Part of Chapters 1.2.1 and 1.2.3 of  6 22.08.2019 (Thu) Propositional logic: Natural deduction rules Chapters 1.2.1 and 1.2.3 of  26.08.2019 (Mon) Tutorial 2 Problems 27.08.2019 (Tue) Tutorial 3 Problems 29.08.2019 (Thu) Quiz 1 7 03.09.2019 (Tue) Introduction to graphs Euler's theorem Matchings in bipartite graphs Section 4.4 of  Section 10.2 of  8 04.09.2019 (Wed) Complete matchings in bipartite graphs Hall's marriage theorem Adjacency matrix, counting number of walks Section 10.2 of  Section 4.2 (pages 121 - 123: graph representations) of  9 05.09.2019 (Thu) Trees: various equivalent characterizations Section 5.1 of  10.09.2019 (Tue) Tutorial 4 Problems 11.09.2019 (Wed) Quiz 2 10 16.09.2019 (Thu) Introduction to deterministic finite automata (DFA) Section 1.1 of  11 17.09.2019 (Thu) Non-deterministic Finite Automata (NFA) Section 1.2 of  12 18.09.2019 (Thu) Regular expressions Section 1.3 of  13 19.09.2019 (Thu) Regular expressions to NFA NFA to DFA DFA to regular expressions Section 1.3 of  Section 1.2 Section 1.3 Tutorial 5 Problems