GRANBY COLLEGES OF SCIENCE AND TECHNOLOGY
College of Information and Communication Technology
Naic, cavite Philippines
Tel: (046) 412-0437
Subject: Discrete Structures
Subject Code: ITC2
Units: 3
Pre-requisite: ITC1-Introduction to Computing
Course Description
Discrete Structures is concerned with the application of objects with discrete
characteristics to computer science as a discipline in order that commonly used structures may
be described, characterized and analyzed. The course examines the fundamentals of
propositional logic and set operations, the analysis of algorithm complexity, mathematical
reasoning including proofs and induction, recursion, and program correctness. Graphs,
including Euler and Hamilton Paths and shortest path problems are examined, as are tree
applications. The course concludes with an investigation of Boolean functions, gate
representations and approaches to circuit minimization.
Learning Objectives
In this course, students learn:
To develop understanding of Logic Sets and Functions.
To use mathematical reasoning techniques including induction and recursion
To understand and apply counting techniques to the representation and characterization
of relational concepts.
To develop an understanding of how graph and tree concepts are used to solve problems
arising in the computer science.
To communicate the solutions of technical problems to other professionals.
To develop improved collaborative skills.
Course Outline
TEACHING AND
LEARNING OUTCOME BASE
TOPIC LEARNING
OUTCOMES ASSESSMENT
ACTIVITIES
After the completion of I. Orientation Discussion
the chapter, students A. Subject Small Group
will be able to: Guidelines Discussion
1. identify the and Policies Informal/Creative
course B. Class Policy Learning
description, C. Grading
content, System
requirements, D. Course
grading system Requirements
as well as class
policy.
After the completion of A. Logic, sets, and Lecture Quiz
the chapter, students functions. discussion Written
will be able to: 1. Logic Interactive activities
1. understand 2. Propositional learning
what logic is, equivalences Guided discovery
sets, and 3. Predicates and learning
1|Page
GRANBY COLLEGES OF SCIENCE AND TECHNOLOGY
College of Information and Communication Technology
Naic, cavite Philippines
Tel: (046) 412-0437
functions. quantifiers
2. solve different 4. Sets and set
problems using operations
set operations 5. Functions
After the completion of B. Algorithms, the Lecture Quiz
the chapter, students integers, and discussion Written
will be able to: matrices Interactive activities
1. identify 1. Algorithms and learning
different their complexity Guided discovery
integers and 2. The integers and learning
algorithms. division
2. Apply number 3. Integers and
theory in algorithms
solving 4. Applications of
problems. number theory
3. Understand 5. Matrices
matrices and
integer division
After the completion of C. Mathematical Lecture Quiz
the chapter, students reasoning discussion Written
will be able to: 1. Methods of proof Interactive activities
1. identify 2. Mathematical learning
different induction Guided discovery
methods of 3. Recursive learning
proof and algorithms
recursive 4. Program
algorithms. correctness
2. Understand
mathematical
induction and
program
correctness.
3. Apply the use of
proofs and
recursive
algorithms.
After the completion of D. Counting Lecture Quiz
the chapter, students 1. The pigeonhole discussion Written
will be able to: principle Interactive activities
1. use 2. Permutations and learning
mathematical combinations Guided discovery
reasoning 3. Discrete learning
techniques probability
including 4. Probability theory
induction and 5. Generalized
recursion. permutations and
combinations
6. Recurrence
relations
7. Generating
functions
2|Page
GRANBY COLLEGES OF SCIENCE AND TECHNOLOGY
College of Information and Communication Technology
Naic, cavite Philippines
Tel: (046) 412-0437
After the completion of E. Relations Lecture Quiz
the chapter, students 1. Relations and their discussion Written
will be able to: properties Interactive activities
1. understand and 2. N-ary relations learning
apply counting and their Guided discovery
techniques to applications learning
the 3. Representing
representation relations
and 4. Closures of
characterizatio relations
n of relational 5. Equivalence
concepts. relations
6. Partial orderings
After the completion of F. Graphs Lecture Quiz
the chapter, students 1. Graph terminology discussion Written
will be able to: 2. Representing Interactive activities
1. develop an graphs and graph learning
understanding isomorphism Guided discovery
of how graph 3. Connectivity learning
concepts are 4. Euler and
used to solve Hamilton paths
problems 5. Shortest path
arising in the problems
computer 6. Planar graphs
science. 7. Graph coloring
After the completion of G. Trees Lecture Quiz
the chapter, students 1. Introduction to discussion Written
will be able to: trees Interactive activities
1. develop an 2. Applications of learning
understanding trees Guided discovery
of how trees 3. Tree traversal learning
concepts are 4. Trees and sorting
used to solve 5. Spanning trees
problems 6. Minimum
arising in the spanning trees
computer
science.
After the completion of H. Boolean algebra Lecture Quiz
the chapter, students 1. Boolean functions discussion Written
will be able to: 2. Representing Interactive activities
1. identify Boolean functions learning
different 3. Logic gates Guided discovery
Boolean 4. Minimization of learning
functions and circuits
logic gates.
2. construct logic
gates
3. apply logic
gates in
minimization of
circuits.
3|Page
GRANBY COLLEGES OF SCIENCE AND TECHNOLOGY
College of Information and Communication Technology
Naic, cavite Philippines
Tel: (046) 412-0437
Assessment Strategy
LECTURE LABORATORY
QUIZ – 20% This course does not require a separate lab.
ASSIGNMENT – 10%
MIDTERM EXAM – 35%
FINAL EXAM – 35%
TOTAL = 100%
1.0 to- 5.0 SCALE PERCENTAGE
EQUIVALENT
1.00 99-100%
1.25 96-98%
1.50 93-95%
1.75 90-92%
2.00 87-89%
2.25 84-86%
2.50 81-83%
2.75 78-80%
3.00 75-77%
4.00 65-74%
5.00 FAILED
Satisfactory
Credited
Incomplete
Dropped
Withdrawn (Authorized)
Non-Credit
References:
Rosen, K. H. (1999) Discrete Mathematics. McGraw-Hill. ISBN 0-07-289905-0
Hall, C., & O’Donnell J. (2000) Discrete Mathematics Using a Computer, Springer Verlag
ISBN 1-85-233089-9
Balakrishnan, V.K. (1996). Introductory Discrete Mathematics, Dover ISBN 0-48-669115-2
Internet sources
4|Page
