Mathematical Foundation of Computer Science

1. 1. The main objective of this course is to buildup the mathematical foundation for the study of computational science and computer technology.
   2. This course introduces the student to discrete mathematics and finite state automata through an algorithmic approach and focuses on various problems solving technique.
   3. 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

1. 1. Definitions
   2. Directed and Undirected Graphs
   3. Walk
   4. Path
   5. Circuits
   6. Connected Components
   7. Connected Component Algorithm
   8. Shortest Path Algorithm
   9. Computer representation a graph (Static Representation only, like Adjacency Matrix, Incidence Matrix, Path Matrix):
      1. Bi-partite graphs
      2. Regular graphs
      3. Planar graphs
      4. Euler graph
      5. Hamilton graph and their properties and characterization
   10. Application of graph theory in computer science (with example).

Unit II: Logic and Induction ————————————————— 8 hours

1. 1. Propositions and Truth functions
   2. Predicates and Quantification
   3. Propositional
   4. Predicate Logic
   5. Expressing statement in the language of Logic
   6. Deduction in Predicate Logic
   7. Elementary Step-wise Induction
   8. Complete Induction.

Unit III: Introduction to Mathematical Reasoning ———————— 7 hours

1. 1. Formal Languages
   2. Inductive Definitions:
      1. Axioms
      2. Rules of Inference and Proofs
      3. Direct Proof and Indirect Proof
      4. Formal Proof and Informal Proof.

Unit IV: Recurrence Relations ————————————————- 7 hours

1. 1. Recursive Definition of Sequences
   2. Differencing and Summation
   3. Solution of Linear Recursive Relation
   4. Solution of Non-linear Recurrence Relation.

Unit V: Finite State Automata ————————————————- 8 hours

1. 1. Alphabets and Language
   2. Notion of a State
   3. State Machine (FSM and DFA)
   4. Regular Expression
   5. Equivalence Relation

Reference Books:

1. 1. Richard Johnsonbaugh, Discrete Mathematics, Fifth Edition, Addison Wesley, Pearson Education Asia (LPE), ISBN: 81-780-82799, 2000
   2. 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
   3. Liu, C.L., Elements of Discrete Mathematics, TMH, 2000, ISBN: 0-07-043476-X
   4. Trus, J.Discrete Mathematics for Computer Scientists, Second Edition, Addision Wesley ISBN: 0-201-36061,1999