International Islamic University Islamabad
Discrete Structure
Class: Semester:
Instructor: Office: Room 136,
Block C, IIU
Email:
Counseling Hours: TBA
Pre-requisites: None
Course Introduction to the mathematical foundations from discrete structures for
Description:
analysing computer algorithms, both for correctness and performance.
Focuses on the introduction to models of computation, including finite state
machines and Turing machines.
This course has been designed to provide students with a clear, accessible
Objectives:
introduction to discrete structures. Discrete Structure describes processes
that consist of a sequence of individual steps (as compared to calculus, which
describes processes that change in a continuous manner). The principal
topics presented in this course are logic and proof, Sets and Function,
sequences, algorithms, induction and recursion, relations, graphs, and trees.
As you progress through this course, you will develop the mathematical
foundations necessary for more specialized subjects in computer science,
including data structures, algorithms, and compiler design. Upon completion
of this course, you will have the mathematical know-how required for an in-
depth study of the science and technology of the computer age.
At the end of the course, the students are expected to:
Expected
Outcomes:
create compound statements, expressed in mathematical symbols or
in English, to determine the truth or falseness of compound
statements and to use the rules of inference to prove a conclusion
statement from hypothesis statements by applying the rules of
propositional and predicate calculus logic;
prove mathematical statements involving numbers by applying various
proof methods, which are based on the rules of inference from logic;
prove mathematical statements involving numbers by applying various
proof methods, which are based on the rules of inference from logic;
define and identify the terms, rules, and properties of set theory and
use these as tools to support problem solving and reasoning in
applications of logic, functions, number theory, sequences, counting,
probability, trees and graphs, and finite state machines;
solve recursive problems by applying knowledge of recursive
sequences;
create graphs and trees to represent and help prove or disprove
statements, to make decisions or select from alternative choices, to
calculate probabilities, to document derivation steps, or to solve
problems; and
Textbook:
Books:
Discrete Mathematics and Its Applications by Kenneth H. Rosen (Seventh
Edition), 2012.
Reference Books
Discrete Mathematical Structure with Application to Computer
Science, J. P. Temblay and B Manohar, McGraw-Hill, 2nd Edition.
Discrete Mathematics, 7 th edition, Richard Johnson Baugh, 2008,
Prentice Hall Publishers.
Discrete Mathematical Structures, 4th edition, Kolman, Busby & Ross,
2000, Prentice-Hall Publishers.
Discrete and Combinatorial Mathematics: An Applied Introduction,
Ralph P. Grimaldi, Addison-Wesley Pub. Co., 1985.
Logic and Discrete Mathematics: A Computer Science Perspective by
Winifred Grassman, Jean-Paul Tremblay, Winifred Grassman, Prentice
Hall, 1995
20 Mid Term Exam
Grading Policy:
60 Final Theory Exam
(Tentative) 20 Quizzes and Assignments
Quiz/ Quizzes:
Assignments Quizzes will be unannounced.
Policy They will be taken either in the first ten minutes of the class (so come
to the class on time & be prepared!) or in the last ten minutes of the
class (so listen to the lecture carefully).
If you miss a quiz, you miss it!
It’s up to the instructor’s discretion to choose the number of quizzes
for evaluation purposes.
Assignments:
Assignments need to be submitted on time. There will be 30% per day
deduction on late submissions
TBA
Plagiarism and Students indulging in any acts of the said offenses should be ready to bear
Cheating Policy grim consequences.
Student will present on given topics in the final week
Project Work
This course is comprised of the following units:
Course Contents Unit 1: Logic & Proofs
Unit 2: The Logic of Compound Statements
Unit 3: The Logic of Quantified Statements
Unit 4: Sets & Functions
Unit 5: Sequences, Sums, and Matrices
Unit 6: Algorithms
Unit 6: Introduction to Recursion
Unit 7: Mathematical Induction
Unit 8: Relations
Unit 9: Graphs
Unit 10: Trees
Unit 11: Boolean Algebra
Weekly Course Log
Week # Theory Lectures Signature
Week 1 Lecture 1 Introduction of discrete mathematics -
and 2 Need and Significance
identifying logical form, statements,
Compound Statements
Week 2 Lecture 1 Translating word statements to symbolic
notation. Venn diagram and set builder
notation.
Lecture 2 logical connectives, NOT, AND, OR, truth
table basics.
Week 3 Lecture 1 Conditional statements – implications,
biconditional, the negation of
conditional statements,
Lecture 2 Equivalence statements, contrapositive,
converse and inverse.
Week 4 Lecture 1,2 Equivalence Laws, Tautologies and
contradictions
Week 5 Lecture 1 Propositional functions and predicates
Lecture 2 Universal & existential quantifiers, Proof
by counter example, Nested quantifiers
Week 6 Lecture 1 Mathematical Reasoning, terminology,
proofs, rules of inference, arguments,
direct & indirect proofs with examples
Lecture 2 Set theory, operations, power set,
Cartesian product, set identities
Week 7 Lecture 1 Functions, domain, codomain, properties
of function, one-to-one, on-to, bijective
function, inversion, composition, floor &
Ceil functions
Week # Theory Lectures Signature
Lecture 2 Relations, relation on sets & Functions,
symmetric, asymmetric and
antisymmetric relations, Counting &
Combining relations
Week 8 Lecture 1, 2 n-ary relations, databases & relations,
representing relations using matrices &
digraphs, join & meet operations on
relations, equivalence relations &
classes.
MIDTERM EXAMINATION
Week 9 Lecture 1,2 Algorithms, pseudocode, linear search,
binary search, Complexity, growth
functions, Big – oh, intractable and
unsolvable problems
Week Lecture 1 Graphs: graph models, terminology,
10 special graphs, bipartite graph, cycles
and wheels
Lecture 2 Graph operations, and representation
using adjacency list and matrices, and
incidence matrices
Week Lecture 1 Graph Isomorphism, proof & disproof,
11 connectivity – strong & weak
connectivity
Lecture 2 Graph applications - shortest path
problem, Dijkstra’s Algorithm, Travelling
salesman problem
Week Lecture 1, 2 Boolean Algebra, operations, Boolean
12 functions & expressions, degree of
Boolean functions
Week # Theory Lectures Signature
Week Lecture 1,2 Duality principle, dual function, laws of
13 Boolean algebra, Applications of Boolean
algebra, logic gates, creating circuits of
different operations, Comparison with
logic & Sets
Week Lecture 1 Trees, tree as a model, rooted
14 and 2 terminology, m - ary tree, ordered
rooted, Levels of vertices and height
Week Lecture 1 Tree Traversal – in-order, preorder, and
15 and 2 prost-order traversal algorithms,
Trees & expression – infix, prefix and
postfix notation
Week Lecture 1 Spanning Trees – DFA, BFS, Backtracking
16 and 2 applications, DFS in directed graphs
