
 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.
Course Contents:
Unit I: Graph Theory ——————————————————— 15 hours

 Definitions
 Directed and Undirected Graphs
 Walk
 Path
 Circuits
 Connected Components
 Connected Component Algorithm
 Shortest Path Algorithm
 Computer representation a graph (Static Representation only, like Adjacency Matrix, Incidence Matrix, Path Matrix):
 Bipartite 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
 Propositional
 Predicate Logic
 Expressing statement in the language of Logic
 Deduction in Predicate Logic
 Elementary Stepwise Induction
 Complete Induction.
Unit III: Introduction to Mathematical Reasoning ———————— 7 hours

 Formal Languages
 Inductive Definitions:
 Axioms
 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 Nonlinear 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
Reference Books:

 Richard Johnsonbaugh, Discrete Mathematics, Fifth Edition, Addison Wesley, Pearson Education Asia (LPE), ISBN: 8178082799, 2000
 Mott, Joe L., Kandel Abraham and Baker, Theodoe P., Discrete Mathematics for Computer Scientists and Mathematicians, Second Edition, PrenticeHall, ISBN: 8120315022
 Liu, C.L., Elements of Discrete Mathematics, TMH, 2000, ISBN: 007043476X
 Trus, J.Discrete Mathematics for Computer Scientists, Second Edition, Addision Wesley ISBN: 020136061,1999