KEY TERMS & MAIN RESULTS – DISCRETE MATHEMATICS

Key terms Examples Exercises –

Do yourself
Chapter 1 – Logic & Proofs
Propositions Ex. Determine whether the proposition is 1/ Determine whether the
TRUE or FALSE. proposition is TRUE or
a/ 1 + 1 = 2 and 2 + 2 = 1. FALSE.
b/ 1 + 1 = 2 or 2 + 2 = 1 a/ 1 + 1 = 2 if and only if
c / 1 + 1 = 2 if and only if 2 + 2 = 1. pigs can fly.
d/ 1 + 1 = 2 if 2 + 2 = 1. b/ I am a superman if 1 +
e/ If it is snowing, then it is snowing. 1 = 2.
Solution. c/ If 1 + 1 = 2 or 1 + 1 =
a/ FALSE (T  F) 3 but not both, then I can
b/ TRUE (T  F) fly.
c/ FALSE (TF) d/ For every nonnegative
d/ TRUE (F T) integer, n, the value of n2
e/ TRUE (p  p) + n + 41 is prime.
Truth tables Ex. Write the truth table for the 2/ Construct the truth
proposition  r  q    p  r  . tables for the
Solution. propositions:
p q r  r  q    p  r  a/ (p  q)  (p  q)
b/  p  q   q   p
T T T T c/ p  r  q  p
d/ p  (q  p)
T T F T

T F T F

T F F T

F T T T

F T F F

F F T F

F F F F

Connectives / Ex. Let p and q be the propositions 3/ Let p, q, and r be the

Operations p : It is below freezing. propositions:
q : It is snowing. p :You get an A on the
 Write these propositions using p and q and final exam.
logical connectives (including negations). q :You do every exercise
a/ It is below freezing but not snowing. in this book.
b/ It is either snowing or below freezing (or r :You get an A in this
both). class.
c/ That it is below freezing is necessary and Write these propositions
sufficient for it to be snowing. using p, q, and r and
Solution. logical connectives
a/ p  q (including negations).
b/ p  q
c/ p  q a/ You get an A in this
class, but you do not do
every exercise in this
book.
b/ You get an A on the
final, you do every
exercise in this book, and
you get an A in this class.
c/ To get an A in this
class, it is necessary for
you to get an A on the
final.
d/ Getting an A on the
final and doing every
exercise in this book is
sufficient for getting an A
in this class.
Tautology Ex. Determine whether this proposition is a 4/ Determine whether
tautology:  p  q   q   p each of these propositions
is a tautology:
Solution.
a/ p  q  p
Truth table of  p  q   q   p :
b/ (p  q)  (q  p)
p q pq (pq)q (pq)q c/  p  q   p   q
 p
T T T F T d/ (p  p)  q.
T F F F T
F T T F T
F F T T T
  p  q   q   p is a tautology.
If-then Ex. Write each of these statements in the 5/ Write each of these
Necessary form “if p, then q” in English. statements in the form “if
Sufficient a/ To get a good grade it is necessary that p, then q” in English.
 you study. a/ It is necessary to walk
