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.

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
 

Grading

2 Quizzes 50%
Final exam 50%

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