| 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 | UPLOADED ON |
LAST UPDATED ON |
| Lecture 1 (21-7-09) |
Introductory Lecture | Lecture 1 | - | 27-07-09 | 10-08-09 |
| Lecture 2 (22-7-09) |
Asymptotic notations: big-Oh, small-oh, Theta, Omega | - | (1), (3), (4), (9) | - | - |
| Lecture 3 (23-7-09) |
Asymptotic notations: big-Oh, small-oh, Theta, Omega | Lectures 2 and 3 | (1), (3), (4), (9) | 22-08-09 | - |
| Lecture 4 (27-7-09) |
Introduction to logic: Proposition, negation, conjunction, disjunction, universal and existential quantifiers |
Lecture 4 | (3), (4), (8) | 10-08-09 | - |
| Lecture 5 (28-7-09) |
Mathematical Induction | Lecture 5 | (1), (4) | 17-08-09 | - |
| Lecture 6 (4-8-09) |
Sets and relations | - | (1), (4), (10) | ||
| Lecture 7 (7-8-09) |
Functions and counting using functions | Lectures 6 and 7 | (1), (4), (10) | 10-08-09 | - |
| Lecture 8 (11-8-09) |
Principle of inclusion and exclusion | - | (1), (2), (4) | - | - |
| Lecture 9 (13-8-09) |
Derangement, Recurrences | Lectures 8 and 9 | (1), (2), (3), (9) | 05-09-09 | - |
| Lecture 10 (18-8-09) |
Linear Homogenous Recurrences | - | (2), (4), (9) | - | - |
| Lecture 11 (20-8-09) |
Inhomogenous Recurrences | - | (2), (4), (9) | - | - |
| Lecture 12 (25-8-09) |
Divide and Conquer Recurrences | - | (9) | - | - |
| Lecture 13 (27-8-09) |
Generating Function | - | (2) | - | - |
| Lecture 14 (1-9-09) |
Generating Function | - | (2) | - | - |
| Lecture 15 (3-9-09) |
Pigeonhole Principle | Lecture 15 | (1), (2), (6), (7) | 03-09-2009 | - |
| Lecture 16 (8-9-09) |
Graph Theory: Introduction | - | (1), (2), (6), (7) | ||
| Class Test I (9-9-09) |
Model Solution | - | |||
| Lecture 17 (10-9-09) |
Graph Theory: Lecture 2 | - | (1), (2), (6), (7) | ||
| Mid Semestral Examination (16-9-09) |
Model Solution | - | |||
| Lecture 18 (6-10-09) |
Basic definitions: complement graph, clique, independent set, bipartite graph, chromatic number, graph isomorphism, subgraph, induced subgraph, path, cycle, walk, connected component, degree sum and handshake lemma, basics of Petersen graph. | - | (1), (6), (7) | ||
| Lecture 19 (8-10-09) |
Adjacency matrix of a graph, components, cut edges, cut vertives. Bipartite graphs | - | (1), (6), (7) | ||
| Lecture 20 (13-10-09) |
Eulerian tour in graphs | - | (1), (7) | ||
| Lecture 21 (15-10-09) |
Directed Graphs, Eulerian circuit characterization of a directed graph. Depth First Search Traversal of a graph |
- | (1), (7), (9) | ||
| Lecture 22 (20-10-09) |
types of edges in DFS, acyclicity in a graph, topological sorting, strongly connected component |
- | (1), (7), (9) | ||
| Lecture 23 (22-10-09) |
Tree, properties of tree, distances in graphs, diameter, radius, eccentricity, centre of a graph |
- | (1), (6), (7) | ||
| Lecture 24 (27-10-09) |
Shortest path (Dijkstra's algorithm), Minimum spanning tree (Kruskal and Prim's algorithm) | - | (1), (9) | ||
| Lecture 25 (29-10-09) |
Number of spanning trees-Cayley's theorem (proof via Prufer code) | - | (1), (7) | ||
| Lecture 26 (03-11-09) |
Jordan curve theorem statement, use in proving K(3,3) and K(5) are non-planar; Kuratowski's theorem(statement), planar graph and Euler's formula for planar graphs | - | (1), (6), (7) | ||
| Lecture 27 (05-11-09) |
Chromatic number, Five color theorem, Statement of four color theorem,
Crossings in a non-planar graph, minimum vertex cover, maximum independent set |
- | (1), (6), (7) | ||
| Lecture 28 (10-11-09) |
Hamiltonian Path, Hamiltonian closure
Introduction to Matching, perfect matching, alternating path, augmenting path |
- | (1), (6), (7) | ||
| Lecture 29 (12-11-09) |
Matching: Berge's theorem, Hall's theorem | - | (1), (6), (7) | ||
| Lecture 30 (17-11-09) |
Logic: Tautologies, adequate set of connectives | - | (8) | ||
| Lecture 31 (19-11-09) |
Logic: An axiom system for propositional calculus | - | (8) | ||
| Class Test II (3-12-09) |
Model Solution | - |