EM1050 Discrete Mathematics

EM1050

Discrete Mathematics

3

Core

Fundamentals: Set theory, relations and functions, axiomatic systems, ordinary Induction, invariants, strong induction. Number Theory: Divisibility, the greatest common divisor, Modular arithmetic, Fermat’s Little theorem, RSA algorithm Algebraic Structures: Monoids, groups, rings and fields. Logic and Proofs: Propositional and predicate logic, proof methods and strategy.Graph Theory: Graphs, representation of a graph in a computer, isomorphic graphs, Eulerian and Hamiltonian graphs, planar graphs, graph coloring, trees, spanning trees, binary trees, tree searching, Hasse diagrams. Algorithms: Greedy algorithms, searching and sorting algorithms, algorithms to obtain minimum spanning tree and shortest path of a weighted graph, complexity of an algorithm. Mathematical models for Computing Machines: Finite state machines, finite state automata, Turing machines.

• ● D. K. Joshi, Foundations of Discrete Mathematics,(1989/2015), Wiley-Inter Science. ● D. K. Joshi, Applied Discrete Structures,(2001/2014), New Age International. ● Thomas Koshy, Discrete Mathematics with Applications,1st edition,(2004), Elsevier Academic Press. ● Ian Anderson, A First Course in Discrete Mathematics, (2001), Springer-Verlag. London Limited. ● Kenneth H. Rossen Discrete Mathematics and Applications, (2002),McGraw-Hill Higher Education.