CAS761

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 

Objectives:

  • To acquire skills in solving mathematical and logical problems.
  • To comprehend mathematical principles and logic.
  • To understand fundamental concepts and tools in discrete mathematics with emphasis on their applications to computer science.

 

Set Theory : Sets and operations, properties - power set - methods of proof - relations, graph and matrix of a relation - partial and total orders, well ordering - equivalence relations, classes and properties - functions, 1-1, onto and bijective - composition of relations and functions - inverse functions.

Mathematical Logic: Propositions and logical operators – Truth table – Equivalences and implications – Basic laws– Some more connectives – Functionally complete set of connectives– Review of Propositional Calculus - Validity - Satisfiability related concepts - CNF and DNF forms - Conversion of arbitrary propositional formula to CNF or DNF.

Groups, Rings and Fields: Introduction-Algebraic Structures, Groups, Abelian Group, Order, Cyclic Group, Homomorphism (Definition), Isomorphism (Definition), Kernel of f (Definition), Rings, Field and its Axioms, Sub-fields, Finite Fields, Powers and primitive roots in finite fields.

Basic Number Theory : Basic Notions-Prime Number Theorem, GCD, Euclidean algorithm, Solving ax + by = d, Congruence, The Chinese Remainder Theorem, Modular Exponentiation, Fermat and Euler , Primitive Roots, Inverting Matrices Mod n, Square Roots Mod n ,Legendre and Jacobi Symbols, Perfect Numbers and Mersenne Numbers.

Graph Theory : Definitions and basic results - Representation of a graph by a matrix and adjacency list - Trees - Cycles - Properties - Paths and connectedness - Sub graphs - Graph Isomorphism - Operations on graphs - Vertex and edge cuts - Vertex and edge connectivity, Spanning Trees, Euler circuits, Hamiltonian graphs.

References:

 

  1. Kenneth H. Rosen, “Discrete Mathematics and Its Applications”, 7th Edition, McGraw-Hill, 2012.
  2. Mahima Ranjan Adhikari and Avishek Adhikari, “Basic Modern Algebra with Applications”, Springer, 2014.
  3. Kolman, Busby and Ross, “Discrete Mathematical Structures”, 6th Edition, PHI, 2009.

 

Outcome:

    Students will be able to:

·          Apply  the  concepts  of  discrete  mathematics  in  the  modeling  and  design  of computational problems.