Discrete Mathematics

December 2020 - January 2021

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

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

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]