b/ Studying is sufficient for passing. 8 miles to get to the top
Solution. of
a/ If you get a good grade, then you study. Long’s Peak.
(Equivalently, if you don't study, then you b/ A sufficient condition
don't get a good grade.) for the warranty to be
b/ If you study, then you pass. good is that you bought
the computer less than a
year ago.
c/ I will remember to
send you the address only
if you send me an e-mail
message.
(Hint: “if p, then q” can
be written as “p only if
q”).
If and only if Ex. Write each of these propositions in the 6/ Write each of these
form “p if and only if q” in English. propositions in the form
a/ If it is hot outside, you buy an ice cream “p if and only if q” in
cone, and if you buy an ice cream cone, it is English.
hot outside. a/ If you read the
b/ For you to win the contest it is necessary newspaper every day, you
and sufficient that you have the only will be in formed, and
winning ticket. conversely.
c/ If you watch television, your mind will b/ For you to get an A in
decay, and conversely. this course, it is
Solution. necessary and sufficient
a/ It is hot outside if and only if you buy an that you learn how to
ice cream cone. solve discrete
b/ You win the contest if and only if you mathematics problems.
have the only winning ticket. c/ It rains if it is a
c/ Your mind will decay if and only if you weekend day, and it is a
watch television. weekend day if it rains.
Negation Ex. Find the negation of the propositions 7/ Find the negation of
a/ It is Thursday and it is cold. the propositions.
b/ I will go to the play or read a book. a/ If you study, then you
c/ If it is rainy, then we go to the movies. pass.
Solution. b/ Alex and Bob are
a/ It is not Thursday or it is not cold. absent.
(Keep in mind, p  q  p  q ) c/ He is young or strong.
b/ I won’t go to the play and I won’t read a
book.
 (Keep in mind, p  q  p  q )
c/ It is not rainy but we don’t go to the
movies.
(Keep in mind, p  q  p  q )
Equivalence Ex1. a/ Write a proposition equivalent to 8/ a/ Write a proposition
p  q that uses only p, q,  and the equivalent to p  q that
connective . uses only p, q,  and the
b/ Write a proposition equivalent to connective .

 p  q  p  q .  b/ Write a proposition
equivalent to
 
Solution.
 p  q  p  q .
a/ p  q  p  q  double negation 
c/ Write a proposition
 pq  pq (see De Morgan's laws) equivalent to (p  q)
So, p  q    p  q  .  (p  q).

  
b/  p  q   p  q  p  q  p  q    9/ Determine whether two

 p qq  (distributive law) propositions are
equivalent.
 p  T  a/ p  q and q  p
 p. b/  p  q  r  and
(Keep in mind, p  q  p  q )  p  q   p  r 
c/ p  q and q  q
Ex2. Determine whether two propositions
are equivalent.
a/ p  q and p  q
b/  p  q  r  and  p  q    p  r 
Solution.
a/ Use a truth table

p q pq p  q
T T T T
T F F T
F T T F
F F T T
 NOT EQUIVALENT.
b/ Starting from the right-hand side,
  p  q   p  r    p  q   p  r 
 pq pr
 
 p p qr (commutative and associative laws)
 pqr (idempotent law)
 p  q  r  (associative law)
 p  q  r 
 EQUIVALENT.
Predicates Ex1. What is the truth values of these 10/ What is the truth
Quantifiers propositions? (the domain for variable x is values of these
{-3, -2, -1, 0, 1, 2}) propositions? (the domain
a/ x  x  1  x 2  1 for variable x is the set of
all real numbers.)
b/ x  x  1  x 2  1
a/ x  x  1  x 2  1
c/ x  x  1  x 2  1
b/ x  x  1  x 2  1
Solution.
a/ FALSE (counter example: x = -2) c/ x  x  1  x 2  1
b/ FALSE (counter example: x = 0)
c/ TRUE (no counter example) 11/ Suppose P(x, y) is a
predicate and the universe
Ex2. Suppose P(x, y) is a predicate and the for the variables x and y
universe for the variables x and y is {1, 2, is {1, 2, 3}.
3}. Suppose P(1,3), P(2,1),
Suppose P(1, 3), P(2, 1), P(2, 2), P(2, 3), P(2,2), P(2, 3), P(2, 3),
P(2, 3), P(3, 1), P(3, 2) are true, and P(x, y) P(3, 1), P(3, 2) are true,
is false otherwise. and P(x, y) is false
Determine whether the following otherwise.
statements are true. Determine whether the
a/ xyP  x, y  following statements are
true.
b/ yxP  x, y 
a/ yxP  x, y 
c/ xy  P  x, y   P  y, x  
b/
Solution. yx  P  x, y   P  y, x  
a/ TRUE (we can see P(1, 3), P(2, 2), P(3,
2) are true  for each x in {1, 2, 3}, there
is at least one y in {1, 2, 3}.) 12/ Find a negation of
b/ FALSE (we can see that no y in {1, 2, 3} each of these statements:
for all x in {1, 2, 3}, details are in below: a/ x(P(x)  Q(x))
b/ x(P(x)  Q(x))
• y = 1: P(2, 1), P(3, 1) are true only
c/ xy(P(x, y)  Q(x,
(true with x = 2, 3, all x in {1, 2, 3}).
y)
• y = 2: P(2, 2), P(3, 2) are true only.
d/ xR(x < 2  x2 < 4)
 • y = 3: P(1, 3), P(2, 3) are true only.
c/ TRUE
• x = 1: P(1, 3)  P(3, 1)
• x = 2: P(2, 2)  P(2, 2)
• x = 3: P(3, 1)  P(1, 3)

Ex3. Find the negation of each of these

statements.
a/
b/
c/
Translation Ex. Suppose the variable x represents 13/ Suppose the variable
students and y represents courses, and: x represents students and
• A(y): y is an advanced course y represents courses, and:
• M(y): y is a math course • A(y): y is an
• F(x): x is a freshman advanced course
• B(x): x is a full-time student • M(y): y is a math
• T(x, y): student x is taking course y. course
Write these statements using these • F(x): x is a
predicates and any needed quantifiers. freshman
a/ Linh is taking MAD101. • B(x): x is a full-
b/ No math course is an advanced course. time student
c/ Every freshman is a full-time student. • T(x, y): student x is
d/ There is at least one course that every taking course y.
full-time student is taking. Write these statements
Solution. using these predicates and
a/ T(Linh, MAD101) any needed quantifiers.

b/ y M  y   A  y   a/ Nam is taking a math
course.
or equivalently, y  M  y   A  y   b/ There are some
c/ x  F  x   B  x   freshmen who are not
taking any course.
d/ yx  B  x   T  x, y   . c/ There are some full-
time students who are not
taking any advanced
course.
Arguments Ex. Determine whether the following 14/ Determine whether
Valid/invalid argument is valid. the following argument is
Rules of “Rainy days make gardens grow. Gardens valid.
inference don't grow if it is not hot. It always rains on Dong is an AI Major or a
a day that is not hot. CS Major but not both. If
Therefore, if it is not hot, then it is hot.” he does not know discrete
 Solution. math, he is not an AI
Consider the statements: Major. If he knows
r : it a rainy day discrete math, he is smart.
g: gardens grow He is not a CS Major.
h: it is hot Therefore, he is smart.
Then,
• Rainy days make gardens grow can
be written as “r  g” (1)
• “Gardens don't grow if it is not hot”
is denoted by “h  g” (2)
• “It always rains on a day that is not
hot” becomes “h  r” (3)
From (3), h  r and from (1), r  g. So,
h  g (4) can be drawn.
From (2), h  g, this is equivalent to g 
h (5).
From (4) and (5), h  g and g  h, we
can conclude that h  h, or in words “if it
is not hot, then it is hot”.
 VALID ARGUMENT.
Applications.
1. Logic Circuits. (readings – pages ____)
Find the output of each of these combinatorial circuits.

2. The goal of this exercise is to translate some assertions about binary strings into
logic notation.
• The domain of discourse is the set of all finite-length binary strings: , 0, 1, 00, 01,
10, 11, 000, 001, . . . . (Here  denotes the empty string.)
• Consider a string like 10x1y, if the value of x is 110 and the value of y is 11, then
the value of 10x1y is the binary string 10110111.
• Here are some examples of formulas and their English translations. Names for
these predicates are listed in the third column so that you can reuse them in your
solutions (as I do in the definition of the predicate NO-1S below).
 a) x consists of three copies of some string.
b) x is an even-length string of 0’s.
x does not contain both a 0 and a 1.
Chapter 2 – sets, sequences, sums
Sets Ex1. Determine whether each of these 15/ Determine whether
statements is true or false. each of these statements
Elements a/ 2 {2,{2}}. is true or false.
b/ 2 {{2},{{2}}}. a/ 2  {{{2}}}.
Empty set c/   {0}. b/ 2  {{2},{2,{2}}}.
d/  {, {}}. c/  {x}.
Subsets e/  ⊆ {0}. d/  {x}.
Solution.
a/ True
b/ False
c/ False
d/ True
e/ True
Cardinality of Ex. What is the cardinality of each of these 16/ What is the
a set sets? cardinality of each of
a/ {a, {a}}. these sets?
b/ {, a, {a, {a}}}. a/ {, {}}.
Solution. b/ { {a, {a}, b} }.
a/ |{a, {a}}| = 2.
b/ |{, a, {a, {a}}}| = 3.
Power set The power set of a set A, denoted by P(A), 17/ Determine whether
is the set of all subsets of A. each of these sets is the
For example, if A = {1, 2}, then the power power set of a set?
set of A is the set P(A) = {, {1}, {2}, {1, a/ .
2}}. b/ {}.
If A contains n elements, P(A) contains 2n c/ {, {a}, {}}.
elements. d/ {, {{1}}, {2}, {{1},
2}}.
Ex1. Determine whether each of these sets
is the power set of a set, where a and b are 18/ How many elements
distinct elements. does each of these sets
a/ {, {a}} have?
 b/ {, {a}, {,a}} a/ P({, {a}}) .
c/ {, {a}, {b}, {a, b}} b/ P({a, {a}, {a, {a}}}).
Solution. c/ P(P({})).
a/ {, {a}} is the power set of the set {a}.
b/ {, {a}, {,a}} cannot be a power set of
any set.
c/ {, {a}, {b}, {a, b}} is the power set of
the set {a, b}.

Ex2. How many elements does each of

these sets have?
a/ P({a, {a}})
b/ P({, a, {a}, {{a}}})
c/ P(P())
Solution.
a/ |{a, {a}}| = 2  | P({a, {a}})| = 22 = 4.
b/ |{, a, {a}, {{a}}}| = 4
 |P({, a, {a}, {{a}}})| = 24 = 16.
c/ || = 0  |P()| = 20 = 1  | P(P())| =
21 = 2
Union  Ex1. Prove that, for all sets A, B: 19/ Show that if A and B
a/ A  B  A  B are sets with A  B, then
Intersection  b/ A – B  A. a/ A  B = B.
c/ A = (A – B)  (A  B) b/ A  B = A.
Difference – Solution. c/ A  B  A.
a/ We use a membership table: d/ A  B = B – A.
Symmetric A B B A–B A B e/ B  A .
difference  1 1 0 0 0
1 0 1 1 1 20/ Find the sets A and B
Complement 0 1 0 0 0 if A  B and A  B = {1,
0 0 1 0 0 3, 4, 5, 7, 9}, and A  B
Based on the agreement of two latest = {3, 4, 7}.
columns, an element belongs to A – B if
and only if it belongs to A  B . 21/ Find the sets A and B
So, A  B  A  B . if A − B ={2, 3, 5, 7}, B
b/ Membership table: − A = {1, 4}, and A ∩ B
A B A–B A ={8, 6}.
1 1 0 1
1 0 1 1
0 1 0 0
0 0 0 0
 From the table, if an element belongs to A –
B (the corresponding number is 1), then it
also belongs to A (the corresponding
number is also 1).

Ex2. Find the sets A and B if A − B ={1, 5,

7, 8}, B − A = {2, 10}, and A ∩ B ={3, 6,
9}.
Solution.
From Ex1 (c):
• A = (A – B)  (AB) = {1, 5, 7, 8,
3, 6, 9}
• B = (B – A)  (AB) = {2, 10, 3, 6,
9}.
AB Ex. Given the sets C = {red; blue; yellow} 22/ Given the sets A = {0,
and S = {small, medium, large}. 1}.
a/ Construct Cartesian product CS. a/ Construct the set AA.
b/ What is the cardinality of the set CS ? b/ Find the complement
How many subsets does CS have? of the set {(0, 1)} in
Solution. AA.
a/ CS = {(red, small), (red, medium), (red, c/ What is the cardinality
large), (blue, small), (blue, medium), (blue, of the set AA? List all
large), (yellow, small), (yellow, medium), subsets of AA.
(yellow, large)}.
b/ |CS | = 33 = 9  AB has 29 subsets.
Set Ex1. Let U = {a, b, c, d, e, f, g} be the 23/ Suppose that the
representation universal set. Find the bit string universal set is U ={1, 2,
representing the subset A = {a, c, d, g}. 3, 4, 5, 6, 7, 8}. Express
Solution. each of these sets with bit
U a b c d e f g strings.
U 1 1 1 1 1 1 1 a/ {3, 4, 5}
A 1 0 1 1 0 0 1 b/ {1, 3, 6, 8}
c/ {1, 2, 3, 5}  {2, 3, 4,
Ex2. Let U = {1, 2, 3, 4, 5, 6, 7, 8}. 6, 7}
Given the subsets A = {1, 2, 3, 5, 7}, B =
{2, 4, 5}. Find the bit string representing 24/ Let U = {a, b, c, d, e,
the subset A – B. f, g} be the universal set.
Solution. Suppose A and B are sets
U 1 2 3 4 5 6 7 8 given by bit strings
A 1 1 1 0 1 0 1 0 1010101 and 1100111.
B 0 1 0 1 1 0 0 0 List all elements in the set
A- 1 0 1 0 0 0 1 0 A B .
 B
functions Ex1. Determine which rules are functions. 25/ Determine which
a/ f: Z  Z; f(x) = 1/(2x-1) rules are functions.
b/ f: Z  R; f(x) = 1/(2x-1) a/ f: Z  Z; f(x) = 1/(x2 -
c/ f: R  R; f(x) = 1/(2x-1) 2)
Solution. b/ f: Z  R; f(x) = 1/(x2-
a/ f: Z  Z; f(x) = 1/(2x-1) 2)
This rule is not a function, because f(2) = c/ f: R  R; f(x) = 1/(x2-
1/3 does not belong to the set Z (the set of 2)
integers).
b/ f: Z  R; f(x) = 1/(2x-1) 26/ Determine whether f
This rule is a function, we determine is a function from the set
exactly one output value for every input of all bit strings to the set
value. of integers if f(S) is the
c/ f: R  R; f(x) = 1/(2x-1) number of 0 bits in S.
This rule is not a function because f(1/2) is
not defined. 27/ Let R be the set {(a,
b) | a - 1 = b or b - 1 = a},
Ex2. Determine whether f is a function where a and b are in {-2,
from the set of all bit strings to the set of -1, 0, 1, 2}.
integers if f(S) is the position of a 0 bit in a/ List all ordered pairs of
S. R.
Solution. b/ Is R a function?
Consider the string S = “10011” as an input, Explain your answer.
f(S) = the position of a 0 bit in S 
f(10011) can be 2 or 3  f is NOT a
function.
One-to-one Ex1. a/ Determine whether the function 28a/ Determine whether
from N = {0, 1, 2, …} to N is one-to-one. the function from f(n) =
Onto a/ f(n) = (n – 1) 2
(n + 1)2 N = {0, 1, 2, …}
b/ Determine whether the function from Z = to N is one-to-one.
Bijection {…, -2, -1, 0, 1, 2, …} to N = {0, 1, 2, …} b/ Determine whether the
is one-to-one. function from Z = {…, -
Inverse 2n if n < 0 2, -1, 0, 1, 2, …} to N =
f  n  
functions (f-1) 2n+1 if n  0 {0, 1, 2, …} is one-to-
Solution. one.
Invertible a/ f(2) = f(0) = 1  f is not one-to-one. n2 if n < 0
f  n  
b/ 2n if n  0
• If n, m are different negative integers 29/ Determine whether
 f(n)  f(m) because f(n) = -2n  - the function f from the set
2m = f(m). of all bit strings to the set
• If n, m are different non-negative of integers is one-to-one
 integers  f(n)  f(m) because 2n+1 if f(S) is the number of 0
 2m + 1. bits in S.
• If n is negative and m is non-
negative  f(n) = -2n (even) and 30a/ Determine whether
f(m) = 2m + 1 (odd)  f(n)  f(m) the function from f(n) =
 nm  n  m  f  n   f  m  (n + 1)2 N = {0, 1, 2, …}
to N is onto.
 f is one-to-one. b/ Determine whether the
function from N = {0, 1,
Ex2. Determine whether the function f from 2, …} to Z = {…, -2, -1,
the set of all bit strings to the set of integers 0, 1, 2, …} is onto
is one-to-one if f(S) is the number of 1 bits
n / 2 if n is even
in S. f  n  
Solution. -(n+1)/2 if n is odd
f(01011) = f(1110) = 3  f is not one-to-
one. 31a/ List all functions
from {, } to {SHOOT,
Ex3. a/ Determine whether the function f(n) PASS, SPRINT}.
= (n – 1)2 from N = {0, 1, 2, …} to N is b/ List all one-to-one
onto. functions from {, } to
b/ Determine whether the function from Z = {SHOOT, PASS,
{…, -2, -1, 0, 1, 2, …} to N = {0, 1, 2, …} SPRINT}.
is onto. c/ List all onto functions
2n if n < 0 from {, } to {SHOOT,
f  n   PASS, SPRINT}.
 2n+1 if n  0
Solution.
32/ Determine whether
a/ Because f(n) = (n-1)2  2 for all values of each of these functions is
n  f is not onto. a bijection from R to R.
b/ Because f(n)  0 for all n  f is not onto. In case f is a bijection,
find the inverse function
Ex4. Determine whether each of these f-1.
functions is a bijection from R to R. In case a/ f(x) = 2x − 5
f is a bijection, find the inverse function f-1. b/ f(x) = (x – 3)(x + 1)
a/ f(x) = −3x + 4
b/ f(x) = −3x2 + 7
Solution.
a/ For every y in R, we can find exactly one
x in R such that y = −3x + 4. In this case, x
= (y – 4)/(-3).
And the inverse function is f-1(y) = (y –
4)/(-3).

b/ For some y in R, we cannot find x (or can

 find more than one values of x) in R such
that y = -3x + 4. For example, no value of x
in R such that 10 = -3x2 + 7 or 1 = -x2.
 f is not a bijection.
Composite Ex1. Find fg and gf, where f(x) = x2 + 1 33/ Find fg and gf,
function and g(x) = x + 2, are functions from R to R. where f(x) = 2x + 1 and
Solution. g(x) = 1 – x3, are
• (fg)(x) = f(g(x)) = f(x+2) = (x+2)2 functions from R to R.
+1
• (gf)(x) = g(f(x)) = g(x2 + 1) = (x2 + 34/ Let g = {(1, c); (2, b);
1) + 2 = x2 + 3. (3, a)} be a function from
Ex2. Let f = {(a, 1); (b, 3); (c, 2)} be a {1, 2, 3} to {a, b, c}.
function from {a, b, c} to {1, 2, 3}. a/ Find g-1.
a/ Find f-1. b/ Find gg-1 and g-1g.
b/ Find ff-1 and f-1f.
Solution.
a/ f-1 = {(1, a); (3, b); (2, c)}
b/ ff-1 = {(1, 1); (2, 2); (3, 3)}
and f-1f = {(a, a); (b, b); (c, c)}.
Sequences Ex1. List the first 6 terms of each of these 35/ List the first 6 terms
sequences. of each of these
a/ the sequence that lists each positive sequences.
integer three a/ the sequence whose nth
times, in increasing order term is the sum of the
b/ the sequence whose nth term is 2n – n2 first n
c/ the sequence whose first term is 2, second odd positive integers
term is 4, and each succeeding term is the b/ the sequence whose nth
sum of the two previous terms. term is n! − 2n
Solution. c/ the sequence whose
a/ 111, 222, 333, 444, 555, 666 first two terms are 1 and 5
b/ 1, 0, -1, 0, 7, 28 and each succeeding term
c/ 2, 4, 6, 10, 16, 26 is the sum of the two
previous terms.
Ex2. Find the first four terms of the
sequence defined by each of these 36/ Find the first four
recurrence relations and initial conditions. terms of the sequence
a/ an = −2an−1, a0 = −1 defined by each of these
b/ an = an−1 − an−2, a0 = 2, a1 = −1 recurrence relations and
c/ an = an−1, a0 = 5. initial conditions.
Solution. a/ an = −an−1, a0 = 5
a/ a0 = -1 b/ an = an−1 − n, a0 = 4
a1 = -2a0 = -2.(-1) = 2 c/ an = an-2, a0 = 3, a1 = 5
 a2 = -2a1 = -2(2) = -4
a3 = -2a2 = -2(-4) = 8
b/ a0 = 2, a1 = -1
a2 = a1 – a0 = -1 – 2 = -3
a3 = a2 – a1 = -3 – (-1) = -2
c/ a0 = 5
a1 = a 0 = 5
a2 = a 1 = 5
a3 = a 2 = 5
Special sums Special sum: 37/ Find the value of each
n
n  n  1 of these (double) sums.
 i  1  2  3  ...  n  20
i 1 2 a/ k
Ex1. Find the value of each of these sums. k 10
10 7
a/  i b/   2k  1
k 1
i 1
10 3 2
b/ 3 c/   2i  j 
i 1 j  0
i1
10 3 2
c/   i  3
i 1
d/  j
i 1 j  0
10 10 20
d/   3i  1
i 1
e/   i  j 
i 1 j 1
Solution.
10
10 10  1
a/ i 
i 1 2
 55
10
b/  3  3  3  ...  3  3 10  30
i1
10 10 10
c/   i  3   i   3  55  30  85
i 1 i 1 i 1

d/
10 10 10

  3i  1    3i   1
i 1 i 1 i 1
10
 3 i  10
i 1

 3  55  10
 175

Ex2. Compute each of these double sums.

2 3
a/   i  j 
i  0 j 1
 3 4
b/  i
i 1 j 1
20 30
c/   i  j 
i 1 j 1

Solution.
a/
2 3

  i  j  
i  0 j 1

 0  1   0  2    0  3 // i = 0
 1  1  1  2   1  3 // i = 1
+  2  1   2  2    2  3 //i = 3
= 27
b/
3 4

 i 
i 1 j 1

1  1  1 + 1 // i = 1
+ 2 + 2 + 2 + 2 // i = 2
+ 3 + 3 + 3 + 3 // i = 3
= 24
20 30
c/   i  j  
i 1 j 1
30

j
j 1
// i = 1

30
+  2 j  // i = 2
j 1
30
+  3 j  // i = 3
j 1

...
30
+  20 j  // i = 20
j 1
30
= 1  2  3  ...  20   j
j 1

20  20  1 30  30  1
 
2 2
= 97650
Chapter 3 – Algorithms & Integers
Algorithms Ex1. List all the steps used to search for 9 38/ List all the steps used
in the sequence 2, 3, 4, 5, 6, 8, 9, 11 using a to search for 8 in the
linear search. How many comparisons sequence 3, 5, 6, 8, 9, 11,
required to search for 9 in the sequence? 13, 14 using a binary
Solution. search. How many
Below is the linear search algorithm in comparisons required to
pseudocode search for 8 in the
procedure linear search(x: integer, a1, a2,..., sequence?
an: distinct integers)
i := 1 39/ Josephus problem.
while (i ≤ n and x = ai ) This problem is based on
i := i + 1 an account by the
if i ≤ n then location := i historian Flavius
else location := 0 Josephus, who was part
return location{location is the subscript of of a band of 41 Jewish
the term that equals x, or is 0 if x is not rebels trapped in a cave
found} by the Romans during the
All the steps used to search for 9 using a Jewish Roman war of the
linear search: first century. The rebels
i=1 preferred suicide to
(1 ≤ 8 and 9  2)  i:=i+1 = 2 capture; they decided to
i=2 form a circle and to
(2 ≤ 8 and 9  3)  i:= i+1 = 3 repeatedly count off
i=3 around the circle, killing
(3 ≤ 8 and 9  4)  i:= i+1 = 4 every third rebel left
i=4 alive.
(4 ≤ 8 and 9  5)  i:= i+1 = 5 However, Josephus and
i=5 another rebel did not
(5 ≤ 8 and 9  6)  i:= i+1 = 6 want to be killed this
i=6 way; they determined the
(6 ≤ 8 and 9  8)  i:= i+1 = 7 positions where they
i=7 should stand to be the last
two rebels remaining
(7 ≤ 8 and 9  9) // the condition is false
alive.
7 ≤ 9  location = 7.
Devise an algorithm to
determine the alive
Based on the steps above, there are 15
positions if the number of
comparisons (, ) required.
rebels is n and an alive
rebel will be killed after
counting to k (k < n).
Big-O Ex1. In the table below, check ✓if the fact 40/ Determine whether
Big-Omega is true and check  otherwise. each of these functions is
Big-theta function = O(x2) = (x2) = (x2) O(x2).
 2x + 11 a/ f(x) = 3x + 7.
x2 + 3x + b/ f(x) = log(x3) + 2x.
1 c/ f(x) = (2x3 + x2 log
x2logx + x)/(x+2).
2018 d/ f(x) = 2x + 1.
x3 – 5x2
+3 41/ Find the least integer
Solution. k such that f(x) is O(xk)
function = O(x2) = (x2) = (x2) for each of these
2x + 11 ✓   functions.
x2 + 3x + ✓ ✓ ✓ a/ f(x) = 2x2 + x2log x.
1 b/ f(x) = x3 + (logx)4.
x2logx +  ✓  c/ f(x) = (xlogx + 3x)(x2
2018 + 100x + 1).
x3 – 5x2  ✓ 
+3 42/ Show that 1 + 2 + 3 +
… + n is O(n2).
Ex2. Find the least integer k such that
(√𝑥 8 +𝑥 4 +1 +1)(𝑙𝑜𝑔𝑥+3)
is O(xk).
𝑥 2 +1
Solution.
x8  x4  1 x8  x4
log x  3 log x
and x 2  1 x 2
(√𝑥 8 +𝑥 4 +1 +1)(𝑙𝑜𝑔𝑥+3) x 4 log x
So,  x 2 log x
𝑥 2 +1 x 2

In other hand, x2logx is O(x3)  the least

integer k is 3.

Ex3. a/ Show that log10n is O(logn)

b/ Show that log(n!) is O(nlogn).
Solution.
a/ log10n = log102.logn  log10n is O(logn)
b/ log(n!) = log(123n)  log(nnnn) =
log(nn) = nlogn
 log(n!) is O(nlogn).
Complexity of Ex1. Consider the algorithm: 43/ Consider the
an algorithm procedure giaithuat(a1, a2, …, an : integers) algorithm: procedure
count:= 0 thuattoan(a1, a2, ..., an:
for i:= 1 to n do positive real numbers).
if ai > 0 then count: = count + 1 m := 0
print(count) for i := 1 to n-1
 Give the best big-O complexity for the for j := i + 1 to n
algorithm above. m := max(ai.aj, m)
Solution. Give the best big-O
With one “for loop” in the algorithm, the complexity for the
complexity of the algorithm is O(n). algorithm above.

Ex2. How much time does an algorithm 44/ How much time does
take to solve a problem of size n if this an algorithm take to solve
algorithm uses 2n2 + 2n operations, each a problem of size n if this
requiring 10−9 seconds, with these values of algorithm uses 2n2 + 2n
n? operations, each requiring
a/ 10 10−9 seconds, with these
b/ 50 values of n?
Solution. a/ 30.
a/ n = 10  the algorithm uses 2.102 + 210 b/ 100.
operations, each requiring 10−9 seconds
 need (2.102 + 210).10-9 = 0.000001224
seconds.
b/ n = 50  the algorithm uses 2.502 + 250
operations, each requiring 10−9 seconds 
need (2.502 + 250). 10-9 = 1125900 seconds.
Divide Ex1. Show that if a | b and b | c, then a | c, 45/ Show that if a | b and
Divisor where a, b, c are integers. b | a, then a = b or a = −b,
Division Solution. where a, b are integers.
Quotient a | b  kZ (b = ka)
Remainder b | c  mZ (c = mb) 46/ Prove or disprove that
mod and div  c = m(ka) = (mk)a, where mk is an if a | bc, then a | b or a | c,
integer where a, b, and c are
 a | c. positive integers and a 
0.
Ex2. Prove or disprove that if ab | c, where
a, b, and c are positive integers, then a | c 47/ What are the quotient
and b | c. and remainder when
Solution. a/ −1 is divided by 3?
ab | c  kZ (c = kab) b/ 3 is divided by 13?
 c = (kb)a and c = (ka)b, where ka, kb c/ −123 is divided by 19?
are integers
 a | c and b | c. 48/ Evaluate these
quantities.
Ex3. What are the quotient and remainder a/ −17 mod 2.
when b/ 144 mod 7.
a/ 1001 is divided by 13? c/ −101 div 13.
b/ −111 is divided by 11? d/ 199 div 19.
 Solution.
a/ 1001 = 13.77 + 0 49/ Suppose a mod 3 = 2
 quotient = 77 and remainder = 0. and b mod 6 = 4, find ab
b/ -111 = 11.(-11) + 10 mod 3.
 quotient = -11 and remainder = 10.

Ex4. Suppose a mod 4 = 3 and b mod 8 = 7,

find ab mod 4.
Solution.
• We have, b mod 8 = 7  b = 8k + 7,
where k is an integer
 b = 4(2k + 1) + 3
 b mod 4 = 3
• So, ab mod 4 = ((a mod 4).(b mod
4)) mod 4
= (3.3) mod 4 = 1.
Congruence Ex. Decide whether each of these integers 50/ Decide whether each
is congruent to 5 modulo 17. of these integers is
a/ 80 congruent to 3 modulo
b/ 103 7.
c/ -29 a/ 37.
d/ -122 b/ 66.
Solution. c/ −17.
Recall that a is congruent to b modulo m if d/ −67.
and only if m divides a – b.
Or equivalently, a  b  mod m  m |  a  b  51/ Find an integer x in
a/ 17  (80 – 5)  80 is not congruent to 5 {0, 1, 2, …, 6} such that:
modulo 17. a/ 5.x  1 (mod 7).
b/ 17  (103 – 5)  103 is not congruent to b/ x.x2  1 (mod 7).
5 modulo 17.
c/ 17 | (-29 – 5)  -29 is congruent to 5
modulo 17.
d/ 17  (-122 – 5)  -122 is not congruent
to 5 modulo 17.
Encryption Ex1. Suppose pseudo-random numbers are 52/ Suppose pseudo-
Decryption produced by using: random numbers are
xn+1 = (3xn + 11) mod 13. produced by using:
Hashing If x3 = 5, find x2 and x4. xn+1 = (2xn + 7)
functions Solution. mod 9.
• x4 = (3x3 + 11) mod 13 a/ If x0 = 1, find x2 and
Pseudo = (3.5 + 11) mod 13 = 0 x3.
random • x3 = (3x2 + 11) mod 13 b/ If x3 = 3, find x2 and
numbers So, 5 = (3x2 + 11) mod 13 x4.
 13 | (3x2 + 11 – 5)
 13 | (3x2 + 6) (*) 53 a/ Encrypt the
Note that x2 is in 0..12  x2 = 11 is the message SELL using the
solution of (*). function f(x) = (x + 21)
mod 26.
Ex2. Using the function b/ Decrypt these
f(x) = (x + 10) mod 26 messages “CFMV L” that
to encrypt messages. Answer each of these were encrypted using the
questions. f(x) = (x + 17) mod 26.
a/ Encrypt the message STOP
b/ Decrypt the message LEI. 54/ A parking lot has 31
Solution. visitor spaces, numbered
A B C … Z from 0 to 30. Visitors are
0 1 2 25 assigned parking spaces
using the hashing
S T O P function h(k) = k mod
18 19 14 15 31, where k is the number
formed from the first
x 18 19 14 15 three digits on a visitor’s
f(x) = 2 3 24 25 license plate. Which
(x+10) spaces are assigned by
mod the hashing function to
26 cars that have these first
three digits on their
license plates: 317, 918,
2 3 24 25
007, 111?
C D Y Z
 STOP has been encrypted to CDYZ.
b/ We will decrypt the message LEI using
the inverse function f-1(x) = (x – 10) mod
26.
Encrypted form L E I
x 11 4 8
f-1(x) = (x – 10) 1 20 24
mod 26
Original B U Y
message

Ex3. Which memory locations are assigned

by the hashing function h(k) = k mod 101
to the records of insurance company
customers with these Social Security
 Numbers?
a/ 104578690
b/ 432222187
Solution.
a/ h(104578690) = 104578690 mod 101 =
58.
 The memory location 58 is assigned
to the customer with the Social
Security number 104578690.
b/ h(501338753) = 501338753 mod 101 =
3.
So, the memory location 3 is assigned to the
customer with the Social Security number
501338753.
Prime, Ex1. Which positive integers less than 30 55/ Which positive
relatively are relatively prime to 30? integers less than 18 are
prime Solution. relatively prime to 18?
Recall that two positive integers a and b are
Gcd, lcm called relatively prime if and only if their 56/ Find these values of
greatest common divisor is 1. the Euler φ-function.
So, positive integers less than 30 are a/ φ(4).
relatively prime to 30 are: 1, 7, 11, 13, 17, b/ φ(5).
19, 23, 29. c/ φ(11).

Ex2. The value of the Euler φ-function at 57/ If the product of two
the positive integer n, φ(n), is defined to be integers is 3072 and their
the number of positive integers less than or least common multiple
equal to n that are relatively prime to n. is 384, what is their
Find these values of the Euler φ-function. greatest common
a/ φ(6) divisor?
b/ φ(7)
Solution.
a/ n = 6: positive integers less than or equal
to 6 that are relatively prime to 6 are: 1, 5
 φ(6) = 2
b/ n = 7: positive integers less than or equal
to 6 that are relatively prime to 6 are: 1, 2,
3, 4, 5, 6
 φ(7) = 6

Ex3. If the product of two integers is

273852711 and their greatest common
divisor is 23345, what is their least
 common multiple?
Solution.
If a and b are positive integers, then
ab = gcd(a, b).lcm(a, b).
7 8 2 11
So, 2 3 5 7 = gcd(a, b).lcm(a, b) =
23345.lcm(a, b)  lcm(a, b) =
273852711/23345 = 24345(711)
Euclidean Ex. Use the Euclidean algorithm to find 58/ Use the Euclidean
algorithm a/ gcd(8, 28) algorithm to find
b/ gcd(100, 101). a/ gcd(12, 18).
Solution. b/ gcd(111, 201).
a/ 28 mod 8 = 4  gcd(8, 28) = gcd(4, 8)
8 mod 4 = 0  gcd(4, 8) = gcd(0, 4) = 4.
b/ 101 mod 100 = 1  gcd(100, 101) =
gcd(1, 100)
100 mod 1 = 0  gcd(1, 100) = gcd(0, 1) =
1.
Integer Ex1. Convert 96 to 59/ Convert 69 to
representation a/ a binary expansion. a/ a binary expansion.
Decimal b/ a base 5 expansion. b/ a base 6 expansion.
Binary c/ a base 13 expansion. c/ a base 9 expansion.
Octal Solution.
Hexadecimal a/ 96 = (1100000)2 60/ Convert each of the
Expansions b/ following expansions to
• 96 = 19.5 + 1 decimal expansion.
Base b • 19 = 3.5 + 4 a/ (401)5
expansions • 3 = 0.5 + 3 b/ (12B7)13
 96 = 19.5 + 1 = (3.5 + 4).5 + 1
 96 = 3.52 + 4.51 + 1.50
 96 = (341)5
c/
• 96 = 7.13 + 5
• 7 = 0.13 + 7
 96 = 7.131 + 5.130
 96 = (75)13

Ex2. Convert each of the following

expansions to decimal expansion.
a/ (102)3
b/ (325)7
c/ (A3)12
Solution.
 a/ (1021)3 = 1.33 + 0.32 + 2.31 + 1.30 = 34
b/ (325)7 = 3.72 + 2.71 + 5.70 = 166
c/ (A3)12 = A.121 + 3.120 = 10.12 + 3 = 123.
Applications: Check digits.

1/ UPCs. Retail products are identified by their Universal Product Codes (UPCs). The
most common form of a UPC has 12 decimal digits: the first digit identifies the product
category, the next five digits identify the manufacturer, the following five identify the
particular product, and the last digit is a check digit. The check digit is determined by the
congruence
3x1 + x2 + 3x3 + x4 + 3x5 + x6 + 3x7 + x8 + 3x9 + x10 + 3x11 + x12 ≡ 0 (mod 10).
For example, if the first 11 digits of a UPC are 79357343104, then the check digit is x12 =
2.
In fact, let x12 be check digit, we have
3 · 7 + 9 + 3 · 3 + 5 + 3 · 7 + 3 + 3 · 4 + 3 + 3 · 1 + 0 + 3 · 4 + x12 ≡ 0 (mod 10)
Simplifying, we have 98 + x12 ≡ 0 (mod 10)  x12 = 2.
a/ Find the check digit for the USPS money orders that have identification number that
start with these ten digits 7555618873 and 6966133421.
b/ Determine whether 74051489623 and 88382013445 are valid USPS money order
identification number.

2/ Parity Check Bits. Digital information is represented by bit string, split into blocks of
a specified size. Before each block is stored or transmitted, an extra bit, called a parity
check bit, can be appended to each block. The parity check bit xn+1 for the bit string
x1x2...xn is defined by xn+1 = x1 + x2 +···+ xn mod 2.
(It follows that xn+1 is 0 if there are an even number of 1 bits in the block of n bits and it
is 1 if there are an odd number of 1 bits in the block of n bits). When we examine a string
that includes a parity check bit, we know that there is an error in it if the parity check bit
is wrong. However, when the parity check bit is correct, there still may be an error. For
example, if we receive in a transmission the bit string 11010110, we find that 1 + 1 + 0 +
1 + 0 + 1 + 1 ≡ 1 (mod 2), so the parity check is incorrect. So, we reject the string.
Suppose you received these bit strings over a communications link, where the last bit is a
parity check bit. In which string are you sure there is an error?
a/ 00100111111
b/ 10101010101
Chapter 4 – Induction & Recursion
Mathematical Ex1. Prove the statement "6 divides n3 - n 61/ Prove that 2 divides
induction for all integers n ≥ 0", using mathematical n2 + n whenever n is a
induction method. positive integer.
Strong Solution.
induction Basis step. The statement is true for n = 0, 62/ Prove that 2n < n! if n
since 6 divides 0. is an integer greater than
Inductive step. 3.
• Suppose for every integer k  0, the
statement is true, that is, "6 divides 63/ Suppose you wish to
k3 - k" use the Principle of
• We have, (k+1)3 - (k+1) = (k3 + 3k2 Mathematical Induction
+ 3k + 1) - (k + 1) = k3 - k + 3(k2 + to prove that
k). 11! + 22! + 33! + … +
As 6 divides k3 - k and 3(k2 + k) is a nn! = (n+1)! – 1,
multiple of 6, we conclude that (k+1)3 - for all n  1.
(k+1) is also a multiple of 6. (a) Write P(1).
By induction, 6 divides n3 - n for all (b) Write P(5).
integers n ≥ 0. (c) Use P(5) to prove
P(6).
Ex2. Suppose you wish to prove that the (d) Write P(k).
following is true for all positive integers n (e) Write P(k + 1).
by using the Principle of Mathematical (f) Use the Principle of
Induction: Mathematical Induction
P(n) = “1 + 3 + 5 + …+ (2n – 1) = n2 ” to prove that P(n) is true
(a) Write P(1) for all n  1.
(b) Write P(12)
(c) Write P(13) 64/ Suppose that the only
(d) Use the fact “P(12) is true” to prove currency were 2-VND
“P(13) is true” bills and 5-VND bills.
(e) Write P(k) Use strong induction to
(f) Write P(k + 1) show that any amount
(g) Use the Principle of Mathematical greater than 3 VND could
Induction to prove that P(n) is true for all be made from a
positive integers n. combination of these
Solution. bills.
a/ “1 = 12”
b/ “1 + 3 + 5 + … + (212 – 1) = 122”
c/ “1 + 3 + 5 + … + (213 – 1) = 132”
d/ We have P(12) is true, or “1 + 3 + 5 + …
+ (212 – 1) = 122” is true.
So, 1 + 3 + 5 + … + (213 – 1)
= 1 + 3 + 5 + … + (212 – 1) + (213 – 1)
= 122 + (2.13 – 1) (due to the truth of
P(12))
= 122 + (2.12 + 1)
= (12 + 1)2
= 132.
Hence, 1 + 3 + 5 + … + (213 – 1) = 132 and
P(13) is true.
e/ “1 + 3 + … + (2k – 1) = k2”
f/ “1 + 3 + … + [2(k + 1) – 1] = (k + 1)2”
g/
• BASIC STEP.
“1 = 12”  P(1) is true.
• INDUCTIVE STEP.
Suppose for each positive integer k, P(k) is
true, that is,
“1 + 3 + … + (2k – 1) = k2” is true.
Then, 1 + 3 + … + (2k – 1) + [2(k + 1) – 1]
= k2 + [(2(k + 1) – 1)] (due to the truth of
P(k))
= k2 + 2k + 1
= (k + 1)2
Hence, 1 + 3 + 5 + … + [2(k+1) – 1] = (k
+ 1)2 and P(k + 1) is true.
By induction, P(n) is true for all positive
integers n.

Ex3. Use strong induction to prove that

every amount of postage of six cents or
more can be formed using 3-cent and 4-cent
stamps.
Solution.
• BASIS STEP.
- 6 cents: two 3-cent stamps
- 7 cents: one 3-cent stamp and one 4-
cent stamp.
- 8 cents: two 4-cent stamps.
• INDUCTIVE STEP.
Assume every amount of postage of j cents
(6  j  k, k  8) can be formed using 3-cent
and 4-cent stamps.
We need to show that an amount of postage
of (k + 1) cents can be formed using 3-cent
and 4-cent stamps.
In fact, k + 1 = (k – 2) + 3, and since 6  (k
– 2)  k, it follows that (k – 2) cents can be
formed using 3-cent and 4-cent stamps (by
the assumption above).
So, (k – 2) + 3 cents can be formed using 3-
 cent and 4-cent stamps.
Recursive Ex1. Give a recursive definition of each of 65/ Give a recursive
definitions these functions. definition of each of
a/ f(n) = n, n = 1, 2, 3, … these functions.
b/ f(n) = 3n + 5, n = 0, 1, 2, … a/ f(n) = (-1)n, n = 0, 1, 2,
Solution. 3, …
a/ f(n) = n, n = 1, 2, 3, … b/ f(n) = 7, for all n = 1,
BASIS STEP. 2, 3, …
f(1) = 1 c/ f(n) = 1 + 2 + 3 + … +
RECURSIVE STEP. n, n =1, 2, 3, …
For n > 1, f(n) = n
 f(n – 1) = n – 1 66/ Find f(3), f(4) if:
 f(n) = f(n – 1) + 1 a/ f(1) = 3 and f(n) =
b/ f(n) = 3n + 5, n = 0, 1, 2, … 2f(n-1) + 5.
BASIS STEP. b/ f(n) = f(n-1).f(n-2) and
f(0) = 5 f(0) = 1, f(1) = 2.
RECURSIVE STEP. c/ f(n) = (f(n-1))2 – 1 and
For n > 0, f(n) = 3n + 5 f(1) = 2.
 f(n – 1) = 3(n – 1) + 5 = 3n + 2
f(n) = f(n – 1) + 3 67/ Give a recursive
definition of each of
Ex2. Give a recursive definition of each of these sets.
these sets. a/ A = {0, 3, 6, 9, 12, …}.
a/ A = {2, 5, 8, 11, 14, …}. b/ B = {…, -8, -4, 0, 4, 8,
b/ B = {…, -5, -1, 3, 7, 10, …}. …}.
c/ C = {3, 12, 48, 192, 768, …}. c/ C = {0.9, 0.09, 0.009,
Solution. 0.0009, …}.
a/ A = {2, 5, 8, 11, 14, …}
BASIS STEP.
2A
RECUSIVE STEP.
x  A  x + 3  A.
b/ B = {…, -5, -1, 3, 7, 10, …}
BASIS STEP.
3B
RECUSIVE STEP.
x  B  (x + 4  B and x – 4  B).
c/ C = {3, 12, 48, 192, 768, …}
BASIS STEP.
3C
RECUSIVE STEP.
x  C  4x  C.
Recursive Ex1. Consider an recursive algorithm to 68/ Consider an
algorithms compute the nth Fibonacci number: algorithm:
procedure Fibo(n : positive integer) procedure Fibo(n :
if n = 1 return 1 positive integer)
else if n = 2 return 1 if n = 1 return 1
else return Fibo(n – 1) + Fibo(n – 2) else if n = 2 return 1
else if n = 3 return 2
How many additions (+) are used to find else return Fibo(n – 1) +
Fibo(6) by the algorithm above? Fibo(n – 2) + Fibo(n – 3)
Solution.
From the tree below, there are 7 additions. How many additions (+)
are used to find Fibo(6)
by the algorithm above?

69a/ Write a recursive

algorithm to find the
sum of first n positive
integers.
b/ Use mathematical
induction to prove that
the algorithm in (a) is
correct.
c/ Write a recursive
algorithm to find the
value of the function f(n)
Ex2. a/Give a recursive algorithm to find = 7, for n = 1, 2, 3, …
Sm(n) = m + n, where n is a non-negative
integer and m is an integer. 70/ Consider the
b/ Use mathematical induction to show that following algorithm:
the algorithm is correct. procedure tinh(a: real
Solution. a/ number; n: positive
• Recursive definition of Sm(n): integer)
BASIS STEP. if n = 1 return a
Sm(0) = m + 0 = m else return atinh(a, n-1).
RECURSIVE STEP. a/ What is the output if
For n > 0, Sm(n) = m + n inputs are: n = 4, a = 2.5?
 Sm(n - 1) = m + (n – 1) Explain your answer.
 Sm(n) = Sm(n - 1) + 1 b/ Show that the
• Recursive algorithm to find Sm(n): algorithm computes na
procedure sum(m: integer; n: non-negative using Mathematical
integer) Induction.
if n = 0 then sum(m, n) := m
else then sum(m, n): =sum(m, n – 1) + 1
 b/ Prove the correctness of the algorithm:
BASIS STEP.
If n = 0: sum(m, n) := m = m + 0 = m + n =
Sm(n).
INDUCTIVE STEP.
Suppose for every integer k  0, sum(m, k)
returns m + k.
We need to show that sum(m, k + 1) returns
m + k + 1.
In fact, from the algorithm, k + 1 > 0 and
sum(m, k + 1): = sum(m, k) + 1 and then
returns m + k + 1.
(by the assumption, sum(m, k) returns m +
k).
Applications.
1. Determine whether each of the following bit strings belongs to the set S
recursively defined by:
• BASIS STEP: 0  S
• RECURSIVE STEP: 1w  S or 0w  S if w  S
a/  (the empty string)
b/ 0
c/ 110
d/ 10110
2. Let S be set of all bit strings of any length. Define the number #0(s) recursively
by:
• Basis step: #0(s) = 0, where  is the empty string.
• Recursive step:
#0 (𝑠) 𝑖𝑓 𝑥 ≠ 0
#0 (𝑥𝑠) = { .
1 + #0 (𝑠) 𝑖𝑓 𝑥 = 0
a) Find #0 (111)
b) Find #0 (010)
c) What can we say about s if #0 (𝑠) = 0?
d) If s and w are two bit strings, show that #0 (𝑠𝑤) = #0 (𝑠) + #0 (𝑤 ).
Chapter 5 – Counting
Product rule & Ex1. Find the number of strings of length 7 71/ There are three
sum rule of letters of the alphabet, with no repeated available flights from
letters, that begin with a vowel. Hanoi to Bangkok and,
Counting Solution. regardless of which of
functions • Keep in mind a row of seven blanks: these flights is taken,
- - - - - - -. there are five available
Counting one- • There are five ways in which the first flights from Bangkok to
to-one letter in the string can be a vowel. Manila. In how many
functions • Once the vowel is placed in the first ways can a person fly
blank, there are 25 ways in which to from Hanoi to Manila via
fill in the second blank, 24 ways to Bangkok?
fill in the third blank, etc.
• Using the product rule, we obtain 72/ Find the number of
5  25  24  23  22  21 20 strings of length 7 of
place
vowel
place
other letters
letters of the alphabet,
with repeated letters
allowed, that have vowels
Ex2. Find the number of strings of length 7
in the first two positions.
of letters of the alphabet, with no repeated
letters, that begin with C or V and end with
73/ Find the number of
C or V.
strings of length 7 of
Solution.
letters of the alphabet,
Using a row of 7 blanks, we first count the
with no repeated letters,
number of strings belonging one of two
that begin with E and end
cases:
with V or a vowel.
• Case 1: Strings begin with C and end
with V: C - - - - - V. 74/ A final test of the
 By the product rule, the number of course MAD101 contains
