Topic outline

  • CSE131-Discrete Mathematics

    Discrete Mathematics


    Discrete Mathematics


    WELCOME NOTE

     

     

    Dear Students, 

    Welcome to the Fall 2022 Semester!
    Welcome back, Students. I can’t wait to see all your smiling faces!  I am here to support you every step of the way.

    I encourage you to make the most of your time here.  Remember to make it a great year. I will see you soon.


    INSTRUCTOR


    Image

    Md. Sajib Hossain

    Lecturer
    Department of CSE
    Daffodil International University

    Email: sajib.cse0388.c@diu.edu.bd
    Mobile: (+88) 01711306945
    Room: 739, AB-4


    INSTRUCTION/GUIDELINE FOR THE COURSE
      • All the students registered for this course have to enroll in BLC
      • Students can find all the course materials from BLC.
      • All the students have to submit the soft copy of their "Assignment " in Moodle under assignment section created here and for this they will be graded here.
      • One weekly discussion or feedback forum is created under each of the lecture. Students have to give their feedback on these forum and marks will be given for their feedback
      • Announcement regarding the class will be posted on BLC. 
      • 3 Quizzes will be held on face-to-face class and 1 quiz will be held on online (BLC) and it will be announced before the class.
      • The question pattern and the syllabus for the quizzes, midterm and final exam is given here under each of the section (quizzes, midterm and final)
      • There are midterm and final exam preparation forum under these sections where students can discuss with each other about their midterm and final exam syllabus, any problem regarding the exam etc.


      COURSE RATIONALE

      Concepts and notations from discrete mathematics are useful in studying and describing objects and problems in all branches of computer science, such as computer algorithms, programming languages, cryptography, automated theorem proving, and software development. It helps improve reasoning power and problem-solving skills. Therefore, it can be considered the backbone of computer science. 

      COURSE OBJECTIVE

      • The goal of this course is to introduce students to ideas and techniques from discrete mathematics that are widely used in science and engineering for thinking logically and mathematically and apply these techniques in solving problems
      • To achieve this goal, students will learn logic and proof, sets, functions, mathematical reasoning as well as key topics involving relations, graphs, and trees.


      COURSE OUTCOME (CO'S)

      COURSE OUTCOME

      CO1

      Be able to comprehend formal logical arguments as well as construct logical proofs with the ability to verify them

      CO2

      Demonstrate skills in expressing mathematical properties formally via the formal language of propositional logic and predicate logic

      CO3

      Gain experience in using various techniques of mathematical induction to prove simple mathematical properties of a variety of discrete structures

      CO4

      Be able to specify and manipulate basic mathematical objects such as sets, functions, and relations and will also be able to verify simple mathematical properties that these objects possess

      CO5

      Demonstrate knowledge of some basic properties and types of graphs and trees and will also be able to apply it to solve fundamental engineering problems


      ASSESSMENT PLAN





      COUNSELING HOURS

      COUNSELING HOURS



      Student Feedback


        


      Additional Support and Library Resources for Students



    • Week 1 (Propositional Logic)

      Week One

      PROPOSITIONAL LOGIC

      LESSON OBJECTIVE

      Lesson 1

      • In this lesson, discrete mathematics will be introduced and a discussion on propositional logic will be initiated.

      Lesson 2

      • In this lesson, a discussion on propositional logic will be continued.


      LEARNING OUTCOME

      • Students will understand what makes up a correct mathematical argument
      • Students will be able to develop an arsenal of different proof methods that will enable students to prove many different types of results
      • Students will be able to explain the process of developing mathematics. 
      • They will get the concept about propositional logic and why this logic is used in Computer Science. 
      • They will get an overview because Discrete Mathematics is important in building the logic in Computer Science.
      • Overview of Discrete Mathematics.
      • Learn about Propositional logic 
      • Learn about different types of Propositions
      • Learn about Bit Operations 

      DISCUSSION TOPICS

      • Introduction 
      • Introduction to Discrete Mathematics
      • Propositional Logic
      • Converse, Contrapositive, and Inverse
      • Bi-conditional Statement
      • Compound Propositions
      • Bit Operations

      LECTURE VIDEO


       

       

      More Video 

    • Week 2 (Propositional Equivalence)

      Week Two

      PROPOSITIONAL EQUIVALENCE


      LESSON OBJECTIVE

      Lesson 3

      • In this lesson, discussion on propositional logic will be continued with the topic of logical equivalence

      Lesson 4

      • In this lesson, a discussion on predicates and quantifiers in propositional logic will be introduced.


      LEARNING OUTCOME

      • Correct mathematical argument and introduce tools to construct these arguments
      • Different proof methods
      • Several strategies for constructing proofs
      • The notion of a conjecture and the process of developing mathematics by studying conjectures
      • Truth table and strategies for constructing logical equivalence
      • Learn about Propositional Equivalences
      • Learn about Tautology, Contradiction, and Contingency
      DISCUSSION TOPICS
      • Propositional Equivalences
      • Tautology, Contradiction, and Contingency
      • Logical Equivalence


      LECTURE VIDEO

            

         

      MORE LECTURE VIDEO FOR CLEAR IDEA

       

       

      IMPORTANT RULES FOR DNF



    • Assignment 1

      Assignment 1

      • Assignment 1
        Opened: Tuesday, 16 August 2022, 12:00 PM
        Due: Monday, 22 August 2022, 11:59 PM

    • Week 3 (Predicates and Quantifiers)

      Week 3

      PREDICATES AND QUANTIFIERS


      LESSON OBJECTIVE

      Lesson 5

      • In this lesson, a discussion on predicates and quantifiers in propositional logic will be continued

      Lesson 6

      • In this lesson, a discussion on sets and its operations will be introduced


      LEARNING OUTCOME

      • After this lecture students will get clear conception about Predicates and Quantifiers  
      • They will be able to represent a sentence using Predicates and Quantifiers. 
      • They will also get a basic concept of set, set operations and why set is used in Discrete Mathematics
      • Learn about Predicates and Quantifiers 
      • Learn about Universal Quantification
      • Learn about Existential Quantification 
      • Learn about the difference between Universal Quantification and Existential Quantification 
      DISCUSSION TOPICS
      • Predicates and Quantifiers
      • Universal Quantification
      • Existential Quantification


      LECTURE VIDEO
       
       

    • Quiz 1



      Quiz 1: 13th September 2022 (Face-to-Face)

         Topic:

      • Propositional Logic
      • Propositional Equivalence
      • Predicates and Quantifiers

      • Week 4 (Sets)

        Week Four


        SETS


        LESSON OBJECTIVE

        Lesson 7

        • In this lesson, a discussion on sets and its operations will be continued

        Lesson 8

        • In this lesson, a discussion on functions and its usage will be introduced


        LEARNING OUTCOME

        • After the lecture students will be able to learn why set is important in discrete mathematics and different operation of sets.
        • They will learn to describe a set.
        • They will learn about equality of sets.
        • They will learn about venn diagram.
        • They will learn about subsets.
        • They will learn about power sets.
        • They will learn about cartesian products.
        • They will also get the idea of functions, its importance, use of function
        DISCUSSION TOPICS

        • Sets and Objects
        • Describing sets
        • Equality of sets
        • Venn Diagram
        • Subset
        • Cardinality
        • Power sets
        • Cartesian products


        LECTURE VIDEO

         

         

      • Week 5 (Set Operations)




        SET OPERATIONS


        LESSON OBJECTIVE

        Lesson 9

        • In this lesson, a discussion on sets and its operations will be continued

        Lesson 10

        • In this lesson, a discussion on functions and its usage will be introduced


        LEARNING OUTCOME

        • After the lecture students will be able to learn why set is important in discrete mathematics and different operation of sets.
        • They will learn about UNION of sets.
        • They will learn about INTERSECTION of sets.
        • They will learn about Disjoint sets.
        • They will learn about Inclusion-Exclusion principle.
        • They will learn about Difference and Symmetric difference of sets.
        • They will learn about Complement of sets.
        • They will learn about Membership table.
        • They will learn about Generalization of sets.
        DISCUSSION TOPICS

        • Sets and operations
        • Union of sets
        • Intersection of sets
        • Disjoint sets
        • Inclusion-Exclusion principle
        • Difference and Symmetric difference of sets
        • Complement of sets
        • Membership table
        • Generalization of sets


        LECTURE VIDEO

         
         

      • Week 6 (Functions)



        FUNCTIONS


        LESSON OBJECTIVE

        Lesson 11

        • In this lesson, a discussion on function and its operations will be continued

        Lesson 12

        • In this lesson, a discussion on functions and its example will be continued


        LEARNING OUTCOME

        • After the lecture students will be able to learn why function is important in discrete mathematics and different operation of function.
        • They will learn about domain, co-domain, image, preimage and range.
        • They will learn about One-to-One, Many-to-One functions.
        • They will learn about Onto and Into functions.
        • They will learn about Bijective functions.
        • They will learn about addition and production of function.
        • They will learn about composition of function.
        • They will learn about inverse of function.
        • They will learn about identity function.
        DISCUSSION TOPICS

        • Functions and operations
        • Domain, co-domain, image, preimage and range
        • One-to-One, Many-to-One functions
        • Bijective functions
        • Addition and production of function
        • Composition of function
        • Inverse of function
        • Identity function


        LECTURE VIDEO

         
         

      • Assignment 2


        • Assignment 2
          Opened: Saturday, 24 September 2022, 12:00 AM
          Due: Monday, 26 September 2022, 12:00 AM

      • Quiz 2



        Quiz 2: 28th September 2022 (Face-to-Face)

           Topic:

        • Set
        • Set Operations
        • Functions

        • Week 7 (Rules of Inferences)



          RULES OF INFERENCES


          LESSON OBJECTIVE

          Lesson 13

          • In this lesson, a discussion on rules of inferences will be introduced

          Lesson 14

          • In this lesson, a discussion on rules of inferences will be continued


          LEARNING OUTCOME

          • After the lecture students will be able to learn why inferences is important in discrete mathematics and different operation of function.
          • They will learn about argument, conclusion, premises.
          • They will learn about rules of inferences.
          • They will learn about fallacies.
          • They will learn to build arguments.
          • They will learn about rules of inferences and quantifiers.
          DISCUSSION TOPICS

          • Rules of inferences
          • Argument, conclusion, premises
          • Fallacies
          • Building arguments
          • Addition and production of function
          • Composition of function
          • Inverse of function
          • Rules of inferences and quantifiers


          LECTURE VIDEO

            
            
          MORE LECTURE VIDEO FOR CLEAR IDEA

           

           


        • Week 8 (Mathematical Induction)



          MATHEMATICAL INDUCTION


          LESSON OBJECTIVE

          Lesson 15

          • In this lesson, a discussion on mathematical induction will be introduced

          Lesson 16

          • In this lesson, a discussion on mathematical induction will be continued


          LEARNING OUTCOME

          • After the lecture students will be able to learn why mathematical induction is important in discrete mathematics and different operation of function.
          • They will learn the rules and format of mathematical induction.
          • They will learn statement of problem.
          • They will learn principle of induction.
          DISCUSSION TOPICS

          • Mathematical induction
          • Statement of problem
          • Principle of induction
          • Example on induction
          • Validity of mathematical induction


          LECTURE VIDEO

              
              
          MORE LECTURE VIDEO FOR CLEAR IDEA
            
           

        • Mid-Term Examination



          The midterm syllabus for CSE131 Discrete Mathematics will be as follows:

          1. Propositional logic
          2. Logical equivalence
          3. Predicates and quantifiers
          4. Rules of inferences
          5. Set
          6. Set operations
          7. Function
          8. Mathematical induction

          • Week 9 (Graph, Graph Terminologies and Bipartite Graph)



            GRAPH, GRAPH TERMINOLOGIES AND BIPARTITE GRAPH


            LESSON OBJECTIVE

            Lesson 17

            • In this lesson, a discussion on graph will be introduced

            Lesson 18

            • In this lesson, a discussion on graph, graph terminologies and bipartite graph will be continued


            LEARNING OUTCOME

            • Able to understand the basics of Graphs
            • Able to represent natural phenomena into Graphs
            • Able to apply Handshaking Theorem
            • Able to classify Graphs
            • Able to identify Bipartite Graphs using coloring algorithm
            DISCUSSION TOPICS

            • Basic concept of Graph.
            • Converting natural phenomena into Graphs.
            • Types of basic Graphs.
            • Handshaking Theorem.


            LECTURE VIDEO

                
                
            MORE LECTURE VIDEO FOR CLEAR IDEA

          • Week 10 (Graph Isomorphism, Representing Graphs)



            GRAPH ISOMORPHISM, REPRESENTING GRAPHS


            LESSON OBJECTIVE

            Lesson 19

            • In this lesson, a discussion on graph isomorphism and representation of graphs will be introduced

            Lesson 20

            • In this lesson, a discussion on graph isomorphism and representation of graphs will be continued


            LEARNING OUTCOME

            • Able to understand the isomorphism of graph
            • Able to identify graphs isomorphism
            • Able to represent graphs using adjacency list, adjacency matrices
            • Able to represent graphs as incidence matrix
            DISCUSSION TOPICS

            • Basic concept of Graph Isomorphism.
            • Finding Isomorphism of Graphs.
            • Representing Graphs as Adjacency list and Adjacency matrices.
            • Representing Graphs as Incidence Matrix.


            LECTURE VIDEO

                 
                 
            MORE LECTURE VIDEO FOR CLEAR IDEA

          • Week 11 (Euler Path, Hamilton Path, Shortest Path Problem)



            EULER PATHS, HAMILTON PATHS, SHORTEST PATH PROBLEMS


            LESSON OBJECTIVE

            Lesson 21

            • In this lesson, a discussion on Euler path, Hamilton path and shortest path problems will be introduced

            Lesson 22

            • In this lesson, a discussion on Euler path, Hamilton path and shortest path problems will be continued


            LEARNING OUTCOME

            • Able to understand the Euler graph, Euler path and Euler circuit/cycle
            • Able to identify Euler graph 
            • Able to understand the Hamilton graph, Hamilton path and Hamilton circuit/cycle
            • Able to identify Hamilton graph
            • Able to understand shortest path problems
            • Able to apply Dijkstra's Algorithm and Floyd's Algorithm
            DISCUSSION TOPICS

            • Basic concept of Euler Graph and Hamilton Graph.
            • Finding Euler path and circuit as well as Hamilton path and circuit.
            • Basic concept of shortest path problems.
            • Applying Dijkstra's algorithm and Floyd's algorithm.


            LECTURE VIDEO

          • Quiz 3



            Quiz 3: 25th November 2022 (Online)

               Topic:

            • Graph, Graph Terminologies
            • Bipartite Graph
            • Isomorphism
            • Representation of Graph
            • Euler's Path, Hamilton's Path
            • Dijkstra and Floyd Algorithm

            • Quiz 3
              Opened: Friday, 25 November 2022, 8:00 PM
              Closed: Friday, 25 November 2022, 9:00 PM

              Date: 25th November, 2022

              Time: 40 Minutes


          • Week 12 (Tree, Spanning Tree, Minimum Spanning Tree)



            INTRODUCTION TO TREE, SPANNING TREE, MINIMUM SPANNING TREE


            LESSON OBJECTIVE

            Lesson 23

            • In this lesson, a discussion on Tree, spanning tree and minimum spanning trees problems will be introduced

            Lesson 24

            • In this lesson, a discussion on Tree, spanning tree and minimum spanning trees problems will be continued


            LEARNING OUTCOME

            • Able to understand the Tree, Forest and Properties of trees, Level and Height
            • Able to understand Rooted tree, Sub-tree, m-ary tree
            • Able to understand the basic of Spanning tree
            • Able to apply BFS and DFS and Backtracking
            • Able to understand Minimum spanning tree
            • Able to apply Prim's and Kruskal's algorithm
            DISCUSSION TOPICS

            • Basic concept of Tree, Forest and their properties
            • Applying BFS and DFS.
            • Basic concept of Spanning Tree and MST.
            • Applying Prim's and Kruskal's algorithm.


            LECTURE VIDEO

            MORE LECTURE VIDEO FOR CLEAR IDEA


          • Week 13 (Relations, Their Properties and Representations)



            RELATIONS, THIER PROPERTIES AND REPRESENTATIONS, CLOSURES OF RELATIONS AND PARTIAL ORDERINGS


            LESSON OBJECTIVE

            Lesson 25

            • In this lesson, a discussion on Relations, Their Properties and Representations, Closures of relations and Partial ordering will be introduced

            Lesson 26

            • In this lesson, a discussion on Relations, Their Properties and Representations, Closures of relations and Partial ordering will be continued


            LEARNING OUTCOME

            • Able to understand the basic of relation and their properties
            • Able to understand the basic of closures of relations
            • Able to understand the basic of partial ordering
            • Able to identify reflexive relation, symmetric relation, transitive relation, etc.
            • Able to construct Hasse Diagram
            DISCUSSION TOPICS

            • Basic concept of Relation and their properties
            • Basic concept of closures of relations
            • Basic concept of partial ordering
            • identifying Reflexive relation, Symmetric relation, Transitive relation, etc.
            • Constructing Hasse Diagram


            LECTURE VIDEO


            MORE LECTURE VIDEO FOR CLEAR IDEA


          • Assignment 3



            • Assignment 3
              Opened: Monday, 14 November 2022, 12:00 AM
              Due: Sunday, 20 November 2022, 12:00 AM

          • Presentation



            Submit your file in the given drive link asap.
            Date: 17 November 2022
            Topic: Computer Science related
            Duration: 10 Minutes
            Minimum 10 Slides.
            Please maintain proper dress code.

          • Final Examination



            The final syllabus for CSE131 Discrete Mathematics will be as follows:

            1. Graph terminologies and types

            2. Handshaking Theorem

            3. Bipartite Graph

            4. Representing Graphs

            5. Isomorphism

            6. Euler Circuit and path

            7. Shortest path

            8. Basic terminologies of Tree

            9. Minimum Spanning Tree (Prim's and Kruskal's algorithms)

            10. Relation, its properties and composition of relations

            11. Closures of Relation