Course Guide for

CMSC 57 Institute of Computer Science

Discrete Mathematical Structures in Computer Science II

About the Course

Welcome to CMSC 57, a continuation of the the two-course series on the discrete
mathematical structures for computer science. This course, together with CMSC 56
(Discrete Mathematical Structures in Computer Science I), essentially provides you
with the mathematical foundation necessary for the study of computer science. A lot
of concepts you will learn in other courses in the BS Computer Science curriculum
are based on what you will learn in this course. Although you may rarely see how
concepts on discrete mathematical structures are applied in computer science during
the course of the semester, be assured that you will soon discover the importance of
this course when you do take the rest of the computer science courses in the BSCS
curriculum.
Course Objectives
At the end of the course, the student should be able to
 apply principles/techniques in combinatorics to solve a given problem in counting;
 define the sample space, sample points and event space of a given random
experiment;
 apply the theory of probability to compute for the probability of a given event in
the context of a given random experiment; and
 explain the principles of algebraic systems; and
 apply the principles/techniques in graph theory on a given problem.
Prerequisites
In order to enroll in this course, you must have taken and passed CMSC 56 (Discrete
Mathematical Structures in Computer Science I). This means that by now you should
 be familiar with the basic concepts in logic, set theory, relations and functions
and matrix algebra (taken up in CMSC 56); and
 be familiar with the basics of algebra.
Course Materials
There will be two sets of handouts to be made available for the course.
 First is a set of handouts containing a list of all definitions of terms and
concepts discussed in the lecture. These will be given out during the lecture
class.
 Another is a set of lecture notes based on the lecture presentation slides will be
made available through the course website on Google Classroom.
More information and instructions will be given out later during the lecture
regarding how to access and make use of the course website as a supplement to the
course.
Course Outline
1 Combinatorics
1.1 Rules of Sum and Product
1.2 Indirect Method of Counting
1.3 Mutual Inclusion-Exclusion Principle
1.4 Two Models of Counting
1.5 Derangements

Institute of Comp Sci/UPLB CMSC 57 Course Guide/ Page 1 of 4

 1.6 Pigeonhole Principle Revisited
1.7 Recurrence Relations
2 Discrete Probability
2.1 Basic Concepts in Probability
2.2 Conditional Probability and Independent Events
2.3 Discrete Random Variables and Discrete Probability Distributions
3 Algebraic Systems
3.1 Algebraic Structures
3.2 Groups, Groupoids, and Semigroups
3.3 Cyclic Groups
4 Introduction to Graph Theory
4.1 Basic Concepts
4.1.1 Graph Terminology, Representations and Operations
4.1.2 Walks, Trails, Paths, Circuits, cycles
4.1.3 Special Types of Graphs
4.1.4 Trees
4.2 Some Graph Problems and their Applications
4.2.1 Minimum Spanning Tree
4.2.2 Traveling Salesman
4.2.3 Graph Matching
4.2.4 Colorability
References
 Grimaldi, R., Discrete and Combinatorial Mathematics: An Applied Introduction.
Addison-Wesley Publishing Company, Inc.
 Kolman, B. and R. Busby, Discrete Mathematical Structures for Computer
Science. Prentice-Hall International.
 Johnsonbaugh, R. Discrete Mathematics. MacMillan Publishing.
 Paterno, M. C. S. and E. A. Albacea. 2003. Discrete Mathematical Structures in
Computer Science Book 2. ICS, UPLB.
 Rosen, K. H. Discrete Mathematics and Its Applications. McGraw Hill.
Copies of the books listed above are available at the ICS Reading Room (Physical
Science Building C-126) or else you may borrow one of my own copies at my office
upon presentation of your student ID. The book by myself and Dr. Albacea is
unfortunately out of print but some students who have taken the course in the past
might still have a copy of the book that you may be able to borrow.
Class Schedule

Week # Topic Reference Activities

1-5 Combinatorics · Chapter 1; Paterno & Albacea Lab Exers 1 to 5
LONG EXAM # 1
6-9 Discrete Probability · Chapter 2; Paterno & Albacea Lab Exers 6 to 9
LONG EXAM # 2
10-12 Algebraic Systems · Chapter 3; Paterno & Albacea Lab Exer 10 to 11
13-16 Intro to Graph Theory · Chapter 4; Paterno & Albacea Lab Exers 12 to14
LONG EXAM # 3

Institute of Comp Sci/UPLB CMSC 57 Course Guide/ Page 2 of 4

 Course Requirements
Your final grade will be based on the following requirements:
10% Lecture Quizzes
25% Laboratory Exercises
45% Long exams
20% Final exam
 Quizzes given during the lecture will be announced and unannounced. I normally
