Discrete Mathematics

Home

• Announcements Forum
• Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic[1] – do not vary smoothly in this way, but have distinct, separated values.

  Research in discrete mathematics increased in the latter half of the twentieth century partly due to the development of digital computers which operate in discrete steps and store data in discrete bits. Concepts and notations from discrete mathematics are useful in studying and describing objects and problems in branches of computer science, such as computer algorithms, programming languages, cryptography, automated theorem proving, and software development. Conversely, computer implementations are significant in applying ideas from discrete mathematics to real-world problems, such as in operations research.
  

  Overview

  Prerequisite

  • Basic Mathematics
    

  Course Objectives

  • To use appropriate set, function and relation models to understand practical examples, and interpret the associated operations and terminologies in context.
  • Determine number of logical possibilities of events.
  • Learn logic and proof techniques to expand mathematical maturity.
  • Formulate problems precisely, solve the problems, apply formal proof techniques, and explain the reasoning clearly.
    

  Course Outcomes

  On completion of the course, student will be able to:
  

  • Solve real world problems logically using appropriate set, function, and relation models and interpret the associated operations and terminologies in context.
  • Analyze and synthesize the real world problems using discrete mathematics.
    

• Syllabus and Notes

• Unit 1

  Unit 2

  Unit 3

  Unit 4

  Unit 5

  Unit 6

  Unit 1

  ×

  Set Theory and Logic

  Discrete Mathematics, Significance of Discrete Mathematics in Computer Engineering

  Sets– Naïve Set Theory (Cantorian Set Theory), Axiomatic Set Theory, Need for Sets, Representation of Sets, Set Operations, cardinality of set, principle of inclusion and exclusion

  Types of Sets – Countable and Uncountable Sets, Finite and Infinite Sets, Countably Infinite and Uncountably Infinite Sets

  Introduction to bounded and unbounded sets and multiset

  Countability of Rational Numbers Using Cantor Diagonalization Argument, power set

  Propositional Logic- logic, Propositional Equivalences, Application of Propositional Logic-Translating English Sentences, Proof by Mathematical Induction and Strong Mathematical Induction
  

  Close

  Unit 2

  ×

  Relations and Functions

  Relations and Their Properties, n-ary Relations and Their Applications, Representing Relations , Closures of Relations, Equivalence Relations, Partial Orderings, partitions, Hasse Diagram, Lattices, Chains and Anti-Chains, Transitive Closure and Warshall‘s Algorithm, n-Ary Relations and their Applications

  Functions- Surjective, Injective and Bijective functions, Inverse Functions and Compositions of Functions, The Pigeonhole Principle
  

  Close

  Unit 3

  ×

  Counting

  The Basics of Counting, rule of Sum and Product, Permutations and Combinations, Binomial Coefficients and Identities, Generalized Permutations and Combinations, Algorithms for generating Permutations and Combinations
  

  Close

  Unit 4

  ×

  Graph Theory

  Graphs and Graph Models, Graph Terminology and Special Types of Graphs, Representing Graphs and Graph Isomorphism, Connectivity, Euler and Hamilton Paths, Single source shortest path- Dijkstra's Algorithm, Planar Graphs, Graph Colouring. Case Study- Web Graph, Google map
  

  Close

  Unit 5

  ×

  Trees

  Introduction, properties of trees, Binary search tree, decision tree, prefix codes and Huffman coding, cut sets, Spanning Trees and Minimum Spanning Tree, Kruskal‘s and Prim‘s algorithms, The Max flow- Min Cut Theorem (Transport network). Case Study- Game Tree, Mini-Max Tree
  

  Close

  Unit 6

  ×

  Algebraic Structures and Coding Theory

  The structure of algebra, Algebraic Systems, Semi Groups, Monoids, Groups, Homomorphism and Normal Subgroups, and congruence relations, Rings, Integral Domains and Fields, coding theory, Polynomial Rings and polynomial Codes, Case Study- Brief introduction to Galois Theory –Field Theory and Group Theory
  

  Close
• Previous Years' Exams
  

  Question Papers

  April 2019October 2018April 2018October 2017

• Have Doubts?

• Forum

  Ask your doubts regarding the subject here. Discuss exam strategies, scores and latest trends in this forum.