Course Outline | General Information | Study Material | Lectures (classwise) |

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

- General Information:
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

- Study material:
Keep looking regularly for any updates
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. - Lectures (classwise):
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 -