# Discrete Mathematics and Graph Theory (MAT1014)

# Credits : 4

# NOTE:

Discrete maths is one of the few theory-only courses and usually has a high-class average. The course is easy and consists of a lot of topics that are common to Digital Logic and Design, therefore it is recommended to take both these subjects in the same semester. Although it is recommended to refer to a professor's slides to prepare for it, you can also go to Neso Academy or Well Academy if you understand hindi on youtube for better understanding.

Aims to introduce us to discrete mathematics so we start with Mathematical Logic and Statement Calculus. It consists of the following sub-topics: - Introduction-Statements and Notation-Connectives–Tautologies–Two State Devices and Statement logic -Equivalence - Implications–Normal forms - The Theory of Inference for the Statement Calculus. The material for this can be read here: - 1

The next step is learning about Predicate Calculus and its inference theory which are covered in this module. The subtopics are: - The Predicate Calculus - Inference Theory of the Predicate Calculus. The material for this can be read here: - 2

The third module introduces us to different algebraic structures. It includes: - Semigroups and Monoids - Groups – Subgroups – Lagrange’s Theorem Homomorphism – Properties-Group Codes. The material for this can be read here: - 3

Module four is about different types of lattices and their properties. It consists of the following subtopics: - Partially Ordered Relations -Lattices as Posets – Hasse Diagram – Properties of Lattices. The material for this can be read here: - 4

Module five is based on Boolean algebra and algorithms. The module is divided into the following subtopics: - Boolean algebra - Boolean Functions-Representation and Minimization of Boolean Functions–Karnaugh map – McCluskey algorithm. The material for this can be read here: - 5

This module introduces us to the fundamentals of graph theory and its properties. It has been divided as follows: - Basic Concepts of Graph Theory – Planar and Complete graph - Matrix representation of Graphs – Graph Isomorphism – Connectivity–Cut sets-Euler and Hamilton Paths–Shortest Path algorithms. The material for this can be read here: - 6

It consists of Tree structures and traversing. The subtopics are: - Trees – properties of trees – distance and centres in tree –Spanning trees – Spanning tree algorithms- Tree traversals- Fundamental circuits and cut-sets. Bipartite graphs - Chromatic number – Chromatic partitioning – Chromatic polynomial - matching – Covering– Four Colour problem. The material for this can be read here: - 7

Industry Lecture