Course: Discrete Mathematics : SEC- L (Fall 2022)

Topic outline

CSE131-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


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

Student Feedback

Additional Support and Library Resources for Students

Announcements Forum
Academic Calendar URL
Course Outline URL

Week 1 (Propositional Logic)
Week 1 (Propositional Logic)
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
Instiga Institute - YouTube
Week 2 (Propositional Equivalence)
Week 2 (Propositional Equivalence)
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 01
  
  Opened: Wednesday, 17 August 2022, 12:00 AM
  
  Due: Tuesday, 23 August 2022, 12:00 AM
Week 3 (Predicates and Quantifiers)
Week 3 (Predicates and Quantifiers)
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
Quiz 1: 11th September 2022 (Face-to-Face)
Topic:
- Propositional Logic
- Propositional Equivalence
- Predicates and Quantifiers
Week 4 (Sets)
Week 4 (Sets)
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
- Sets Lecture Slide File
- Weekly Discussion Forum
Week 5 (Set Operations)
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
- Set Operations Lecture Slide File
- Weekly Discussion Forum
Week 6 (Functions)
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
- Function Lecture Slide File
- Weekly Discussion Forum
Assignment 2
Assignment 2
- Assignment 2
  
  Opened: Saturday, 24 September 2022, 12:00 AM
  
  Due: Monday, 26 September 2022, 12:00 AM
Quiz 2
Quiz 2
Quiz 2: 27th September 2022 (Face-to-Face)
Topic:
- Set
- Set Operations
- Functions
Week 7 (Rules of Inferences)
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
- Rules of Inference Lecture Slide File
- Weekly Discussion (Answer following question) Forum
  
  Someone who lies is not trustworthy. All untrustworthy persons are bad friends. Whoever has the ability and helps in a bad time is a good friend. Therefore, someone who lies doesn’t help in a bad time.
  Verify whether the argument is valid or not?
Week 8 (Mathematical Induction)
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
- Mathematical Induction Lecture Slide File
- Weekly Discussion (Answer following question) Forum
  
  1. Let P (n) be the statement that 1³+ 2³ +···+ n³ = (n(n + 1)/2)² for the positive integer n.
  a) What is the statement P (1)?
  b) Show that P (1) is true, completing the basis step of the proof.
  c) What is the inductive hypothesis?
Mid-term Examination
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))
Week 9 (Graph, Graph Terminologies and Bipartite Graph))
GRAPH, GRAPH TERMINOLOGIES, 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)
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)
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

MORE LECTURE VIDEO FOR CLEAR IDEA
Quiz 3
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: 25^th November, 2022
  Time: 40 Minutes
Week 12 (Tree, Spanning Tree, Minimum Spanning Tree)
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)
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
- Assignment 3
  
  Opened: Monday, 14 November 2022, 12:00 AM
  
  Due: Sunday, 20 November 2022, 12:00 AM
Presentation
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.
- Upload Presentation File Here URL
- Group Details URL
Final Examination
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