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

[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

 Date Topic Reference 1 06.08.2019 (Tue) Basic counting rules, Pigeon-hole principle Chapters 6.1 and 6.2 of [1] 2 07.08.2019 (Wed) Permutations, Combinations (with and without repetitions) Chapters 6.3, 6.4 and 6.5 of [1] 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 [1] 4 20.08.2019 (Tue) Number of onto functions, derangements Introduction to logic Chapter 8.6 of [1] Chapters 1.1 and 1.2 of [1] 5 21.08.2019 (Wed) Propositional logic: Natural deduction rules Part of Chapters 1.2.1 and 1.2.3 of [2] 6 22.08.2019 (Thu) Propositional logic: Natural deduction rules Chapters 1.2.1 and 1.2.3 of [2] 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 [3] Section 10.2 of [1] 8 04.09.2019 (Wed) Complete matchings in bipartite graphs Hall's marriage theorem Adjacency matrix, counting number of walks Section 10.2 of [1] Section 4.2 (pages 121 - 123: graph representations) of [3] 9 05.09.2019 (Thu) Trees: various equivalent characterizations Section 5.1 of [3] 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 [4] 11 17.09.2019 (Thu) Non-deterministic Finite Automata (NFA) Section 1.2 of [4] 12 18.09.2019 (Thu) Regular expressions Section 1.3 of [4] 13 19.09.2019 (Thu) Regular expressions to NFA NFA to DFA DFA to regular expressions Section 1.3 of [4] Section 1.2 Section 1.3 Tutorial 5 Problems