Discrete Structure (DS) Syllabus
Here is DS Course Content along with Marks Distribution. Practice Well!!
Marks Distribution
| Chapters | Hours | Marks |
|---|---|---|
| 1. Logic, Induction and Reasoning | 12 | 24 |
| 2. Finite State Automata | 10 | 16 |
| 3. Recurrence Relation | 8 | 8 |
| 4. Graph Theory | 15 | 32 |
| Total | 45 | 80 |
Logic, Induction and Reasoning
- 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
- 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
- Recursive Definition of Sequences
- Solution of Linear recurrence relations
- Solution to Nonlinear Recurrence Relations
- Application to Algorithm Analysis
Graph Theory
- 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
- Cut sets and Cut vertices
- Network Flows, Maxflow and Mincut Theorem
- Data Structures Representing Trees and Graphs in Computer
- Network Application of Trees and Graphs
- Concept of Graph Coloring
DS Course Content – Notes IOE