COMSATS University Islamabad,

Sahiwal Campus

Course Outline & Lecture Plan

Discrete Structures
CSC 102

Department of Mathematics

Department of Mathematics
 Discrete Structures CSC- 102

A: Teacher and Course Information

Teacher Name: Shaheen Akhter E-mail: shaheen@cuisahiwal.edu.pk

Program: BS CS Semester: 2nd
Department: Mathematics COMSATS University Islamabad, Sahiwal
Campus

B: Course Description

Topics Covered:

Mathematical reasoning, Propositional and Predicate Logic, Nested Quantifiers, Rules of

Inference, Methods of Proofs Direct/ Indirect Proofs (Proof by Induction, Proof by
Contraposition, Proof by Contradiction, Proof by Implication), Set Theory, Functions,
Mappings, Function Composition, Inverse Functions, Recursive Functions, Relations,
Equivalence Relations and Partitions, Partial Orderings, Recurrence Relations, Closures of
Relations, Number Theory, Sequences, Series, Counting, Inclusion and Exclusion Principle,
Pigeonhole Principle, Permutations and Combinations, Graph: Elements of Graph Theory,
and Graph Isomorphism, Planar Graphs, Graph Coloring, Euler Graph, Hamiltonian Path,
Matrix Representation of Graphs, Applications of Trees, Tree Traversal.

Course Objectives:

The course provides a solid theoretical foundation of discrete structures as they apply to
Computer Science problems and structures. The students will learn how to use mathematical
notation and solve problems using mathematical tools. Discrete Structures develop the
quantitative skills necessary for continued success in computer science. These skills enhance
their ability to both analyze and describe mathematically many of the algorithms and data
structure performance characteristics common to computer science.

Department of Mathematics
 Discrete Structures CSC- 102
MTH- 493

Students Learning Outcomes:

After completion of this course the student will be able to

1. Distinguish between the notion of discrete and continuous mathematical structures.
2. Demonstrate an understanding of the basic concepts of set theory.
3. Apply fundamental counting algorithms to solve applied problems, particularly those
found in the area of computer science.
4. Prove mathematical statements by means of inductive reasoning.
5. Demonstrate an understanding of the principle of recursion and apply it to the study
of sequences and sets.
6. Apply the basic properties of graphs and trees and use these concepts to model
simple applications. Communicate mathematical ideas in both written and oral form
for a variety of audiences.

Textbook:
Discrete Mathematics and Its Applications, 7th Edition by Kenneth H. Rosen

Reference Book(s):
Discrete Mathematics with Applications, 4th Edition by Susanna S. Epp
Discrete Mathematics, 7th Edition by Richard Johnson Baugh

Department of Mathematics Page 3 of 7

Discrete Structures CSC- 102

C: Lecture-wise Activities
Week # Lecture # Topic Evaluation Remark
 Discrete versus Continuous
 Formal Logics
 Logic Form and Logic Equivalence
1
 Proposition Chapter 1
 Propositions & their Symbolic by Rosen
Representation
 The Negation of a Proposition
1
 Examples
 Compound Propositions
 Conjunction Students
 Disjunction are advised
2
 Tautologies to solve
 Contradictions some
 Contingencies exercise
 Truth Tables
 Conditional Statements
 The Contrapositive of a Conditional
Statement
 The Converse and Inverse of a
3 Chapter 1
Conditional Statement
by Rosen
2  Equivalence Proposition
 Bi-Conditional Statements
 Exclusive Or Propositions
 Bit Strings
4  Predicates and Quantified statements Chapter 1
 Example by Rosen
5  Proofs with the help of logical laws Chapter 1
 Exercises by Rosen
 Valid and Invalid arguments
3  Modes Ponens and Modus Tollens
6 Chapter 1
 Rules of Inference, Fallacies and Quiz #1
by Rosen
Contradiction, and Valid Arguments
 Examples
 Sets
 Union of Sets
7  Intersection of Sets Chapter 2
 Algebra of Sets by Rosen
4
 Properties of Sets
 Matrices
8  Proofs & Disproof’s by Venn Diagrams Chapter 2
 Proofs & Disproof’s by Set Properties by Rosen
 Rational Numbers
 Prime Numbers
9 Chapter 2
 Composite Numbers
5 by Rosen
 Divisibility
 Floor and Ceiling Function
10  Function Assignment#1 Chapter 2

Department of Mathematics
Discrete Structures CSC- 102
MTH- 493
 Types of Functions by Rosen
 Composition of Functions
 Relations and its Properties
11 Chapter 9
 N-ary Relations and its Applications
by Rosen
 Equivalence Relation
6
 Representation of Relations
Chapter 9
12  Closure of Relations
by Rosen
 Partial Order Relation
Chapter 1
13  Direct Proofs
by Rosen
 Indirect proofs
7
 Contrapositive Method Chapter 1
14 Assignment #2
 Contradiction Method by Rosen
 Disprove by Counter Examples
 Sequences
 Summation Notation
Chapter 2
15  Product Notation
8 by Rosen
 Related Problems
 General Results
16 Review Quiz# 2
17 Midterm Examination
 Mathematical Induction
9 Chapter 5
18  Proof by Mathematical Induction for
by Rosen
Equalities
 Mathematical Induction
Chapter 5
19  Proof by Mathematical Induction for by Rosen
Divisibility Problems
10
 Mathematical Induction
Chapter 5
20  Proof by Mathematical Induction for
by Rosen
Inequalities
 Mathematical Induction
Chapter 5
21  Proof by Mathematical Induction for
by Rosen
Recurrence Relation
11  Combinatorics
 Sum and Product Rule Chapter 6
22 Quiz# 3
 Permutations by Rosen
 Combinations
 Counting Techniques
Chapter 6
23  The Pigeonhole Principle Assignment #3
by Rosen
12  Inclusion Exclusion Principle
 Probability Chapter 7
24
 Laws of Probability by Rosen
 Probability Chapter 7
25
 Conditional Probability by Rosen
 Graphs
13
 The Handshaking Theorem Chapter 10
26
 Regular Graph, Complete Graph and by Rosen
Bipartite Graph
 Paths and Circuits Chapter 10
14 27 Quiz# 4
 Euler Circuits & Euler Path by Rosen

Department of Mathematics Page 5 of 7

Discrete Structures CSC- 102

 Hamiltonian Circuits
 Matrix representations of Graphs
 Adjacency Matrix of a Graph Chapter 10
28
 Adjacency Matrix of a Digraph by Rosen
 Incidence Matrix of a Simple Graph
Chapter 10
29  Isomorphisms of Graphs
by Rosen
15  Planar Graph
Chapter 10
30  Euler’s Formula Assignment #4
by Rosen
 Chromatic Number
 Trees
 Characterizing Trees Chapter 11
31
16  Kirchhoff’s Theorem by Rosen
 Traversals
32 Review =
17 Final Term Examination =

Prepared By Verified By Approved By

(Course Instructor) (Course Moderator) (Head of the Department)

Department of Mathematics