RIPHAH INTERNATIONAL COLLEGE
Associate Degree Program
Course Title : Discrete Mathematics
Course Number :
Credit Hours :3
Course Pre-requisite : Knowledge of Intermediate Calculus
Course Duration : 16 weeks
Course Objectives:
This course will help students to:
• Introduce students to the fundamental concepts of sets, functions, principal of mathematical
induction , binomial theorem, types of ordering and relations, permutation ,combination , trees
and graph theory
Learning Outcomes:
After studying this course, students should be able to:
• Operations on sets
• The principal of induction – Exclusion
• Mathematical Induction
• Special type of relations
• Ordering Relation
• Relational Databases
• Trees
• Introduction to graph theory
• Permutation and combinations
Violation of Academic Honesty Policy:
If any of the projects / assignments are identical or partially identical, a Zero will be awarded. The
repetition of such kind may lead to an “F” grade in the course.
General Classroom Norms:
Class attendance is mandatory. You may miss up to 25% (8 out of 32 sessions) class sessions but save
it for emergency only. In case you exceed this level, you will be withdrawn from the course. As a
courtesy to the instructor and other students, be prepared to arrive at class and be in your seat on time.
In addition, please note that each class lasts for 90 minutes (1.5 Hours).
Also keep in mind some general rules in the class as given below:
• Cell phones should be powered off.
• Eatables are not allowed in the class.
• The teacher will not tolerate any disruptive behavior in the class.
• The University Dress Code has to be observed, no warnings will be given, and violators will be
asked politely to leave the class and consequently will be marked absent.
Participation:
Students are required to attend all classes and read all the assigned material in advance of class
(although not necessarily with perfect comprehension). Advanced preparation and class participation
are crucial for periods in which we discuss cases. During discussion sessions, the instructor generally
keeps track of the insightful and useful comments students make. (Any unproductive contribution is
not rewarded)
Grade Distribution:
Evaluation Type Percentage (%) Activities
Quizzes 15 Minimum 4
Assignments 15 Minimum 4
Presentation 10 Minimum 1
Mid Term 30
Final Term 30
Total Points 100
Course Contents:
Week Contents Activities
01 Basic Definitions:
• Describing sets mathematically
• Relation between sets
• Venn diagrams
02-03 Operations on sets: Assignment 1
• Union and intersection
• Sets difference ,complements and
DeMorgan”s Law
• Power sets and products
• Lattices and Boolean Algebra
04 The principal of induction – Exclusion : Quiz 1
• Finite Cardinality
• principal of induction – Exclusion for
two sets
05-06 Mathematical Induction: Assignment 2
• A first form of induction
• Using strong form of Mathematical
Induction
• Algorithm to compute powers
• Binary Relations
• Introduction to propositions
07-08 Special type of relations: Quiz 2
• Reflexive and irreflexive relations
• Symmetric and Anti symmetric
Relations
• Transitive Relations
Ordering Relation:
• Partial ordering , Linear ordering
• Optimal elements in ordering
MID TERM
10-11 Relational Databases: Assignment 3
• Introduction of Relational database
• Storing information in relations
• Relational Algebra
Basic Definitions of Functions
• Functions as rules and functions as
sets
• Graphs of functions , Equality of
functions ,Restrictions of functions
• One to One and onto functions
• Increasing and decreasing functions
12-14 Trees Quiz 3
• Definitions of trees
• Characterization of trees
• Spanning Trees Presentation
• Kruskals trees algorithm
• Rooted Trees
• Binary trees Assignment 4
• Binary search trees
• Application of decision trees
Introduction to graph theory
• Definitions of graph
• Subgraph
• The handshaking problems
• Path and cycle
• Hamiltonian cycle
15-17 Permutation and combinations : Quiz 4
• Factorial and permutations
• Linear Permutation
• Circular Permutation
• Permutation with repetition
• Definition and formula of
combination
• Combination with repetition
• Pascal’s triangle
• Binomial theorems and its properties
FINAL TERM
Reference Book:
1. Discrete Mathematics for computer science by Gary Haggard, John Schlipf, and Sue Whiteside’s
2. Discrete Mathematics for computer science by Herbert Edelsbrunner and Brittany
