Organization

• Regular Classes: Wednesday & Friday at 11:10AM to 12:55PM

• Class Venue: Room 718 in the Library Building

• Discussion Hours with TAs: 

• Reading material and videos and exercises will be posted/uploaded regularly.

• Every 2/3 weeks a small online assignment will be posted. You will have to write up your solutions and submit a pdf (scanned or texed up) in the google classroom. 

• In you have any doubts or questions feel free to email the instructor or the TAs or post the question in classroom or ask the question during the class. 

• No cheating policy: If some student is caught cheating (in any of the exam or on the assignments) it would be reported to the dean. The dean will make the final decision on what action to be taken, but the instructor will insist on giving ZERO to the student in the whole course.

• Evaluation:  30% on midsem, 50% on endsem and 20% on Assignements

Instructors and TAs

• Instructor: Sourav Chakraborty (sourav@isical.ac.in)

• TAs:  

1. Soumi Nandi (nandisoumi1@gmail.com)

2. Avijeet Ghosh (avi.ghosh23@gmail.com)

3. Soura Sena Das (sourasenad@gmail.com )

Study Materials

• Introductory material : Introduction, Sets, Relations, Functions [Part1 video, Part2 video, slides]

• Introductory material : Introduction to Propositional and Predicate Logic [Video, slides]

• Introductory material: Introduction to Graph Theory [Video, slides]

• Introduction to Elementary Number Theory and Proof techniques [Video, slides (4a), slides (4b)]

• Proof Techniques [Video, slides (5a), slides (5b)] 

• More on Proof Techniques [Video, slides (6a), slides (6b)] 

• More on Proof Techniques [Video, slides (7a), slides (7b)]

• Induction on Graphs [Video, slides8] 

• Nice write-up on induction 

• Nice write-up on generating function

• Nice write-up on recurrences

• Nice write-up on Binomial Coefficients

Topics covered in class

• Lecture 1: (11/1/23)  Introduction 

• Lecture 2: (13/1/23) Introduction to graphs, induction of graphs, Handshake theorem, HP in tournaments.

• Lecture 3: (18/1/23) Writing proofs in graphs theory. Eulerian Paths.

• Lecture 4 (20/1/23) Counting using Recurrences, Ramsey Number, Sunflower Lemma.

• Lecture 5 (25/1/23) Sunflower Lemma, Helly's Theorem

• Lecture 6 (1/2/23) Formal Introduction to Propositional and Predicate Logic

• Lecture 7 (3/2/23)  Asymptotic notations and recurrences with asymptotic relations

• Lecture 8 (8/2/23)  Counting using generating functions

• Lecture 9 (15/2/23) Solving recurrences using generating functions - Fibonacci sequence, Catalan Number

• Lecture 10 (17/2/23) Counting the number of irreducible polynomials over F_p using generating functions 

• Lecture 11 (22/2/23) Revision on solving recurrences involving asymptotic relations

• Lecture 12 (24/2/23) Revision of some of the topics

• Midsem (3/3/23)

• Lecture 13 (10/3/23) Matchings in graphs - Hall's Marriage THeorem

• Lecture 14 (15/3/23) Connectivity in Graphs

• Lecture 15 (16/3/23) Characterization of trees (Guest lecture by Krisnendu Mukhopadhyay)

• Lecture 16 (22/3/23) Introduction to Planar Graphs

• Lecture 17 (24/3/23) 5-coloring Theorem

• Lecture 18 (29/3/23) Kurotowski's Theorem

• Lectute 19 (31/3/23) Introduction to Network Flows

• Lecture 20 (5/4/23) Max-flow Mincut Theorem

• Lecture 21 (12/4/23) Introduction to Probabilistic Methods and Spectral Graph Theory

• Lecture 22 (21/4/23) Revision of some of the topics

• Endsem

Assignments

• Assignment 1

• Assignment 2

• Assignment 3 - Solve the midsem paper

Problem sets for Practice and useful links

• Link to previous years DMath course MTech 2022-23, MTech 2021-22, MTech2019-2020, MTech 2018-19

• Problem Set on Introduction to Graph theory, Propositional and Predicate Logic and Proof Techniques

• Problem Set on Asymptotic Relations and solving recurrences

• Problem Set on Generating functions, Recurrences and Counting

• Problem Set on everything to be covered till midsem

• Problem Set on Planar Graphs