- The main objective of this course is to buildup the mathematical foundation for the study of computational science and computer technology.
- This course introduces the student to discrete mathematics and finite state automata through an algorithmic approach and focuses on various problems solving technique.
- It helps the target student in gaining fundamental and conceptual clarity in the area of Logic Reasoning. Algorithms, Recurrence relation. Graph Theory, and Theory of Automata.
Unit I: Graph Theory ———————————————————- 15 hours
- Directed and Undirected Graphs
- Connected Components
- Connected Component Algorithm
- Shortest Path Algorithm
- Computer representation a graph (Static Representation only, like Adjacency Matrix, Incidence Matrix, Path Matrix):
- Bi-partite graphs
- Regular graphs
- Planar graphs
- Euler graph
- Hamilton graph and their properties and characterization
- Application of graph theory in computer science (with example).
Unit II: Logic and Induction ————————————————— 8 hours
- Propositions and Truth functions
- Predicates and Quantification
- Predicate Logic
- Expressing statement in the language of Logic
- Deduction in Predicate Logic
- Elementary Step-wise Induction
- Complete Induction.
Unit III: Introduction to Mathematical Reasoning ———————— 7 hours
- Formal Languages
- Inductive Definitions:
- Rules of Inference and Proofs
- Direct Proof and Indirect Proof
- Formal Proof and Informal Proof.
Unit IV: Recurrence Relations ————————————————- 7 hours
- Recursive Definition of Sequences
- Differencing and Summation
- Solution of Linear Recursive Relation
- Solution of Non-linear Recurrence Relation.
Unit V: Finite State Automata ————————————————- 8 hours
- Alphabets and Language
- Notion of a State
- State Machine (FSM and DFA)
- Regular Expression
- Equivalence Relation
- Richard Johnsonbaugh, Discrete Mathematics, Fifth Edition, Addison Wesley, Pearson Education Asia (LPE), ISBN: 81-780-82799, 2000
- Mott, Joe L., Kandel Abraham and Baker, Theodoe P., Discrete Mathematics for Computer Scientists and Mathematicians, Second Edition, Prentice-Hall, ISBN: 81-203-1502-2
- Liu, C.L., Elements of Discrete Mathematics, TMH, 2000, ISBN: 0-07-043476-X
- Trus, J.Discrete Mathematics for Computer Scientists, Second Edition, Addision Wesley ISBN: 0-201-36061,1999