DISCRETE STRUCTURE [CT 551] - SYLLABUS
Lecture : 3 Year : II
Tutorial : 0 Part : II
Practical : 0
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.
1. Logic, Induction and Reasoning (12 hours)
1.1. Proposition and Truth function
1.2. Propositional Logic
1.3. Expressing statements in Logic Propositional Logic
1.4. The predicate Logic
1.5. Validity
1.6. Informal Deduction in Predicate Logic
1.7. Rules of Inference and Proofs
1.8. Informal Proofs and Formal Proofs
1.9. Elementary Induction and Complete Induction
1.10. Methods of Tableaux
1.11. Consistency and Completeness of the System
2. Finite State Automata (10 hours)
2.1. Sequential Circuits and Finite state Machine
2.2. Finite State Automata
2.3. Language and Grammars
2.4. Non-deterministic Finite State Automata
2.5. Language and Automata
2.6. Regular Expression and its characteristics
3. Recurrence Relation (8 hours)
3.1. Recursive Definition of Sequences
3.2. Solution of Linear recurrence relations
3.3. Solution to Nonlinear Recurrence Relations
3.4. Application to Algorithm Analysis
4. Graph Theory (15 hours)
4.1. Undirected and Directed Graphs
4.2. Walk Paths, Circuits, Components
4.3. Connectedness Algorithm
4.4. Shortest Path Algorithm
4.5. Bipartite Graphs, Planar Graphs, Regular Graphs
4.6. Planarity Testing Algorithms
4.7. Eulerian Graph
4.8. Hamiltonian Graph
4.9. Tree as a Directed Graph
4.10. Binary Tree, Spanning Tree
4.11. Cutsets and Cutvertices
4.12. Network Flows, Maxflow and Mincut Theorem
4.13. Data Structures Representing Trees and Graphs in Computer
4.14. Network Application of Trees and Graphs
4.15. Concept of Graph Coloring
References:
1 Kenth Rosen, “Discrete Mathematical Structures with Applications to Computer Science”, WCB/ McGraw Hill
2 G. Birkhoff, T.C. Bartee, “Modern Applied Algebra”, CBS Publishers.
3 R. Johnsonbaugh, “Discrete Mathematics”, Prentice Hall Inc.
4 G.Chartand, B.R.Oller Mann, “Applied and Algorithmic Graph Theory”, McGraw Hill
5 Joe L. Mott, Abrahan Kandel, and Theodore P. Baker, “Discrete Mathematics for Computer Scientists and Mathematicians”, Prentice-Hall of India
Lecture : 3 Year : II
Tutorial : 0 Part : II
Practical : 0
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.
1. Logic, Induction and Reasoning (12 hours)
1.1. Proposition and Truth function
1.2. Propositional Logic
1.3. Expressing statements in Logic Propositional Logic
1.4. The predicate Logic
1.5. Validity
1.6. Informal Deduction in Predicate Logic
1.7. Rules of Inference and Proofs
1.8. Informal Proofs and Formal Proofs
1.9. Elementary Induction and Complete Induction
1.10. Methods of Tableaux
1.11. Consistency and Completeness of the System
2. Finite State Automata (10 hours)
2.1. Sequential Circuits and Finite state Machine
2.2. Finite State Automata
2.3. Language and Grammars
2.4. Non-deterministic Finite State Automata
2.5. Language and Automata
2.6. Regular Expression and its characteristics
3. Recurrence Relation (8 hours)
3.1. Recursive Definition of Sequences
3.2. Solution of Linear recurrence relations
3.3. Solution to Nonlinear Recurrence Relations
3.4. Application to Algorithm Analysis
4. Graph Theory (15 hours)
4.1. Undirected and Directed Graphs
4.2. Walk Paths, Circuits, Components
4.3. Connectedness Algorithm
4.4. Shortest Path Algorithm
4.5. Bipartite Graphs, Planar Graphs, Regular Graphs
4.6. Planarity Testing Algorithms
4.7. Eulerian Graph
4.8. Hamiltonian Graph
4.9. Tree as a Directed Graph
4.10. Binary Tree, Spanning Tree
4.11. Cutsets and Cutvertices
4.12. Network Flows, Maxflow and Mincut Theorem
4.13. Data Structures Representing Trees and Graphs in Computer
4.14. Network Application of Trees and Graphs
4.15. Concept of Graph Coloring
References:
1 Kenth Rosen, “Discrete Mathematical Structures with Applications to Computer Science”, WCB/ McGraw Hill
2 G. Birkhoff, T.C. Bartee, “Modern Applied Algebra”, CBS Publishers.
3 R. Johnsonbaugh, “Discrete Mathematics”, Prentice Hall Inc.
4 G.Chartand, B.R.Oller Mann, “Applied and Algorithmic Graph Theory”, McGraw Hill
5 Joe L. Mott, Abrahan Kandel, and Theodore P. Baker, “Discrete Mathematics for Computer Scientists and Mathematicians”, Prentice-Hall of India
No comments:
Post a Comment