ways to fill in the five interior letters 50 multiple choice
is 24 · 23 · 22 · 21 · 20. questions. There are four
• Case 2: Strings begin with V and end possible answers for each
with C: V - - - - - C. question.
 By the product rule, the number of a/ In how many ways can
ways to fill in the five interior letters a student answer the
is 24 · 23 · 22 · 21 · 20. questions if the student
Therefore, by the sum rule, the answer is answers every question?
(24 · 23 · 22 · 21 · 20) + (24 · 23 · 22 · 21 · b/ In how many ways can
20) = 2(24 · 23 · 22 · 21 · 20). a student answer the
questions on the test if the
Ex3. How many subsets of the set {1, 2, 3, student can leave answers
4, 5} blank?
a/ contain 2 and 3?
b/ do not contain 3? 75/ How many subsets of
c/ have more than one element? the set {(0, 0), (0, 1), (1,
0), (1, 1)}
Solution. a/ are there in total?
a/ Suppose A is a subset of {1, 2, 3, 4, 5}, b/ contain (0, 0) and (1,
then A contains members chosen from {1, 1)?
2, 3, 4, 5}. We can see:
• 1 may belong to A or not. 76/ a/ How many
• 2 may belong to A or not. functions are there from
 • 3 may belong to A or not. the set {a, b, c, d} to the
