Mathematics for Computer Sciences

Semester and Year Offered:

Course Coordinator and Team:

Email of course coordinator:

Pre-requisites: MA512/MA532 (Discrete Mathematics)

Aim:

In this course, students will be able to develop mathematical thinking and problem-solving skills associated with writing proofs and well ordering principle. Students will be exposed to a wide variety of mathematical concepts that are used in the Computer Science discipline.

Course Outcomes:

After completing this course, students should able to

1. understand the concepts related to Logic and Data Type,
2. familiarise Automata Theory and coding theory.

Brief description of modules/ Main modules:

Proof, Logic and Data Type

1. Proofs and well ordering principle Propositions, Predicates, The Axiomatic Method, Axioms, Proving an Implication, Proving an “If and Only If”, Proof by Cases, Proof by Contradiction, Well Ordering Proofs, Factoring into Primes, Well Ordered Sets, Ordinary Induction, Strong Induction, Strong Induction vs. Induction vs. Well Ordering
2. Logical Formulas and Mathematical Data Types Propositions from Propositions, Propositional Logic in Computer Programs, Equivalence and Validity, The Algebra of Propositions, The SAT Problem, Predicate Formulas, Sets, Sequences, Functions, Binary Relations, Finite Cardinality, Recursive Definitions and Structural Induction, Strings of Matched Brackets, Recursive Functions on Nonnegative Integers, Arithmetic Expressions, Induction in Computer Science, Infinite Cardinality,The Halting Problem, The Logic of Sets

Automata Theory

1. Introduction Automata: The Methods and the Madness Why Study Automata Theory? Introduction to Finite Automata, Structural Representations, Automata and Complexity, Alphabets, Strings, Languages The Ground Rules, The Protocol, Enabling the Automata to Ignore Actions, The Entire System as an Automaton, Using the Product Automaton to Validate the Protocol.
2. Deterministic and Nondeterministic Finite Automata Definition of a Deterministic Finite Automaton, How a DFA Processes Strings, Simpler Notations for DFA's, Extending the Transition Function to Strings, The Language of a DFA An Informal View of Nondeterministic Finite Automata, Definition of Nondeterministic Finite Automata, The Extended Transition Function, The Language of an NFA, Equivalence of Deterministic and Nondeterministic Finite Automata, A Bad Case for the Subset Construction.
3. An Application: Text Search Finding Strings in Text, Nondeterministic Finite Automata for Text Search, A DFA to Recognize a Set of Keywords

Coding Theory

The Binary Symmetric Channel, Block Codes, Weight and Distance, Generator and Parity-Check Matrices, Group Codes, Coset Decoding, Hamming Codes, Extended Hamming Codes

Assessment Details with weights:

Tentative Assessment schedule with details of weightage

:

Reading List:

Thomson Leighton and Albert R Meyer, Mathematics for Computer Science, EBook, MIT opencourseware, 2017.

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (3rd Edition), Pearson, 2009

ADDITIONAL REFERENCE: