Discrete Mathematics

Course Code (Credit):

FCBS0106(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.

Learning Outcomes:

  • Upon successful completion of this course, the student will be able to:
  • Apply the logical structure of proofs and work symbolically with connectives and quantifiers to produce logically valid, correct and clear arguments.
  • Evaluate elementary mathematical arguments and identify fallacious reasoning
  • Reformulate statements from common language to formal logic. Apply truth tables and the rules of propositional and predicate calculus.
  • Model and solve real-world problems using graphs, both quantitatively and qualitatively.

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: (3 Hours)

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(1): Describe the scheduling of semester examination at a University and Frequency Assignments using Graph Coloring with examples. Find also their Chromatic numbers.

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

Project 6(3): 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. iscrete 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:

Session Topic Reference Link (if any)
1 Logic and Proofs (Propositional Logic) Link 1
Link 2
Link 3 		-
2 Converse, Inverse, Contrapositive, Connectives Link -
3 Tautology, Contradiction, Logical Equivalence - Assignment 1: Truth Tables, Logical Equivalence
4 Project 1: Compound Propositions (Truth Values) - Project 1
5 Theory of Inference - -
6 Deriving Conclusions, Inference Theory Link -
7 Predicates and Quantifiers Link -
8 Predicate Calculus by Inference - Assignment II: Valid Conclusions from Premises
9 Predicate Calculus by Inference (continued) - Project 2: Build Valid Arguments
10 Relations and Properties Link -
11 Representation of Relations, Poset Link -
12 Assignment III - Project 3: Matrix Representation of Relation
13 POSET, Hasse Diagram Link Assignment: Hasse Diagrams
14 Maximal & Minimal, Supremum & Infimum Link 1
Link 2 		-
15 Lattices, Basic Properties - -
16 Project 4: Topological Sort of a POSET - Project 4
17 Intro to Graph Theory, Terminology Link 1
Link 2 		-
18 Special Types of Graphs - -
19 Graph Representation - Assignment V: Graph Identification
20 Project 5: Applications of Special Graphs - Project 5
21 Graph Isomorphism, Planar Graphs Link -
22 Connectivity, Euler & Hamilton, Coloring Link -
23 Project 6(i): Exam Scheduling via Coloring - Project 6(i)
24 Project 6(ii): Non-Isomorphic Graphs - Project 6(ii)
25 Project 6(iii): Euler/Hamilton Graphs, Gray Code - Project 6(iii)
26 Trees and Properties Link -
27 Spanning Trees, MST Link -
28 Kruskal’s Algorithm Link 1
Link 2 		Assignment
29 Project 7: MST using Kruskal’s Algorithm - Project 7
30 Presentation by Students - Final Presentations