Discrete Structures
Course Objectives:
 To gain knowledge in discrete mathematics and finite state automata in an algorithmic approach.
 To gain fundamental and conceptual clarity in the area of Logic, Reasoning, Algorithms, Recurrence Relation, Graph Theory, and Theory of Automata.
 Logic, Induction and Reasoning (12 hours)
 Proposition and Truth function
 Propositional Logic
 Expressing statements in Logic Propositional Logic
 The predicate Logic
 Validity
 Informal Deduction in Predicate Logic
 Rules of Inference and Proofs
 Informal Proofs and Formal Proofs
 Elementary Induction and Complete Induction
 Methods of Tableaux
 Consistency and Completeness of the System
 Finite State Automata (10 hours)
 Sequential Circuits and Finite state Machine
 Finite State Automata
 Language and Grammars
 Nondeterministic Finite State Automata
 Language and Automata
 Regular Expression and its characteristics
 Recurrence Relation (8 hours)
 Recursive Definition of Sequences
 Solution of Linear recurrence relations
 Solution to Nonlinear Recurrence Relations
 Application to Algorithm Analysis
 Graph Theory (15 hours)
 Undirected and Directed Graphs
 Walk Paths, Circuits, Components
 Connectedness Algorithm
 Shortest Path Algorithm
 Bipartite Graphs, Planar Graphs, Regular Graphs
 Planarity Testing Algorithms
 Eulerian Graph
 Hamiltonian Graph
 Tree as a Directed Graph
 Binary Tree, Spanning Tree
 Cutsets and Cutvertices
 Network Flows, Maxflow and Mincut Theorem
 Data Structures Representing Trees and Graphs in Computer
 Network Application of Trees and Graphs
 Concept of Graph Coloring
References:
 Kenth Rosen, “Discrete Mathematical Structures with Applications to Computer Science”, WCB/ McGraw Hill
 G. Birkhoff, T.C. Bartee, “Modern Applied Algebra”, CBS Publishers.
 R. Johnsonbaugh, “Discrete Mathematics”, Prentice Hall Inc.
 G.Chartand, B.R.Oller Mann, “Applied and Algorithmic Graph Theory”, McGraw Hill
 Joe L. Mott, Abrahan Kandel, and Theodore P. Baker, “Discrete Mathematics for Computer Scientists and Mathematicians”, PrenticeHall of India
Evaluation Scheme:
The questions will cover all the chapters of the syllabus. The evaluation scheme will be as indicated in the table below:
Chapters 
Hours 
Marks Distribution* 
1 
12 
24 
2 
10 
16 
3 
8 
8 
4 
15 
32 
Total 
45 
80 
*Note: There could be a minor deviation in Marks distribution