• 4 may belong to A or not. set {1, 2, 3}?
• 5 may belong to A or not. b/ How many one-to-one
Therefore, there 22222 ways to functions are there from
construct A. the set {a, b, c, d} to the
 There are 25 = 32 subsets of {1, 2, 3, set {1, 2, 3}?
4, 5}.
b/ Similarly to the part a/, there are 24 = 16
subsets of {1, 2, 3, 4, 5} do not contain 3.
c/ number of subsets having more than one
element = number of all subsets – number
of subsets having no element = 25 – 1 = 31.

Ex4. a/ How many functions are there from

the set {a, b, c, d} to the set {1, 2, 3, 4}?
a/ How many one-to-one functions are there
from the set {a, b, c, d} to the set {1, 2, 3,
4}?
Solution.
a/ A function corresponds to a choice of one
of the 4 elements in the codomain{1, 2, 3,
4} for each of elements {a, b, c, d}in the
domain. Therefore, we have:
• 4 ways to choose the value of the
function at a.
• 4 ways to choose the value of the
function at b.
• 4 ways to choose the value of the
function at c.
• 4 ways to choose the value of the
function at d.
 By the product rule, there are 44
functions.
b/ An one-to-one function corresponds to a
choice of one of the 4 elements in the
codomain{1, 2, 3, 4} for each of elements
{a, b, c, d}in the domain so that no value of
the codomain can be used again.
Therefore, we have:
• 4 ways to choose the value of the
function at a.
• 3 ways to choose the value of the
 function at b (because the value used
for a cannot be used again for b).
• 2 ways to choose the value of the
function at c.
• 1 ways to choose the value of the
function at d.
 Therefore, there are 4321 one-to-
