To operate the Blended Learning Center(BLC) at optimal level, maintenance will be performed every day at 8:30 AM and at 5:00 PM regularly which can take up to 30 minutes. Please consider scheduling your activity in the BLC platform accordingly.
Topic outline
- CSE131-Discrete Mathematics
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
Discrete Mathematics and Its Applications, 7/e, Kenneth Rosen, ISBN: 0072880082© 2007
- 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
- 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
- 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 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
- 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
- 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
- Assignment 2
- Quiz 2
Quiz 2
Quiz 2: 27th September 2022 (Face-to-Face)
Topic:
- 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
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
1. Let P (n) be the statement that 13+ 23 +···+ n3 = (n(n + 1)/2)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
- Euler's Path, Hamilton's Path
- Dijkstra and Floyd Algorithm
Date: 25th 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
- Presentation
Presentation
Submit your file in the given drive link asap.Date: 17 November 2022Topic: Computer Science relatedDuration: 10 MinutesMinimum 10 Slides.Please maintain proper dress code.
- 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