International Islamic University, Islamabad
Fall 2022
Faculty of Computing
Department of Software Engineering
Course Information
Course Code & Course Title: Lab: No
CS102 – Discrete Structures Credit hrs: 3
Prerequisites For the Course: None
Instructor: Neelum Inam Course TA: None
E-mail : neeluminam@yahoo.com E-mail: None
Text Book:
1. Discrete Mathematics and its applications, Kenneth H Rosen, 7th Edition.
Reference Book:
1. Discrete Mathematics with Applications,Susanna Epp's, 4th Edition.
2. Discrete Mathematical Structures, Kolman, 4th Edition
Course Objectives:
Introduces the foundations of discrete mathematics as they apply to Computer Science,
focusing on providing a solid theoretical foundation for further work. Further, this course
aims to develop understanding and appreciation of the finite nature inherent in most
Computer Science problems and structures through study of combinatorial reasoning,
abstract algebra, iterative procedures, predicate calculus, tree and graph structures.
Educational Outcomes
Students will be able to:
1. Use logical notation to define and reason about fundamental mathematical
concepts such as sets, relations, functions, and integers.
2. Evaluate elementary mathematical arguments and identify
fallacious reasoning (not just fallacious conclusions).
3. Synthesize induction hypotheses and simple induction proofs.
4. Prove elementary properties of modular arithmetic and explain their applications
in Computer Science.
5. Apply graph theory models of data structures and state machines to solve
problems of connectivity and constraint satisfaction, for example, scheduling.
6. Problem solve and study in a small team with fellow students.
Course Outline
The purpose of this course is to understand and use discrete structures that are backbones of
computer science/software engineering. Later courses in the computer science/software
engineering curriculum build on the mathematical foundations covered here. In particular, this
class is meant to introduce logic, proofs, sets, relations, functions, mathematical induction,
recursion, graphs, trees and counting principles, with an emphasis on applications in computer
science/software engineering.
Tentative Lecture Plan:
Week Topic Activity
1. Introduction, Assignment 1
Course outline and class policies discussion
Logic
Introduction to logic, Propositions, Propositional Logic,
Conditional Statements, Converse, Contrapositive and
Inverse,
2. Logic(contd.) Assignment 1 Submission
Logic and Bit Operations, Proofs, Valid and Invalid
Arguments
Propositional Equivalences, Predicates
Truth tables, Constructing new Logical Equivalences,
Predicate Logic
3. Quantifiers Assignment 2
Predicate Calculus, Universal Quantifier, Existential Quiz1
Quantifier, Binding Variables, Negations, Translating from
English into Logical Expressions, Nested Quantifiers, Order
of Quantifiers, Translating Statements involving Nested
Quantifiers.
4. Rules of inference Assignment 2 Submission
Valid arguments, Proof by Contradiction
5. Generating Functions
6. Sets and Operations on Sets
Venn Diagram, Power Set, Cartesian Product, Using Set
Notation with Quantifier, Union, Intersection, Set identities,
Computer Representation of Sets.
7. Functions Quiz2
One to One Functions, Onto Functions, Bijection, Inverse
Functions, Compositions of Functions, Graph of Functions
Sequences and Summations
Arithmetic Progression, Special Integer Sequences,
Geometric Progression
8. Mid Term Examination
9. Mid Term Discussion
Basics of Counting
Basic Counting principles, Sum Rule, Product Rule
10. Counting Principles
Basic Counting principles, Sum Rule, Product Rule, The
Inclusive-Exclusive Principle,Tree diagrams,
11. Pigeonhole Principle Quiz3
Boxes Principle, Generalized Pigeonhole Principle,
Applications
Graphs
Terminology and special types of graphs, bipartite graph,
New Graph from Old
12. Relations Assignment 3
Function as relations, Relations on Set, Properties of
Relation, Combining Relations, Equivalence Relations,
Partial Ordering
13. Graph Coloring Assignment 3 Submission
Introduction, Application of Graph Coloring
14. Euler and Hamilton Paths
Euler Path and Circuits, Hamilton Path and Circuits
15.
Trees
Rooted Tree(m-ary tree),Ordered Rooted Tree, Trees as
Model, Properties of Tree, Tree Traversal
16. Revision
Grading and General Course Policies:
Assignments and/or grade percentages are subject to change. The breakdown is as follows:
Quizzes 15%
Assignments 5%
Mid Term 20%
Final____ _________________ 60%__
Total 100%
Students will submit all assignments individually.
Come prepare in every class for a surprise quiz.
You are responsible for timely and functional delivery of assignment to CR on submission date. Late
assignments will result in zero marks.
Assignments will be graded on the basis of adhering to requirements, robustness, analytical
reasoning/explanation, documentation, user-interface and above all originality.
No makeup quiz/exam/assignment will be taken.
Students are responsible to ensure that their attendance does not fall below specified limit.
