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
- Non-deterministic 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”, Prentice-Hall 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
|