one functions.
|A  B| = Ex1. Find the number of integers from 100 77/ Find the number of
|A| + |B| - |AB| to 1000 inclusive that are integers from 999 to 9999
(in A or in B) a/ divisible by 7. inclusive that are:
b/ divisible by 7 or 11. a/ divisible by 13 or 17.
Solution. b/ divisible by 13 but not
a/ When we divide 1000 by 7, we obtain by 17.
142 + 6/7. Then, the largest integer in our
range that is divisible by 7 is 1427, or 994. 78/ Find the number of
And if we divide 100 by 7, the result is strings of length 7 of
about 14 + 2/7. So, the smallest integer in letters of the alphabet,
100..1000 that is divisible by 7 is 21, not with no repeated letters,
14. that
Therefore, the number of integers between a/ begin with V or end
100 and 1000 inclusive that are divisible by with a vowel.
7 is (994 – 21)/7 + 1, or 139. b/ begin or end with a
b/ vowel.
• From the part a/, there are 139 c/ begin or end with a
integers that are divisible by 7. vowel (but not both).
• Similarly, there are (990 – 110)/11 +
1, or 81 integers between 100 and
1000 inclusive that are divisible by
11.
• And again, there are (924 – 154)/77
+ 1, or 11 integers between 100 and
1000 inclusive that are divisible by
77.
By Inclusion – Exclusion principle, the
answer is 139 + 81 – 11 = 209.

Ex2. Find the number of strings of length 7

of letters of the alphabet, with no repeated
letters, that begin with E or end with a
vowel.
Solution.
 Using a row of seven blanks: - - - - - - -
• There are 252423222120 strings
of the form E- - - - - -.
• There are 2524232221205 strings
of the form - - - - - - (a vowel)
• There are 24232221204 strings of
the form E- - - - - (a vowel, not E)
By Inclusion – Exclusion principle, the
answer is 252423222120 +
2524232221205 – 24232221204.
Counting Ex1. A vending machine dispensing books 79/ How many bit strings
problems and of stamps accepts only one-dollar coins, $1 of length eight do not
Recurrence bills, and $5 bills. contain three consecutive
relations a/ Find a recurrence relation for the number 0s?
of ways to deposit n dollars in the vending
machine, where the order in which the coins 80/ Verify that an = 3n and
and bills are deposited matters. an = 3n +1 are solutions to
b/ Find a0, a1, a2, a3, a4. the recurrence relation an
c/ How many ways are there to deposit $7 = 4an - 1 - 3an - 2.
for a book of stamps?
Solution. 81/ You take a job that
a/ Let an be the number of ways to deposit n pays $10,000 annually.
dollars in the vending machine. a/ How much do you earn
Some ways to deposit n dollars: 20 years from now if you
• One $1 coin first, then (n – 1) receive a ten percent raise
dollars. In this case, there are an-1 each year?
ways corresponding to (n – 1) b/ How much do you earn
remaining dollars. 20 years from now if each
• One $1 bill first, then (n – 1) dollars. year you receive a raise
In this case, there are also an-1 ways of $1000 plus four
corresponding to (n – 1) remaining percent of your previous
dollars. year's salary?
• One $5 bill first, then (n – 5) dollars
(if n > 5). In this case, there are an-5
ways corresponding to (n – 5)
remaining dollars.
So, we have the recurrence relation
an = 2an-1, if 5 > n  1
an = 2an-1 + an-5, if n  5
b/
• a0 = 1 // the only way to deposit zero
dollar is depositing nothing.
 • a1 = 2a0 = 2.
• a2 = 2a1 = 4
$1-coin, $1-bill
$1-bill, $1-coin
$1-coin, $1-coin
$1-bill, $1-bill
• a3 = 2a2 = 2.4 = 8
• a4 = 2a3 = 16.
c/ a5 = 2a4 + a0 = 32 + 1 = 33
a6 = 2a5 + a1 = 66 + 2 = 68
a7 = 2a6 + a2 = 136 + 4 = 140.

Ex2. Find a recurrence relation for the

number of bit strings of length n that do not
contain three consecutive 0s.
Solution.
Let an be the number of bit strings of length
n that do not contain three consecutive 0s.
For example, a1 = 2 (two bit strings “0” and
“1” of length 1), a2 = 4 and a3 = 7 (except
for the string “000”).
Strings of length n we want to count are of
exactly one of three cases:
• 1 (n – 1 remaining bits satisfying the
condition). For example, with n =
length = 4, 1001 and 1100 are strings
of this type, but 1000 or 0110 are
not.  there are an-1 such strings.
• 01 (n – 2 remaining bits satisfying
the condition)  there are an-2 such
strings.
• 001(n – 3 remaining bits satisfying
the condition)  there are an-3 such
strings.
Therefore, an = an-1 + an-2 + an-3.

Ex3. Verify that an = 3n + 2 is a solution to

the recurrence relation an = 4an - 1 - 3an - 2.
Solution.
an = 3 n + 2
 an-1 = 3(n-1)+2 = 3n+1
 an-2 = 3(n-2)+2 = 3n
  4an - 1 - 3an - 2 = 4.(3n+1) – 3(3n)
 4an - 1 - 3an - 2 = 3.(3n+1) + (3n+1) –
3(3n) = 3.(3n+1) = 3n+2
 4an - 1 - 3an - 2 = an.
Therefore, an = 3n + 2 is a solution to the
recurrence relation an = 4an - 1 - 3an - 2.

Ex4. You take a job that pays $25,000

annually. How much do you earn n years
from now if you receive a four percent raise
each year?
Solution.
a/ Let Sn be the salary after n years.
Then, Sn = (1 + 0.04)Sn-1
 Sn = (1 + 0.04)nS0 = 25,000(1.04).
Applications.

1/ Messages are transmitted over a communications channel using two signals. The
transmittal of one signal requires 1 microsecond, and the transmittal of the other signal
requires 2 microseconds.
a/ Find a recurrence relation for the number of different messages consisting of
sequences of these two signals, where each signal in the message is immediately followed
by the next signal, that can be sent in n microseconds.
b/ What are the initial conditions?
c/ How many different messages can be sent in 10 microseconds using these two signals?

