Discrete Mathematics

Teacher

Dr P HariKrishna

Category

Core Courses

Course Attendees

Still no participant

Course Reviews

Still no reviews

Course Name :Discrete Mathematics

 

 

Code(Credit) : CUTM1004(2-0-1)

Course Objectives:

To understand mathematical reasoning in order to read, comprehend and construct Mathematical arguments as well as to solve problems, occurred in the development of programming  languages.

To work with discrete structures such as graphs to study the structure of the world wide web, to model a computer network and to find the shortest path between two places in a transportation network.

Course Outcomes:

Upon successful completion of this course, the student will be able to:

 

COs Course Outcomes Mapping with COs with POs

(High-H, Low-L, Medium-M)

CO1 Apply Knowledge of mathematics in truth tables and the rules of propositional and predicate calculus PO1(M), PO2(H)
CO2 Apply the logical and analytical structure of proofs and work symbolically with connectives and quantifiers to produce logically valid, correct and clear arguments. PO1(H), PO2(H), PO3(L)
CO3 Solving elementary mathematical arguments and identify fallacious reasoning PO1(H), PO2(H)
CO4 Model and solve real-world problems using graphs, both quantitatively and qualitatively. PO1(H), PO2(H), PO5(H)

Course Syllabus

MODULE-I                                                                                                    (4Hours)

Propositional Logic, Connectives, Truth tables of compound propositions, Propositional Equivalence.

Project 1: Given the truth values of the propositions p and q, find the truth values of the conjunction, disjunction, implication, bi-implication, converse, contrapositive and inverse.

 

MODULE-II                                                                                                   (3Hours)

Theory of inference, Predicates and Quantifiers, Rules of Inference.

Project 2:Build valid arguments of a given set of propositional logics and quantified statements using rules of inferences.

 

MODULE-III                                                                                                  (3 Hours)

Relations and its properties, Partial Ordering, POSET, Totally Ordered Set.

Project 3:Define the properties of a relation on a set using the matrix representation of that relation with examples.

MODULE-IV                                                                                                  (3Hours)

Hasse Diagram, Maximal & Minimal Elements of a Poset, Greatest & Least Elements of a Poset, Supremum & Infimum of a Poset, Lattice.

Project 4: Find a Topological Sort of a Poset.

MODULE-V                                                                                                      (3 Hours)

Introduction to Graph Theory, Graph Terminology and Special types of Graphs, Representation of Graphs.

Project 5:Describe how some special types of graphs such as bipartite, complete bipartite graphs are used in Job Assignment, Model, Local Area Networks and Parallel Processing.

MODULE-VI                                                                                                    (3 Hours)

Graph Isomorphism, Connectivity, Euler and Hamiltonian Graphs, Planar Graphs, Graph Coloring.

Project 6(i):Describe the scheduling of semester examination at a University and Frequency Assignments using Graph Coloring with examples.  Find also their Chromatic numbers.

Project 6(ii):List out 10 pairs of Non-isomorphic graphs and explain the reason behind it.

Project 6(iii):List out all features ofEuler and Hamiltonian Graphs. Justify whether the given set of graphs are Euler and Hamiltonian. Construct a Gray Code where the code words are bit strings of length three.

MODULE-VII                                                                                                                (4  Hours)

Trees and their Properties, Spanning Trees, Minimum Spanning Trees, Kruskal’s Algorithm.

Project 7:Find a minimum spanning tree in a given weighted graph using Kruskal’s Algorithm.

Text Books:

  1. Discrete Mathematics and its Applications by K.H.Rosen, Publisher: TMH, Sixth Edition, 2009.  Chapters: 1(1.1 ,1.2,1.3, 1.5); 7(7.1,7.6); 8(8.1 to8.5, 8.7, 8.8);9(9.1,9.4,9.5)                                                                                                                                                                                                                                                          Reference Books:

  1. Discrete Mathematical Structures with Applications to Computer Science, J. P. Trembkay,Manohar, Tata MC Graw – Hill Edition 38th reprint, 2010.

  2. Discrete and Combinatorial Mathematics by R.P.Grimaldi Publisher: Pearson, 5th Edition, 2003.

  3. Discrete Mathematics and Applications by Thomas Koshy Publisher: Elsevier, 2004.

  4. Discrete Mathematical Structures by B. Kolman, R.C. Busby & S. Ross Publisher: PHI, 5th Edition, 2003.

