| 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 16:05-17:50, Thursday 16:05-17:50 Room No. 709-710, S. N. Bose Bhavan (Library Building) |
| The necessary evil - marks, exam, etc.: | Mid-sem: 30, End-sem: 50, Internal evaluation: 20 |
| 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. |
| LECTURE DATES | TOPICS | NOTES (pdf) | BOOKS |
| Lecture 1 (15-7-08) |
Introductory Lecture | - | - |
| Lecture 2 (17-7-08) |
Mathematical Induction and asymptotic notations: big-Oh, small-oh, Theta, Omega | - | (1), (3), (4) |
| Lecture 3 (22-7-08) |
Functions and counting using functions | - | (1), (4) |
| Lecture 4 (29-7-08) |
Functions and counting using functions | - | (1), (4) |
| Lecture 5 (31-7-08) |
Equivalences and ordered sets | - | (1), (4) |
| Lecture 6 (5-8-08) |
Introduction to logic: Proposition, negation, conjunction, disjunction, universal and existential quantifiers |
- | (5) |
| Lecture 7 (7-8-08) |
Implications: conditional, biconditional; tautology, logical equivalence | - | (5) |
| Lecture 8 (12-8-08) |
Derangement, Recurrences | - | (1), (2) |
| Lecture 9 (14-8-08) |
Linear Homogenous Recurrences | - | (2), (4) |
| Lecture 10 (19-8-08) |
Inhomogenous Recurrences | - | (2), (4) |
| Lecture 11 (21-8-08) |
Divide and Conquer Recurrences | - | - |
| Lecture 12 (26-8-08) |
Generating Function | - | (2) |
| Lecture 13 (28-8-08) |
Pigeonhole principle | - | (2) |
| Lecture 14 (2-9-08) |
Graph Theory: Introduction | - | (1), (2), (6), (7) |
| Lecture 15 (4-9-08) |
Graph Theory: Introduction | - | (1), (2), (6), (7) |
| Mid Sem | Model Solution | - | |
| Lecture 16 (23-9-08) |
Graph traversal (DFS/BFS), graph acyclicity, topological sort, | - | (1), (2) |
| Lecture 17 (25-9-08) |
Strongly connected component, Shortest path (Dijkstra's algorithm) |
- | (1), (2) |
| Lecture 18 (30-9-08) |
Minimum spanning tree (Kruskal and Prim's algorithm) |
- | (1), (2) |
| Lecture 19 (16-10-08) |
Eulerian graphs and tour | - | (1), (2), (6), (7) |
| Lecture 20 (21-10-08) |
Eulerian graphs and tour Bi-partite graph |
- | (1), (6), (7) |
| Lecture 21 (4-11-08) |
Clique, Vertex Cover, Independent Set, Dominating Set, Chromatic Number Jordan curve theorem statement, use in proving K(3,3) and K(5) are non-planar |
- | (1), (6), (7) |
| Lecture 22 (6-11-08) |
Kuratowski's theorem(statement), planar graph, Euler's theorem Four-color theorem(statement), Five-color theorem |
- | (1), (6), (7) |
| Lecture 23 (8-11-08) |
Number of spanning trees-Cayley's theorem (proof via Prufer code) Hamiltonian path, Hamiltonian closure |
- | (1), (7) |
| Lecture 24 (11-11-08) |
Propositional Calculus - Tautologies | - | (8) |
| Lecture 25 (13-11-08) |
Propositional Calculus - Adequate Set of connectives | - | (8) |
| Lecture 26 (18-11-08) |
An Axiom System for Propositional Calculus | - | (8) |
| Class Test | Model Solution | - | |
| End Sem | Model Solution | - |