2/ Suppose inflation continues at five percent annually. (That is, an item that costs $1.00
now will cost $1.05 next year). Let an = the value (that is, the purchasing power) of one
dollar after n years.
a/ Find a recurrence relation for an.
b/ What is the value of $1000 after 10 years?
c/ What is the value of $1000 after 50 years?
d/ If inflation were to continue at ten percent annually, find the value of $1000 after 50
years.
Chapter 8 - Relations
Binary relation Ex1. List the ordered pairs in the relation R 82/ List the ordered pairs
from A ={0, 1, 2, 3, 4} to B ={0, 1, 2, 3}, in the relation R from A
Properties of where (a, b) ∈ R if and only if ={0, 1, 2, 3, 4} to B ={0,
relations a/ a + b = 4. 1, 2, 3}, where (a, b) ∈ R
b/ a | b. if and only if
Combination Solution. a/ a > b.
of relations a/ R = {(1, 3); (2, 2); (3, 1); (4, 0)} b/ a – b = 1.
 b/ R = {(1, 1); (1, 2); (1, 3); (1, 0); (2, 0); (2, c/ a = 2b.
Composite 2); (3, 0); (3, 3)}.
relation 83/ Determine whether
Ex2. Determine whether the relation R on the relation R on the set
the set of all real numbers is reflexive, of all real numbers is
symmetric, antisymmetric, and/or reflexive, symmetric,
transitive, where (x, y)R if and only if antisymmetric, and/or
a/ (x, y)R  x = 2y. transitive, where (x,
b/ x = 1. y)R if and only if
Solution. a/ xy = 0.
a/ x = 2y. b/ x = y + 1 or x = y – 1.
• (1, 1)R (because 1  2.1)  R is c/ x  y (mod 5).
not reflexive.
• 2 = 2.1  (2, 1)R but (1, 2)R 84/ Let R be the relation
(because 1  2.2)  R is not on the set of ordered pairs
symmetric. of positive integers such
• If xRy and yRx  x = 2y and y = 2x that
 x = y (= 0)  R is antisymmetric. (a, b)R(c, d)  ad = bc.
• (4, 2)R and (2, 1)R but (4, 1)R Show that
 R is not transitive. a/ R is reflexive.
b/ (x, y)R  x = 1. b/ R is symmetric.
• (2, 2) R  R is not reflexive. c/ R is transitive.
• (1, 2) R but (2, 1) R  R is not
85/ Let R = {(1, 2), (1, 3),
symmetric.
(2, 3), (3, 1)}, and S =
• If (x, y)R and (y, x)R, then x = 1
{(2, 1), (3, 1), (3, 2)} be
and y = 1  x = y.
relations on the set {1, 2,
Hence, R is antisymmetric.
3}. Find
• If (x, y)R and (y, z)R, then x = 1 a/ R – S.
and y = 1  (x, z)R. b/ R  S.
Hence, R is transitive.
c/ R  S.
d/ R  S.
Ex3. Let R be the relation on the set of
e/ 𝑅̅
ordered pairs of positive integers such that
f/ S-1.
(a, b)R(c, d)  a + d = b + c.
Show that g/ SR.
a/ R is reflexive.
b/ R is symmetric. 86/ List the 16 different
c/ R is transitive. relations on the set {0,
Solution. 1}.
a/ For every positive integer a, (a, a) R (a, a)
because a + a = a + a. 87/ Which of the 16
relations on {0, 1}, are
b/ (a, b)R(c, d)  a + d = b + c
  c + b = d + a  (c, d)R(a, b). a/ reflexive?
Hence, R is symmetric. b/ ir-reflexive?
c/ For all positive integers a, b, c, d, m and c/ symmetric?
n, if (a, b)R(c, d) and (c, d)R(m, n), then d/ anti-symmetric?
a + d = b + c and c + n = d + m e/ asymmetric?
 a+d+c+n=b+c+d+m f/ transitive?
 a+n=b+m
 (a, b)R(m, n).
Therefore, R is transitive.

Ex4. Let R = {(1, 1), (3, 3), (2, 3)}, and S =

{(1, 2), (3, 1), (2, 2)} be relations on the set
{1, 2, 3}. Find
a/ R – S.
b/ R  S.
c/ R  S.
d/ R  S.
e/ 𝑅̅
f/ S-1.
g/ SR.
Solution.
V

Counting Ex1. How many different relations on {a, 88/ a/ How many
relations b} contain the pair (a, b)? different relations are
Solution. there on the set {a, b, c}?
Every relation on the set {a, b} is a subset b/ How many different
of the Cartesian product {a, b} {a, b}. relations on the set {a, b,
On other hand, {a, b} {a, b} = {(a, a); (a, c} do not contain (a, a)?
b); (b, a); (b, b)}, which has 24 subsets. c/ How many different ir-
 There are 24 = 16 relations. reflexive relations are
there on the set {a, b, c}?
Ex2. How many different reflexive
relations are there on the set {a, b}?
Solution.
Every relation on the set {a, b} is a subset
of the Cartesian product {a, b} {a, b}.
And a reflexive relations on the set {a, b}
is a set containing both (a, a); and (b, b). By
the product rule, there are 1.1.2.2 such
subsets.
Therefore, there are 4 reflexive relations on
 the set {a, b}.

Ex3. How many different relations are there

from {a, b, c, d} to {1, 2, 3}?
Solution.
There are 243 = 212 relations from {a, b, c,
d} to {1, 2, 3}.
Representation Ex1. Represent each of these relations on 89/ Represent each of
s of relations {1, 2, 3, 4} with a matrix (with the elements these relations on {1, 2,
of this set listed in increasing order). 3, 4} with a matrix (with
a/ {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}. the elements of this set
b/ {(1, 1), (1, 4), (2, 2), (3, 3), (4, 1)}. listed in increasing
Solution. order).
0 1 1 1 a/ {(1, 1), (1, 3), (1, 4),
0 0 1 1  (2, 2), (2, 3), (2, 4), (3, 1),
a/  . (4, 1), (4, 2)}
0 0 0 1
  b/ {(1, 4), (3, 1), (3, 2),
0 0 0 0 (3, 4)}.
1 0 0 1
0 1 0 0  90/ How many 1- entries
b/  .
0 0 1 0 does the matrix
  representing the relation
1 0 0 0
R on A ={1, 2, 3,..., 100}
consisting of the first 100
Ex2. How many 1-entries does the matrix positive integers have if
representing the relation R on A ={1, 2, R is
3,..., 100} consisting of the first 100 a/ {(a, b) | a = b  1}?
positive integers have if R is
b/ {(a, b) | a + b < 101}?
a/ {(a, b) | a ≤ b}?
b/ {(a, b) | a + b = 100}?
91/ Let R and S be
Solution. relations on a set
a/ aRb  a ≤ b. represented by the
R 1 2 ... 99 100
matrices
1 1 1 ... 1 1 1 0 1
2 0 1 ... 1 1 M R  1 0 1  and
... ... ... ... ... ... 0 1 0 
99 0 0 0 1 1
0 1 1
M S  0 1 1  .
100 0 0 0 0 1
 The number of 1-entries is (1 + 2 + 3
1 0 0 
+ … + 100) = 5050.
b/ aRb  a + b = 100. Find the matrices that
The matrix has the size of 100x100. represent
Since the (row i, column 100 – i)-position a/ RS.
in the matrix is the only 1-entry of row i, it b/ RS-1.
follows that the matrix has n 1-entries. c/ R – S .
d/ RS.
Ex3. Let R be the relation represented by e/ RS.
the matrix
0 1 1  92/ Suppose that the
M R  0 1 1  . relation R on a set is
1 0 0  represented by the matrix
Find the matrix representing 1 1 0 
0 1 1  .
a/ R-1.  
b/ R . 1 1 0
c/ R2. a/ Is R reflexive?
d/ R – R2. b/ Is R symmetric?
e/ RR2. c/ Is R antisymmetric?
Solution.
a/ Let MR and M R be the matrices
1

representing relations R and R-1.

Recall that (i, j)  R-1  (j, i)R, or
equivalently,
(i, j)-entry = 1 in M R  (j, i)-entry = 1 in
1

MR.
 M R is the transpose of MR.
1

0 0 1 
 MR  MR   M R  1 1 0 
T
1

1 1 0 
b/ Let MR and M R be the matrices
representing relations R and R .
Recall that (i, j) R  (i, j) R, or
equivalently,
(i, j)-entry = 1 in M R  (i, j)-entry = 0 in
MR.
1 0 0 
 M R  1 0 0 .
0 1 1 
c/ Let M R 2 be the matrix representing the
relation R2.
The matrix of R2 (= RR) can be computed
by Boolean product of MRMR
0 1 1  0 1 1 
M R2  M R M R  0 1 1  0 1 1 
 
1 0 0  1 0 0 
1 1 1
 1 1 1 .
0 1 1
d/ Let M R  R2 be the matrix representing
relation R – R2.
Recall that A – B is the set of elements that
belong to A but not belong to B.
So, the relation R – R2 contains only
ordered pairs (a, b) where (a, b)R but (a,
b)R2.
So, the (i, j)-entry of M R  R is 1  the (i, j)-
2

entry of MR is 1 and the (i, j)-entry of M R 2

is 0.
0 0 0 
Therefore, M R  R 2  0 0 0 .
1 0 0
e/ Let M R R be the matrix representing the
2

relation RR2.
Recall that RR2 contains only ordered
pairs (a, b) that belong to exactly one of (R
– R2) and (R2 – R).
So, (i, j)-entry of M R R is 1  (i, j)-entry of
2

M R is 1 OR (i, j)-entry of M R is 1 (BUT

2

NOT BOTH).
0 1 1 
Therefore, M R R 2  0 1 1  .
0 0 0 

Ex4. Suppose that the relation R on a set is

1 1 0 
represented by the matrix 0 1 1  .
1 1 0
a/ Is R reflexive?
 b/ Is R symmetric?
c/ Is R antisymmetric?
Solution.
a/ Recall that a relation R on a set A is
reflexive if and only if
aA, (a, a)R.
Or equivalently, in the matrix MR, the
(row i, column i)-entry is 1 for every value
of i.
We can see (3, 3)-entry of MR is 0  (3, 3)
R  R is not reflexive.
b/ Recall that a relation R on a set A is
symmetric if and only if
ab, (a, b)R  (b, a) R.
Based on this definition, R is symmetric if
and only if the matrix MR is symmetric, that
is, the (i, j)-entry of MR equals to the (j, i)-
entry of MR.
Since MR is not symmetric ((1, 2)-entry of
MR is 1 and (2, 1)-entry of MR is 0), we can
conclude that R is not symmetric.
c/ Recall that the relation R is
antisymmetric if and only if (a, b)  R and
(b, a)  R imply that a = b. Consequently,
the matrix of an antisymmetric relation has
the property that if mij = 1 with i  j, then
mji = 0. Or, in other words, either mij = 0 or
mji = 0 when i  j .
So, it is easy to see that R is not
antisymmetric (m23 = m32 = 1).
Equivalence Ex1. Let R be the relation on the set of real 93/ Which of these
relations numbers such that relations on {0, 1, 2, 3}
aRb if and only if a − b is an integer. are equivalence
Partitions & Show that R is an equivalence relation. relations? What are the
equivalence Solution. equivalence classes of
classes • Because a − a = 0 is an integer for all that equivalence relation?
real numbers a, aRa for all real a/ R = {(0, 0), (1, 1), (2,
numbers a. Hence, R is reflexive. 2), (3, 3)}.
• Now suppose that aRb. Then a −b is b/ S = {(0, 0), (1, 1), (1,
an integer, so b − a is also an integer. 2), (2, 1), (2, 2), (3, 3)}.
Hence, bRa. It follows that R is c/ T = {(0, 0), (1, 1), (1,
symmetric. 3), (2, 2), (2, 3), (3, 1), (3,
 • If aRb and bRc, then a − b and b − c 2),
are integers. Therefore, a −c = (a − b) (3, 3)}.
+ (b − c) is also an integer. Hence,
aRc. Thus, R is transitive. 94/ Suppose that A is a
Consequently, R is an equivalence nonempty set, and f is a
relation. function that has A as its
domain. Let R be the
Ex2. (Congruence Modulo m). Let m be relation on A consisting
an integer with m > 1. Show that the of all ordered pairs (x, y)
relation such that f(x) = f(y).
R ={(a, b) | a ≡ b(mod m)} is an Show that R is an
equivalence relation on the set of integers. equivalence relation on
Solution. A.
Recall that a ≡ b (mod m) if and only if m
divides a − b. 95/ Which of these
• Note that a − a = 0 is divisible by m, relations on the set of all
because 0 = 0 · m. Hence, a ≡ a (mod people are equivalence
m), so congruence modulo m is relations? Determine the
reflexive. properties of an
• Now suppose that a ≡ b (mod m). equivalence relation that
Then a − b is divisible by m, so a − b the others lack.
= km, where k is an integer. It a/ {(a, b) | a and b are the
follows that b − a = (−k)m, so b ≡ a same age}.
(mod m). Hence, congruence modulo b/ {(a, b) | a and b share a
m is symmetric. common parent}.
• Next, suppose that a ≡ b (mod m) c/ {(a, b) | a and b speak a
and b ≡ c (mod m). Then m divides common language}.
both a − b and b − c. Therefore, there
are integers k and l with a − b = km 96/ What is the
and b − c = lm. Adding these two congruence class [3]m
equations shows that a − c = (a − b) (that is, the equivalence
+ (b − c) = km + lm = (k + l)m. class of 4 with respect to
Thus, a ≡ c (mod m). Therefore, congruence modulo m)
congruence modulo m is transitive. when m is
It follows that congruence modulo m is an a/ 2
equivalence relation. b/ 3
c/ 4
Ex3. List the ordered pairs in the d/ 5
equivalence relation R produced by the
partition A1 ={1, 2}, A2 ={3}, and A3 ={4} 97/ List the ordered pairs
of S ={1, 2, 3, 4}. in the equivalence
Solution. relations produced by the
R = {(1, 1); (1, 2); (2, 1); (2, 2); (3, 3); (4, partition {a, b}, {c, d},
 4)}. {e} of {a, b, c, d, e}.