Session Plan:1

Logic and Proofs (Mathematical Logic)

Propositional Logic:

https://youtu.be/p2b2Vb-cYCs

https://youtu.be/itrXYg41-V0

https://youtu.be/_RrxqiB_pfE

Session 2:

CONVERSE, INVERSE, AND CONTRA POSITIVE

SOME MORE CONNECTIVES

MODULE -I LOGIC-converted

https://youtu.be/3vqHz4dDGJk

Session 3:

Tautology and Contradiction, Logical Equivalence:

Equivalence Formulas: Other Connectives

video lecture link-https://youtu.be/HcS4lqXxrV4

Assignment 1 on Module 1: Construction of Truth Tables and Proving Logical Equivalences.

Assignment-1_Discrete_Math

Session 4:

Project 1: Given the truth values of the propositions p and q, find the truth values of the compound propositions.

Session 5:

Theory of Inference, Inference rules.

Session 6:

Theory of Interference, deriving conclusions, from the given premises.Theory of Inference-converted

https://youtu.be/NTSZMdGlo4g

Session 7: Predicates and Quantifies.

 

https://youtu.be/YMRO8i4-_q8

Session 8: predicate calculus by inference

Predicate Calculus-https://www.youtube.com/watch?v=qgJkBfcIE8A&t=378s

Assignment II : Deriving the valid conclusions from the given set of premises.

Assignment_2_Discrete_Math

Session 9: predicate calculus by inference

Project 2:Build valid arguments of a given set of propositional logics and quantified statements using rules of inferences.

Session 10:

Relations and Properties.

https://youtu.be/IQivwnECpYk

Session 11:

Representation of Relations,  Poset, totally ordered set.

 

https://youtu.be/qwArgnmbLC4

Session 12:

Assignment III.

Project 3:Define the properties of a relation on a set using the matrix representation of that relation with examples.

Session 13:

POSET, Construction of Hasse diagram.

https://youtu.be/Sy6dYKHDcnY

Assignment : Construction of Hasse diagrams with different posets.

Session 14:

Maximal & Minimal Elements of a Poset, Supremum & Infimum of a Poset.

https://youtu.be/fJ2tJgSMAA4

https://youtu.be/xu51YdEN1uc

Session 16:

Project 4: Find a Topological Sort of a Poset.

Session 17:

Introduction to Graph Theory, Graph Terminology.

https://youtu.be/g9U_kSjmmTI

https://youtu.be/ZsUwebrgJAc

https://youtu.be/pQfffi6XLjU

Session 20:

Project 5:Describe how some special types of graphs such as bipartite, complete bipartite graphs are used in Job Assignment, Model, Local Area Networks and Parallel Processing.

Session 21:

Graph Isomorphism, Planner graphs

https://youtu.be/Xq8o-z1DsUA

Session 23:

Project 6(i):Describe the scheduling of semester examination at a University and Frequency Assignments using Graph Coloring with examples.  Find also their Chromatic numbers.

Session 24:

Project 6(ii):List out 10 pairs of Non-isomorphic graphs and explain the reason behind it.

Session 25:

Project 6(iii):List out all features ofEuler and Hamiltonian Graphs. Justify whether the given set of graphs are Euler and Hamiltonian. Construct a Gray Code where the code words are bit strings of length three.

Session 26:

Trees and their Properties.

https://youtu.be/orKlYmj5AZY

Session 27:

Spanning Trees, Minimum Spanning Trees.

https://youtu.be/KkEz3qAkBtg

Session 28:

Kruskal’s Algorithm.

https://youtu.be/HtxN3v321HU

https://youtu.be/huQojf2tevI.

Assignment.

Session 29:

Project 7:Find a minimum spanning tree in a given weighted graph using Kruskal’s Algorithm.

Session 30:

Presentation by the students based on the assignment works  with different Applications.

Case Studies

Our Main Teachers

Dr P HariKrishna

Associate Professor
VIEW PROFILE

Working as Associate Professor of Mathematics CUTMAP Vizianagaram from July 2017 to Till Date. Awarded Ph.D in 2016 from Andhra University. Having an experience of 19 years in teaching and Research. Published 15 Papers in the area of Fixed point theory in National & International Journals.