BX4005 Mathematical Foundations of Computer Science Syllabus:
BX4005 Mathematical Foundations of Computer Science Syllabus – Anna University PG Syllabus Regulation 2021
COURSE OBJECTIVES:
To introduce Mathematical Logic and their rules for validating arguments and programmes.
To introduce counting principles for solving combinatorial problems.
To give exposure to Graph models and their utility in connectivity problems.
To introduce abstract notion of Algebraic structures for studying cryptographic and its related areas.
To introduce Boolean algebra as a special algebraic structure for understanding logical circuit problems.
UNIT I LOGIC AND PROOFS
Propositional Logic – Propositional Equivalences – Predicates and Quantifiers – Nested Quantifiers – Rules of Inference – Introduction to Proofs – Proof Methods and Strategy.
UNIT II COMBINATORICS
Mathematical Induction – Strong Induction and Well Ordering – The Basics of Counting – The Pigeonhole Principle – Permutations and Combinations – Recurrence Relations Solving Linear Recurrence Relations Using Generating Functions – Inclusion – Exclusion – Principle and Its Applications
UNIT III GRAPHS
Graphs and Graph Models – Graph Terminology and Special Types of Graphs – Matrix Representation of Graphs and Graph Isomorphism – Connectivity – Euler and Hamilton Paths.
UNIT IV ALGEBRAIC STRUCTURES
Groups – Subgroups – Homomorphisms – Normal Subgroup and Coset – Lagrange‘s Theorem – Definitions and Examples of Rings and Fields.
UNIT V LATTICES AND BOOLEAN ALGEBRA
Partial Ordering – Posets – Lattices as Posets – Properties of Lattices – Lattices as Algebraic Systems – Sub Lattices – Direct Product And Homomorphism – Some Special Lattices – Boolean Algebra
TOTAL : 45 PERIODS
COURSE OUTCOMES:
CO1: Apply Mathematical Logic to validate logical arguments and programmes.
CO2: Apply combinatorial counting principles to solve application problems.
CO3: Apply graph model and graph techniques for solving network other connectivity related problems.
CO4: Apply algebraic ideas in developing cryptograph techniques for solving network security problems.
CO5: Apply Boolean laws in developing and simplifying logical circuits.
REFERENCES:
1. Kenneth H.Rosen, “Discrete Mathematics and its Applications”, Tata McGraw Hill Pub. Co.Ltd., Seventh Edition, Special Indian Edition, New Delhi, 2011.
2. Tremblay J.P. and Manohar R, “Discrete Mathematical Structures with Applications to Computer Science”, Tata McGraw Hill Pub. Co. Ltd, 30th Reprint, New Delhi, 2011.
3. Ralph. P. Grimaldi, “Discrete and Combinatorial Mathematics: An Applied Introduction”, Pearson Education, 3rd Edition, New Delhi, 2014.
4. ThomasKoshy, “Discrete Mathematics with Applications”, 2nd Edition, Elsevier Publications, Boston, 2006.
5. SeymourLipschutz and Mark Lipson,”Discrete Mathematics”, Schaum‘s Outlines, Tata McGraw Hill Pub. Co. Ltd., Third Edition, New Delhi, 2013