Ex4. Determine whether the relation with 98/ Determine whether

the directed graph shown is an equivalence the relation with the
relation on the set {a, b, c, d}. directed graph shown is
an equivalence relation.

Solution.
- R is reflexive (there are loops at
every vertex).
- R is symmetric (there is an edge
from v1 to v2 whenever there is an
edge from v2 to v1).
- R is transitive (if there is an edge
from v1 to v2 and an edge from v2 to
v3, then there is an edge from v1 to
v3).
So, R is an equivalence relation.

Ex5. Which of these relations on {0, 1, 2,

3} are equivalence relations? What are the
equivalence classes of that equivalence
relation?
a/ R = {(0, 0), (1, 1), (1, 2), (2, 1), (2, 2), (3,
3)}.
b/ S = {(0, 0), (1, 2), (2, 1), (2, 2), (2, 3), (3,
3)}.
Solution.
a/ R is reflexive, symmetric and transitive.
So, R is an equivalence relation.
Equivalence classes are: {0}; {1, 2}; {3}.
b/ S is not an equivalence relation because S
is not symmetric ((2, 3)S but (3, 2)S).
Therefore, S is not an equivalence relation.
n-ary relations Ex1. The 3-tuples in a 3-ary relation 99/ The 4-tuples in a 4-
and represent the following attributes of a ary relation represent
application to student database: student ID number, name, these attributes of
database phone number. What is a likely primary published books: title,
key for this relation? ISBN, publication date,
Solution. number of pages. What is
• Two students may have the same a likely primary key for
name  is not a likely primary key this relation?
for this relation.
• Some students may not have phone 100/ Which projection
numbers  phone number is also mapping is used to delete
not a likely primary key for this the first, second, and
relation. fourth components of a 6-
• Students have different ID numbers tuple?
 student ID number is a likely
primary key for this relation.

Ex2. What do you obtain when you apply

the projection P2,3,5 to the 5-tuple (a, b, c, d,
e)?
Solution.
P2,3,5(a, b, c, d, e) = (a, d).
Applications.
Chapter 9 – Graph Theory
Simple graphs Ex1. The degree sequence of a graph is the 101/ Draw these simple
sequence of the degrees of the vertices of graphs.
Edge the graph in non-increasing order. How a/ K7.
Vertex/vertice many edges does a graph have if its degree b/ C7.
s sequence is 4, 3, 3, 2, 2? c/ W7.
Solution. d/ K3,4.
Special simple Based on the handshaking theorem,
graphs: Kn, Cn, number of edges = (½)(the sum of degrees 102/ Find the degree
Wn, Qn of vertices) = (½)(4 + 3 + 3 + 2 + 2) = 7. sequence of each of the
graphs in the exercise
Handshaking Ex2. A sequence d1, d2, ..., dn is called 101.
theorem. graphic if it is the degree sequence of a
simple graph. Determine whether each of 103/ An undirected graph
Degree of a these sequences is graphic. For those that has five vertices of
vertex are, draw a graph having the given degree degree three and three
sequence. vertices of degree five.
Adjacent a/ 3, 3, 3, 3, 2, 0. How many edges does
Incident b/ 5, 4, 3, 2, 1. the graph have?
c/ 7, 6, 5, 4, 4, 2, 1, 1.
Solution. 104/ Determine whether
Recall that a simple graph has no any a each of these sequences
multiple edge or a loop. is graphic. For those that
a/ Below is a simple graph having the are, draw a graph having
degree sequence 3, 3, 3, 3, 2, 0. the given degree
sequence.
a/ 5, 4, 3, 2, 1, 0.
b/ 1, 1, 1, 1.
c/ 4, 4, 3, 2, 1.
b/ 8, 8, 4, 4, 2, 2, 0, 0.

105/ The
complementary graph
G of a simple graph G
has the same vertices as
G. Two vertices are
b/ Recall that a graph cannot have an odd adjacent in G if and only
number of vertices that have odd degrees. if they are not adjacent in
So, no graph having the degree sequence 5, G.
4, 3, 2, 1 (3 vertices that have odd degrees). a/ If G is a simple graph
c/ Suppose there is such a simple graph with 9 vertices and G has
with vertices a, b, c, d, e, f, g, h where 11 edges, how many
deg(a) = 7, deg(b) = 6, deg(c) = 5, deg(d) = edges does G have?
4, deg(e) = 4, deg(f) = 3, deg(g) = 1 and b/ If the degree sequence
deg(h) = 1. of the simple graph G is
• First, vertex a must be adjacent to 7 4, 2, 2, 1, 1, what is the
other vertices. Hence, vertex a is degree sequence of G?
adjacent to both g and h. Draw the graphs G and G.
• Next, there are 6 vertices that are
adjacent to b. From 7 remaining
vertices beside b, at least one of g
and h is adjacent to b. In this
situation, at least one of g and h must
have degree 2 or larger. It is a
contradiction with the fact deg(g) =
deg(h) = 1.
So, there is no such a simple graph.

Ex4. The complementary graph G of a

simple graph G has the same vertices as G.
Two vertices are adjacent in G if and only if
they are not adjacent in G.
 Draw the complementary graph of the
graph below.

Solution.
By the definition, the complementary
graph G is given below:

Note that the union of G and G is the

complete graph Kn, where n is the number
of vertices of G. So, if G has m edges, then
G has n(n-1)/2 – m edges.
Bipartite Ex1. For which values of n is the graph Cn 106/ For which values of
graphs bipartite? n are these graphs
a/ Cn. bipartite?
b/ Wn. a/ Kn.
Solution. b/ Qn.
a/ Cn.
• If n is even, “odd-position” vertices 107/ Determine whether
and “even-position” vertices must be the graph represented by
colored by different color (e.g., red the adjacency matrix is
for “odd-position” and black for bipartite.
“even-position” vertices). Since no
edge connects an “odd-position”
vertex to an “even-position” vertex,
the graph Cn is bipartite if n is even.
• If n is odd, the first and the final
vertices in the cycle are both in “odd-
 positions” and they connect each
other. This means, they are colored
by the same color while they are
adjacent. Therefore, Cn is not
bipartite if n is odd.
b/ Wn.
Since the vertex at the center connecting to
all other vertices around the cycle, the graph
Wn is a non-bipartite graph.

Ex2. Determine whether the graph

represented by the adjacency matrix is
bipartite.

Solution.
From the matrix, the corresponding graph is
bipartite.
In fact, the set of vertices can be divided
into two parts {v1, v4} and {v2, v3}, where
v1 (row 1) and v4 (row 4) are not adjacent;
and v2 and v3 are not adjacent.
Connected Ex1. Find all cut vertices of the given 108/ Find all cut vertices
graphs graph. and all cut edges (or
bridges) of the given
Cut vertex graph.

Cut edge

Solution.
If vertex B is removed, the graph becomes

and disconnected. So, B is a cut vertex.

Similarly, if we remove vertex G, the graph
becomes a disconnected graph. Hence, G is
also a cut vertex.
 Ex2. Find all cut edges (or bridges) of the
given graph.

Solution.
The given graph is connected and a
removing a cut edge (or bridge) makes a
disconnected graph.
For example, if BC is removed, the graph
becomes a disconnected graph as below

So, BC is a bridge of the given graph.

Similarly, other bridges are BF, BG, GD,
and AB.
Representing Ex1. Find an adjacency matrix for each of 109/ Find an adjacency
graphs these graphs. matrix for each of these
a/ K5. graphs.
Adjacency b/ W5. a/ K6.
matrix c/ K2,3. b/ C6.
Incidence Solution. c/ W6.
matrix 0 1 1 1 1 d/ K2,4.
1 0 1 1 1  e/ Q3.

a/ 1 1 0 1 1
  110/ Find the number of
1 1 1 0 1 1-entries in the incidence
1 1 1 1 0  matrix of each of these
0 1 0 0 1 1 graphs.
1 0 1 0 0 1  a/ Kn.
 b/ Wn.
0 1 0 1 0 1
b/   c/ Km,n.
0 0 1 0 1 1
1 0 0 1 0 1 111/ Draw a graph that
 
1 1 1 1 1 0 has
 0 0 1 1 1
0 0 1 1 1 

c/ 1 1 0 0 0
 
1 1 0 0 0
1 1 0 0 0 
as its adjacency matrix.
Ex2. Find the number of 1-entries in the Is this graph bipartite?
incidence matrix of each of these graphs.
a/ K7.
b/ K2,5.
Solution.
a/ Recall that the incidence matrix has the
number of columns equaling to the number
of edges of the graph.
So, the incidence matrix of the graph K7
has 7(6)/2 = 21 columns.
By the definition of an incidence matrix and
because K7 is a simple graph, each column
of this incidence matrix has exactly two 1-
entries. Hence, there are 212 = 42 1-entries
in this matrix.
b/ Similarly to part a/, since the graph K2,5
has 25 = 10 edges, the incidence matrix of
this graph has 20 1-entries.
Isomorphism Ex1. Use paths either to show that these 112/ Use paths either to
graphs are not isomorphic or to find an show that these graphs
Path of length isomorphism between them. are not isomorphic or to
n find an isomorphism
between them.
Counting paths

Solution.
We will show that two graphs are not
isomorphic by using a special path the one
graph has but another graph has not.
In fact, the left-hand side graph (G) has one
path making a “triangle” (e.g. u1-u2-u3)
while the graph H has no the same property.
 So, two graphs are not isomorphic.

Ex2. How many paths of length 3 between

A and B does the graph have?

113/ How many paths of

length 2 between a and b
does each of these graph
have?
Solution.
a/
The adjacency matrix of the graph is
0 1 1 1
1 0 1 0 
M 
1 1 0 0
 
1 0 0 0
To find the number of paths of length 3
between A and B, we can multiply the (1, b/
2)-entry of the matrix M3.
First, we will compute M2.
0 1 1 1  0 1 1 1
1 0 1 0  1 0 1 0 
M 
2

1 1 0 0  1 1 0 0
  
1 0 0 0  1 0 0 0
3 1 1 0
1 2 1 1 

1 1 0 1
 
0 1 1 0
Next, to find the (1, 2)-entry of M3, we
multiply the first row of M2 by the second
column of M. The result is 4.
Euler Ex1. For which values of n do these graphs 114/ For which values of
paths/circuits have an Euler circuit? n do these graphs have an
a/ Kn. Euler circuit?
Hamilton b/ Cn. a/ Wn.
paths/circuits Solution. b/ Qn.
Recall that a connected graph has an Euler
circuit if and only if every vertex of this 115/ For which values of
graph has even degree. m and n does the
a/ Every vertex of Kn has degree n – 1. So, complete bipartite
Kn has an Euler circuit if and only if n is an graph Km,n have an
odd integer and n > 1. a/ Euler circuit?
b/ Every vertex of Cn has degree 2. So, Cn b/ Euler path?
has an Euler circuit for every integer n > 2.
116/ For which values of
Ex2. Does the undirected graph represented m and n does the
by the adjacency matrix complete bipartite graph
1 2 1 1 Km,n have a Hamilton
2 0 0 4  circuit?

1 0 2 3
  117/ What is the length of
