Discrete Mathematics (MTB-604)

Prerequisites

• Nil

Syllabus

Logic: Propositional and predicate logic. Inference.

Lattices as partially ordered sets and as algebraic systems. Duality, Distributive, complemented and complete lattices. Boolean algebras and their basic properties.

Boolean functions and expressions. Application of Boolean algebra to switching circuits (using AND, OR and NOT gates)

Graphs and Planar Graphs: Graphs, Multi-graphs, Weighted Graphs, Directed graphs. Paths and circuits. Matrix representation of graphs. Eulerian paths and circuits. Planar graphs. Euler’s formula. Trees and spanning trees.

Suggested Readings:

1. C. L. Liu, Elements of Discrete Mathematics, (Second Edition), McGraw Hill, International Edition, 1986.

2. J. P. Tremblay and R. Manohar, Discrete Mathematics with Applications to Computer Science, Tata McGraw-Hill, 1997.

3. S. Wiitala, Discrete Mathematics: A Unified Approach, McGraw-Hill Book Co.

4. N. Deo, Graph Theory with Applications to Computer Science, Prentice-Hall of India,

5. Discrete Mathematics and its Applications by Kenneth Rosen, Seventh (Indian) Edition.

6. Introduction to Graph Theory by Douglas B. West, Second Edition.

7. Introduction to Algorithms by Cormen, Leiserson, Riverst, and Stein, Third Edition.

Weekly Office Hours

FRI : 15:10 - 16:00 Hours

SAT : 15:10 - 16:00 Hours

Reading Materials

1. Theoretical Computer Science Cheat Sheet .

2. Applications of Graphs in Day-to-Day Life.

3. A basic draft on Graphs.

4. A basic draft on Tree.

(On Graph)(Slides taken from Dr. PSM, IITG)

• Graph-BFS: .

• DFS, Spanning Tree.

• MST-KRUSKAL

• MST-PRIMS

• Shortest Paths in a Graph