| Course Outline | General Information | Study Material | Lectures (classwise) |
The course consists of 4 lecture hours per week.
The basic thrust of the course would be to understand discrete mathematics as a mathematical foundation to understanding computer science subjects in general and theoretical computer science subjects like Design and Analysis of Algorithms, Automata, Computational Complexity etc. in particular. In this course, we will broadly study three topics. They are Combinatorics, Graph Theory and Logic.
We will try to stick to the basic course outline as given in this page, but may deviate a bit.
We would assume in the course that you know mathematics at a level as required in the ISI M. Tech. entrance test.
| Class Timings: | Tuesday 09:30-11:10, Thursday 09:30-11:10 Room No. 718, S. N. Bose Bhavan (Library Building) |
| The necessary evil - marks, exam, etc.: | Mid-sem: 25, End-sem: 50, Internal evaluation: 25 |
| Books |
(1) Invitation to Discrete Mathematics J. Matousek and J. Nesetril Clarendon Press, Oxford (2) Applied Combinatorics Fred S. Roberts and B. Tesman Pearson, Prentice Hall (3) Concrete Mathematics Ronald L. Graham, Donald E. Knuth and O. Patashnik Pearson Education (4) Elements of Discrete Mathematics C. L. Liu Tata McGraw Hill (5) Discrete Mathematical Structures B. Kolman, R. C. Busby, S. C. Ross and N. Rehman Pearson Education (6) Graph Theory Frank Harary Narosa Publishing House (7) Introduction to Graph Theory Douglas B. West Prentice Hall, India (8) Introduction to Mathematical Logic Elliott Mendelson Litton Educational Publishing Inc. (9) An Introduction to Algorithms T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein Prentice Hall India. (10) Introduction to Combinatorics Martin J. Erickson Wiley Interscience Publication |
| LECTURE DATES | TOPICS | NOTES (pdf) | BOOKS |
| Lecture 1 (13-7-10) |
Introductory Lecture | - | - |
| Lecture 2 (15-7-10) |
Introduction to logic: Proposition, negation, conjunction, disjunction, universal and existential quantifiers |
- | (3), (4), (8) |
| Lecture 3 (22-7-10) |
Asymptotic notations: big-Oh, small-oh, Theta, Omega | - | (1), (3), (4), (9) |
| Lecture 4 (29-7-10) |
Asymptotic notations: big-Oh, small-oh, Theta, Omega | - | (1), (3), (4), (9) |
| Lecture 5 (3-8-10) |
Mathematical Induction | - | (1), (4) |
| Lecture 6 (5-8-10) |
Sets, Relations, Equivalence, Partial Order | - | (1), (4), (10) |
| Lecture 7 (6-8-10) |
Functions and counting using functions | (1), (4), (10) | |
| Lecture 8 (10-8-10) |
Functions and counting using functions | - | (1), (2), (4) |
| Lecture 9 (17-8-10) |
Principle of Inclusion and Exclusion | (1), (2), (3), (9) | |
| Lecture 10 (23-8-10) |
Recurrences | - | (2), (4), (9) |
| Lecture 11 (26-8-10) |
Recurrences | - | (2), (4), (9) |
| Lecture 12 (27-8-10) |
Counting using Recurrences | - | (2) |
| Lecture 13 (31-8-10) |
Valid parenthesization, number of monotonic Manhattan paths, Solution of recurrences |
- | (1), (2), (3), (9) |
| Lecture 14 (02-9-10) |
Solving recurrences | - | (1), (2), (3), (9) |
| Lecture 15 (03-9-10) |
Generating Function | - | (1), (2) |
| Lecture 16 (09-9-10) |
Recurrences involving convolution, Catalan Number Generating Function, Solving recurrences using Generating Function |
- | (1), (2) |
| Lecture 17 (10-9-10) |
Exponential Generating Function | - | (2) |
| Class Test I (21-9-10) |
Class Test I | Model Solution | - |
| Mid Semestral Exam (23-9-10) |
- | Model Solution | - |
| Lecture 18 (28-9-10) |
Graph Theory basic definitions: complement of a graph, clique, independent set, bipartite graph, chromatic number |
- | (1), (7) |
| Lecture 19 (30-9-10) |
Basic definitions: graph isomorphism, subgraph, induced subgraph, path, cycle, walk, Petersen graph, connected component |
- | (1), (7) |
| Lecture 20 (05-10-10) |
Degree Sum, Adjacency matrix and number of walks, Shortest Path in a weighted graph |
- | (1), (7) |
| Lecture 21 (02-11-10) |
BFS, DFS, Bipartite graphs and odd cycles |
- | (1), (7), (9) |
| Lecture 22 (03-11-10) |
Strongly connected component, Eulerain trail |
- | (1), (7), (9) |
| Lecture 23 (04-11-10) |
Directed graph, Tree |
- | (1), (7) |
| Lecture 24 (09-11-10) |
Radius, Diameter, Center of a graph MST |
- | - |
| Lecture 25 (16-11-10) |
Edge subdivision, Planarity, K(3,3) and K(5), Kuratowski's theorem(statement), Euler's theorem, Chromatic number, Five color theorem |
- | (1), (6), (7) |
| Lecture 26 (17-11-10) |
Number of spanning trees-Cayley's theorem (proof via Prufer code) Minimum Vertex Cover and Maximum Independent Set |
- | (1), (6), (7) |
| Lecture 27 (18-11-10) |
Logic: Tautologies, adequate set of connectives |
- | (8) |
| Lecture 28 (22-11-10) |
An Axiom System for Propositional Calculus |
- | (8) |
| Lecture 29 (23-11-10) |
An Axiom System for Propositional Calculus |
- | (8) |
| Lecture 30 (23-11-10) |
An Axiom System for Propositional Calculus |
- | (8) |
| Lecture 31 (24-11-10) |
An Axiom System for Propositional Calculus |
- | (8) |
| Lecture 32 (25-11-10) |
Hamiltonian path and cycle, Introduction to Matching, perfect matching, alternating path, augmenting path Berge's theorem, Hall's theorem |
- | (7) |
| Class Test II (14-12-10) |
Class Test II | Model Solution | - |