1 4 3 0 the longest simple circuit
have an Euler circuit? And what is the in the graph W7?
length of an Euler circuit in this graph?
Solution. 118/ Find a Hamilton
The graph is connected and its degree circuit in the graph or
sequence is 8, 8, 6, 6. So, it has an Euler explain that it does not
circuit. The length of an Euler circuit have.
equals to the number of edges the graph
has, which is (8 + 8 + 6 + 6)/2 = 14 by the
handshaking theorem.

Ex3. a/ Determine whether K2,3 has a

Hamilton circuit or a Hamilton path.
b/ Determine whether K3,3 has a Hamilton
circuit or a Hamilton path.
c/ Determine whether K2,4 has a Hamilton
circuit or a Hamilton path.
Solution.
a/ The graph K2,3 has a Hamilton path, has
no Hamilton circuit.

(Hamilton path, not a Hamilton circuit C-

A-D-B-E)
b/ K3,3 has a Hamilton circuit and a
Hamilton path.

(Hamilton circuit and Hamilton path: A-

D-B-E-C-F-A)
c/ K2,4 has no a Hamilton circuit or a
Hamilton path.

Ex4. What is the length of the longest

simple circuit in the graph K11?
Solution.
K11 has an Euler circuit (because every
vertex in this graph has degree 10).
Recall that an Euler circuit is a simple
circuit containing every edge of the graph
K11. So, an Euler circuit in K11 is also the
longest simple circuit. Therefore, the length
of the longest simple circuit equals to the
number of edges of the graph K11, which is
55.

Ex5. Find a Hamilton circuit in the graph

or explain that it does not have.

Solution.
Suppose the graph has a Hamilton circuit,
call it (H). If a vertex has degree 2, then (H)
must pass through both two edges incident
with this vertex. So, (H) passes through the
edges a-b, a-e, f-e, f-g, c-b and c-g exactly
 once.
Because b (g) has degree 3, (H) cannot pass
through all edges incident with b (g).
Hence, (H) cannot pass through d-b two
edges and d-g. It follows that (H) cannot
pass through d. It is a contradiction.
Applications.
1/ Use Dijkstra’s algorithm to find a least expensive route in terms of total dollars using
the roads in the graph between Camden and Atlantic City.

2/ Solve the traveling salesman problem for this graph by finding the total weight of all
Hamilton circuits and determining a circuit with minimum total weight.

3/ The following is a floor plan of a house. Is it possible to enter the house in room A,
travel through every interior doorway of the house exactly once, and exit out of room
E? If so, how can this be done?
 Chapter 10 – Trees
Tree - Ex1. Which of these graphs are trees? 119/ Which of these
Definition a/ graphs are trees?
a/
Leaf

Internal nodes
b/
Child
b/
Parent

Height
c/

c/

d/
Solution.
a/ The graph is disconnected. So, it is not a
tree.
b/ The graph is connected, but it has a
simple circuit (see a triangle). So, it is not a
tree.
c/ This graph is a tree because it is a
connected graph with no simple circuit.
120/ Given the tree
Ex2. Given the tree
 If J is chosen as the root
of the tree, what is the
If B is chosen as the root of the tree, what is
height of the tree?
the height of the tree?
Solution.
If B is the root of the tree, the levels of
nodes in the tree are shown as below:
Level 0: B
Level 1: E, F, A
Level 2: C, D
Level 3: I, G, H
Level 4: J
Recall that the height of the tree is the
maximum level of the tree. Hence, the
height of the tree is 4.
m-ary trees Ex1. a/ How many edges does a tree with 121a/ How many vertices
full m-ary 10,000 vertices have? does a full 5-ary tree with
trees and b/ How many edges does a full binary tree 100 internal vertices
properties with 1000 internal vertices have? have?
Solution. b/ How many leaves does
a/ number of edges = number of vertices – 1 a full 3-ary tree with 100
= 10000 – 1 = 9999. vertices have?
b/ Keep in mind, in a full m-ary tree we
have n = mi + 1, where n is number of 122/ Suppose a full
nodes and i is the number of internal ternary tree has 16
nodes. leaves.
In this case, n = 21000 + 1 = 2001. a/ How large can the
 Number of edges = 2001 – 1 = 2000. height of the tree
possibly be?
Ex2. Suppose a full binary tree has 35 b/ How small can the
nodes. height of the tree
a/ How many leaves does the tree have? possibly be?
b/ How large can the height of the tree
possibly be?
c/ How small can the height of the tree
possibly be?
 Solution.
a/ n = mi + 1 and n = i + l
 35 = 2i + 1 and 35 = i + l
 i = 17 and l = 18.
b/ maximum height of the tree = number of
internal nodes of the tree = 17.
c/ minimum height of the tree = logm(l) =
log2(18) = 5.
Binary search Ex1. 123/ Build a binary
trees Build a binary search tree for the words search tree for the words
banana, peach, apple, pear, coconut, EAGLE, ANT, BAT,
mango, and papaya using alphabetical DUCK, BEAR, PIG,
order. CAT and DOG using
Solution. alphabetical order.

124/ How many

comparisons are needed
to locate or to add each of
these words in the binary
search tree for exercise
123, starting fresh each
time?
a/ BEAR
b/ DOG
c/ MONKEY.

125/ Using alphabetical

Ex2. How many comparisons are needed to order, construct a binary
locate or to add each of these words in the search tree for the words
binary search tree for Ex1, starting fresh in the sentence “Let the
each time? cat out of the bag.”
a/ pear
b/ banana
c/ orange.
Solution.
a/ Staring from the root of the tree to
locate/insert the word pear:
banana < pear  go to the right
peach < pear  go to the right
pear = pear  locating/inserting
successfully.
 3 comparisons.
b/ banana = banana  strop locating after
 one comparison.
c/ banana < orange  go to the right
peach > orange  go to the left
coconut < orange  go to the right
mango < orange  go to the right
papaya > orange  go to the left
left child of papaya is null  fail to locate
the word orange.
 We fail to locate orange by
comparing it successively to banana,
peach, coconut, mango, and papaya.
Once we determine that orange
should be in the left subtree of
papaya, and find no vertices there,
we know that orange is not in the
tree. Thus 5 comparisons were used.

Ex3. Using alphabetical order, construct a

binary search tree for the words in the
sentence “The quick brown fox jumps over
the lazy dog.”
Solution.

Prefix codes Ex1. Which of these codes are prefix 126/ Which of these
codes? codes are prefix codes?
Huffman code a/ a: 11, e: 00, t : 10, s: 010. a/ a: 101, e: 11, t : 001, s:
b/ a: 01, e: 101, t : 110, s: 1101. 011, n: 010
Solution. b/ a: 010, e: 11, t : 011, s:
a/ This code scheme is a prefix code. 1011, n: 1001, i: 10101
b/ From the code scheme, we can see that t
is encoded by 110 which is also the first 127/ Construct the binary
part of the string 1101 used for s. So, this tree with prefix codes
code scheme is not a prefix code. representing these coding
 schemes.
Ex2. What are the codes for a, e, i, k, o, p, a/ a: 11, e:0, t : 101, s:
and u if the coding scheme is represented by 100.
this tree? b/ a:1, e: 01, t : 001, s:
0001, n: 00001.

128/ Use Huffman

coding to encode the
word “success”. What is
the average number of
bits required to encode a
symbol?

129/ Use Huffman

coding to encode these
symbols with given
Solution. frequencies: A: 0.10, B:
Moving from the root of the tree to each 0.25, C: 0.05, D: 0.15, E:
leaf and writing the bits labeled on edges, 0.30, F: 0.07, G: 0.08.
we obtain the codes: What is the average
a: 000, e: 001, i: 01, k: 1100, o: 1101, p: number of bits required
11110, u: 11111. to encode a symbol?

Ex3. Use Huffman coding to encode the

word “google”. What is the average number
of bits required to encode a symbol?
Solution.

From the last tree, we obtain the codes for

 “google”:
e: 000, l: 001, g: 01, o: 1
 The word “google” can be coded as
string “011101001000”
 The average number of bits required
to encode a symbol is 12/5 = 2.4.
Tree traversal Ex1. a/ Construct the binary search tree 130a/ Construct the
Pre-order for the sequence: 7, 8, 2, 9, 5, 1, 3, 11, 9. binary search tree for the
In-order Given the order of numbers after applying sequence: 11, 13, 5, 4, 7,
Post-order b/ pre-order traversal. 15, 10, 6, 9.
c/ in-order traversal. Given the order of
d/ post-order traversal. numbers after applying a/
Solution. pre-order traversal.
a/ The binary search tree for the given b/ in-order traversal.
sequence of numbers: c/ post-order traversal.

b/ A preorder traversal produces the list: 7,

2, 1, 5, 3, 8, 11, 9.
c/ A preorder traversal produces the list: 1,
2, 3, 5, 7, 8, 9, 11.
d/ A preorder traversal produces the list: 1,
3, 5, 2, 9, 11, 8, 7.
Expression Ex1. What is the value of each of these 131/ What is the value of
tree expressions? each of these
Prefix a/ + − ↑ 3 2 ↑ 2 3 / 6 – 4 2 expressions?
Infix b/ 6 2 / 5 + 5 2 − ∗ a/ 7 4 2 − − 1 3 4 + + ∗
Postfix Solution. b/ ∗ + 3 + 3 ↑ 3 + 3 3 3
notations a/ This is a prefix notation c/ 2 1 ∗ 2 ↑ 7 7 – 9 3 / ∗ −
+−↑32↑23/6 42
2
132a/ Represent the
=+−↑32↑23 /62 expressions (2*x + y)*((y
3
- x))↑2 using binary
=+− ↑32 23 3
8
trees.
= + − 3 2 8 3 Write these expressions
9 in
b/ prefix notation.
 =+ 9 8 3 c/ postfix notation.
1

= 1 3
4

=4
b/ This is a postfix notation
62/5+52−∗
= 62 /5+52−∗
3

= 35 + 52-*
8

=8 52 - *
3

=83*
= 24.

Ex2. a/ Represent the expressions (x + y)↑2

− y*(5 − x) using binary trees.
Write these expressions in
b/ prefix notation.
c/ postfix notation.
Solution.
a/ Expression tree for the given expression:

b/ prefix notation:
–+xy2*y–5x
c/ postfix notation:
xy+2y 5x-*-
Applications.

1/ a/ Use Huffman coding to encode these symbols with frequencies a: 0.4, b: 0.2, c: 0.2,
d: 0.1, e: 0.1 in two different ways by breaking ties in the algorithm differently. First,
among the trees of minimum weight select two trees with the largest number of vertices
to combine at each stage of the algorithm. Second, among the trees of minimum weight
select two trees with the smallest number of vertices at each stage.
b/ Compute the average number of bits required to encode a symbol with each code and
compute the variances of this number of bits for each code. Which tie-breaking procedure
produced the smaller variance in the number of bits required to encode a symbol?

2/ Suppose that m is a positive integer with m ≥ 2. An m-ary Huffman code for a set of
N symbols can be constructed analogously to the construction of a binary Huffman
code. At the initial step, ((N − 1) mod (m − 1)) + 1 trees consisting of a single vertex with
least weights are combined into a rooted tree with these vertices as leaves. At each
subsequent step, the m trees of least weight are combined into an m-ary tree.
Using the symbols 0, 1, and 2 use ternary (m = 3) Huffman coding to encode these letters
with the given frequencies: A: 0.25, E: 0.30, N: 0.10, R: 0.05, T: 0.12, Z: 0.18.

3/ Use a decision tree to give the best way to find the lighter counterfeit coin among 24
coins.

4/ The tournament sort is a sorting algorithm that works by building an ordered binary
tree. We represent the elements to be sorted by vertices that will become the leaves. We
build up the tree one level at a time as we would construct the tree representing the
winners of matches in a tournament. Working left to right, we compare pairs of
consecutive elements, adding a parent vertex labeled with the larger of the two elements
under comparison. We make similar comparisons between labels of vertices at each level
until we reach the root of the tree that is labeled with the largest element. The tree
constructed by the tournament sort of 22, 8, 14, 17, 3, 9, 27, 11 is illustrated in part (a) of
the figure. Once the largest element has been determined, the leaf with this label is
relabeled by −∞, which is defined to be less than every element. The labels of all vertices
on the path from this vertex up to the root of the tree are recalculated, as shown in part (b)
of the figure. This produces the second largest element. This process continues until the
entire list has been sorted.
Use the tournament sort to sort the list 17, 4, 1, 5, 13, 10, 14, 6.