IOE Syllabus of Discrete Structure (DS)

Discrete Structure (Subject code: CT 551) is included on IOE Syllabus for Computer Engineering – II Year II Part with the objective to gain knowledge in discrete mathematics and finite state automata in an algorithmic approach and to gain fundamental and conceptual clarity in the area of Logic, Reasoning, Algorithms, Recurrence Relation, Graph Theory, and Theory of Automata.

  1. Logic, Induction and Reasoning (12 hours)
    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 (10 hours)
    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 (8 hours)
    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 (15 hours)
    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. Cut sets and Cut vertices
    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

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

*There could be a minor deviation in Marks distribution

We're always listening.
Have something to say about this article? Find us on Facebook, Twitter or our LinkedIn.
Raju Dawadi
Raju Dawadi
Raju is currently actively involved in DevOps world and is focused on Container based architecture & CI/CD automation along with Linux administration. Want to discuss with him on any cool topics? Feel free to connect on twitter, linkedIn, facebook.

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.