give quizzes at the beginning of the lecture session so be sure to be on time for
the lecture class!
 You will be required to complete a set of laboratory exercises during the
laboratory sessions. The exercises involving solving problems in combinatorics,
probability, abstract algebra and graph theory. None of the exercises require the
use of a computer and simply require the use of pen and paper and a calculator to
compute for large products/sums. Note that while your laboratory instructor will
be solving sample problems during the laboratory session as illustrations on how
to apply the concepts learned in the lecture, you are expected to have studied
beforehand these concepts in preparation for your laboratory class.
 You will be required to take three(3) long exams. The coverage of each long
exam is indicated in the Course Schedule in the previous section of this Course
Guide. You will be given two(2) hours to answer each exam. Because of this, the
long exams will be scheduled outside class hours. I will be announcing the time
and venue of each exam during the lecture at least a week before the scheduled
date of the exam.
 The final exam will be given during the final exam week. The time and date of
the final exam will be set by the Office of the University Registrar. And, yes, you
can be exempted from taking the final exam! (See Class Policies below.)
 For your final grade, we shall be using the following grading scale:
Grade Standing Grade Standing
1.00 95-100 2.25 70-74
1.25 90-94 2.50 65-69
1.50 85-89 2.75 60-64
1.75 80-84 3.00 55-59
2.00 75-79 5.00 0-54
Class Policies
 Missed Long Exams
If you missed an exam, you should present an official excuse slip (from the Office
of the College Secretary) upon returning to class. You will then be given a make-
up exam as soon as possible. No excuse slip means you will obtain a zero for that
exam.
 Missed Lecture Quizzes
Policies concerning missed quizzes follow that for missed long exams. However,
you will not be given a make-up quiz; the missed quiz will simply be dropped
during the computation of the your final grade for the course.
 Exemption from the Final Exam
You will be exempted from the final examination if you satisfy all of the following:
• obtain a passing pre-final standing of 55% (Grade=3.00) or better; and
• did not miss an exam (unexcused).

Institute of Comp Sci/UPLB CMSC 57 Course Guide/ Page 3 of 4

 Course Attendance
Your attendance during the lecture will be checked every meeting.
If you incur at least seven(7) absences in the lecture or at least four(4) absences
in the laboratory class and majority of these absences are unexcused, you will
receive a grade of 5.0 for the course with the remark “Excessive unexcused
absences”. If, on the other hand, majority of these absences are excused you will
receive a grade of DRP with the remark “Excessive excused absences”.
 Policies for the Laboratory Classes
Policies on the conduct of lab session will be discussed during each lab class.
 Food & Drink Inside the Lecture Hall
Given the odd hours of the lecture class, you may eat and drink in the lecture hall
as long as you dispose of your litter properly and do not disturb your classmates.
 On Academic Integrity
Intellectual honesty is one of the most important values which this university
upholds. Therefore, as a student of the University of the Philippines, it is expected
that any work you submit for this course is your own. This means that cheating in
exercises, exams, plagiarism and other forms of intellectual dishonesty will not be
tolerated. It is said that each one of us has his own brilliant idea and therefore you
should not miss the chance of discovering yours.
If you are caught cheating in this course, the policy below will be followed:
• for the first offense, you will receive a score of zero for quiz/exam/exercise; and
• for the second offense, you will receive a final grade of 5.0 for the course.
As you can see, like any other faculty member or good student of the University of
the Philippines, I take academic integrity seriously. I hope that you will, too.
Contact Information and Consultation Hours
Who am I? My name is Margarita Carmen S. Paterno and I will be your lecturer
for this course during this semester. Students call me ma'am Margie or ma'am
Paterno. I am a faculty member of the Institute of Computer Science of the
University of the Philippines Los Baños and have handled undergraduate courses on
college algebra, elementary statistics, statistical packages, discrete mathematics,
data structures, operating systems, automata theory and information technology
literacy. I received my bachelors degree from this university and my masters
degrees from Iowa State University and the National University of Singapore.
How can you contact me? You can contact me via telephone (preferably during my
consultation hours--see below) or email:
Institute of Computer Science
University of the Philippines Los Baños
College, Laguna 4031
Telephone/Fax number: (049) 536-2302
E-mail: mspaterno@up.edu.ph
When and where can you consult me? You can see me at Room C-121 of the
PhySci Building for consultation during my consultation hours--unless, of course, I
am called away to attend a meeting or some other matter:
Tuesdays to Fridays: 9:00AM-11:30AM
If you are unable to come during these times, you may also see me by appointment.
Just let me know after class or else via email when you can come see me and I can let
you know if I will be free then.

Institute of Comp Sci/UPLB CMSC 57 Course Guide/ Page 4 of 4