Discrete Structure

Syllabus

1. Logic, Induction and Reasoning
   1. Proposition and Truth function
   2. Propositional Logic
   3. Expressing statements in Logic Propositional Logic
   4. The predicate Logic
   5. Validity
   6. Informal Deduction in Predicate Logic
   7. Rules of Inference and Proofs
   8. Informal Proofs and Formal Proofs
   9. Elementary Induction and Complete Induction
   10. Methods of Tableaux
   11. Consistency and Completeness of the System
2. Finite State Automata
   1. Sequential Circuits and Finite state Machine
   2. Finite State Automata
   3. Language and Grammars
   4. Non-deterministic Finite State Automata
   5. Language and Automata
   6. Regular Expression and its characteristics
3. Recurrence Relation
   1. Recursive Definition of Sequences
   2. Solution of Linear recurrence relations
   3. Solution to Nonlinear Recurrence Relations
   4. Application to Algorithm Analysis
4. Graph Theory
   1. Undirected and Directed Graphs
   2. Walk Paths, Circuits, Components
   3. Connectedness Algorithm
   4. Shortest Path Algorithm
   5. Bipartite Graphs, Planar Graphs, Regular Graphs
   6. Planarity Testing Algorithms
   7. Eulerian Graph
   8. Hamiltonian Graph
   9. Tree as a Directed Graph
   10. Binary Tree, Spanning Tree
   11. Cutsets and Cutvertices
   12. Network Flows, Maxflow and Mincut Theorem
   13. Data Structures Representing Trees and Graphs in Computer
   14. Network Application of Trees and Graphs
   15. Concept of Graph Coloring