CMPSC 360 Discrete Mathematics for Computer Science
Spring 2022 Mahfuza Farooque Final Practice ExamSolutions
Syllabus:
1. Predicate Logic: Chapter 2.6, 2.7
2. Proofs(Direct, Indirect Proofs): Chapter 4
3. Relations: Chapter 4
5. Proof by Induction: Chapter 6
6. Number theory(RSA included): Chapter 8
7. Counting: Chapter 7:Basic of Counting, Permutation, Combination, Binomial Th.
8. Graph Theory: Chapter 9
(Spanning tree is not part of the syllabus)
1. Suppose that there is a certain town in which all the men either shave themselves, or they are shaved
by the town barber Figaro (who is male). Suppose Vinny is too cheap to have the barber shave him.
Let S(x,y) be the two variable predicate “person x is shaved by person “y”. First translate the given
statement into English, then determine the truth value of the statement and justify your answer.
(a) ∀x(S(x, Figaro)∨S(x,x))
Ans: Note that the implied domain for both x and y is the men who live in this town.
Translation: Every man in the town is either shaved by the barber Figaro or shaves himself.
Value: True (this is the given statement above).
(b) ∀x(¬S(x,x)→ S(x, Figaro))
Ans: Translation: Every man in the town that does not shave himself is shaved by the barber
Figaro.
Value: True (since there are only two possibilities, one of them must hold).
(c) ∀x(S(x, Figaro)→¬S(x,x))
Ans: Translation: Every man in the town that is shaved by the barber Figaro does not shave
himself.
Value: False (the counterexample is Figaro, who shaves himself and is also shaved by Figaro).
(d) ∃y∀x(S(x,y))
Ans: Translation: There is a man who shaves every man in the town.
Value: False (Since Vinny shaves himself, there is noone who shaves everyone).
(e) ∃!x(S(x,x)∧S(x, Figaro))
Ans: Translation: There is exactly one man who both shaves himself and is shaved by the barber
Figaro.
Value: True (the example is Figaro, who shaves himself and is also shaved by Figaro).
CMPSC 360, Spring 2022, Final Practice ExamSolutions 1
2. The relation R = {(a,b) | |a+1| = |b+1|} is defined on the set of integers Z. Find the equivalence
class for R.
Solution: It’s easy to make sure that R is an equivalence relation. The equivalence classes of R are
defined by the expression {−1−n,−1+n}, where n is an integer.
Below are some examples of the classes En for specific values of n and the corresponding pairs of the
relation R for each of the classes:
n= 0 : E0 = [−1] =−1,R0 = (−1,−1)
n= 1 : E1 = [−2] =−2,0,R1 = (−2,−2),(−2,0),(0,−2),(0,0)
n= 2 : E2 = [−3] =−3,1,R2 = (−3,−3),(−3,1),(1,−3),(1,1)
n=−2 : E−2 = [1] = 1,−3,R−2 = (1,1),(1,−3),(−3,1),(−3,−3)
n= 10 : E10 = [−11] =−11,9,R10 = (−11,−11),(−11,9),(9,−11),(9,9)
n=−10 : E−10 = [−11] = 9,−11,R−10 = (9,9),(9,−11),(−11,9),(−11,−11)
As it can be seen, E2 = E−2,E10 = E−10. It follows from here that we can list all equivalence classes
for R by using non-negative integers n.
3. Consider the following graph. Starting from node 1, how many Hamiltonian paths there exists in this
graph? How many Eulerian trails can be found in this graph?
Solution:
Starting from node 1, since all the of the nodes are connected, there are there are 3! of choices for
Hamiltonian paths. This is equal to all permutations of 3 objects. There are no Eulerian trails in this
graph since there are 4 nodes with odd degrees.
CMPSC 360, Spring 2022, Final Practice ExamSolutions 2
4. How many Hamiltonian cycles there exists in Kn graph?
(Hint: Just be cautious that cycles are invariant under reflection and rotation) All the nodes in Kn
graph are connected, so we there is a path between all permutations of the nodes. For the cycles, we
should count the number of
Solution: There are n! possible permutations between n objects. But we should consider that cycles
are invariant under rotation. So each n permutations refer to the same cycle. Also, each cycle is
invariant under reflection. So we should also divide the result by a factor of 2. So we have n!n×2 =
(n−1)!
2
Hamiltonian paths in Kn graphs.
5. Suppose you have a bipartite graphs with two disjoint set of nodes V and U where all the edges only
exist between V and U . If d(u) denotes the degree of node u, prove that ∑u∈U d(u) = ∑v∈V d(v)|E|.
Solution: We know that the summation of all node degrees in a graph is equal to 2|E|. So we have
∑u∈U d(u)+∑v∈V d(v) = 2|E|. Since there are no edges inside the sets U and V , all of the nodes
connected to u ∈ U are a member of V and vice-versa. So ∑u∈U d(u) counts each edge exactly
once since the other end-point of each edge is in V . This is also true for ∑v∈V d(v). So we have
∑u∈U d(u) = ∑v∈V d(v)|E|.
6. Expand (7x+5y)6 by Binomial Theorem.
Solution: (Mention the formula) 1.(7x)6+6.(7x)5.(5y)+15.(7x)4.(5y)2+20.(7x)3.(6y)3+15.(7x)2+
6.(7x).(5y)5+1.(5y)6
7. Prove that 1+a+a2+a3+ ...+an = a
n+1−1
a−1
Proof: Let P(n) be the statement that 1+a+a2+a3+ ...+an = a
n+1−1
a−1
We procede by induction on n. Base Case:
For n = 1, we have
a2−1
a−1 = a+1
Therefore, P(1) is true.
Inductive Hypothesis: Assume that for any k >= 1, P(k) holds. That means,
1+a+a2+a3+ ...+ak =
ak+1−1
a−1
.
Inductive Step: We must show that the statement holds for for n = k+ 1.That means we want to
show that
1+a+a2+a3+ ...+ak+1 =
ak+2−1
a−1
To do that, let’s expand the left hand side of the equation:
1+a+a2+a3+ ...+ak+ak+1
=
ak+1−1
a−1 +a
k+1( By induction hypothesis)
CMPSC 360, Spring 2022, Final Practice ExamSolutions 3
=
ak+1−1+ak+2−ak+1
a−1
=
ak+2−1
a−1
Therefore, P(k+1) holds. Thus by the principle of mathematical induction, for all n≥ 1, P(n) holds
2
8. In an online auction event, the host Bob and bidder Alice are communicating using the RSA encryp-
tion method. Imagine you are the bidder Alice, and you will first send Bob an encrypted message (a
bid). After receiving Alice’s bid, Bob will then reply with the latest highest bid.
Assume that Alice’s bid is 3, and Bob’s reply is 2.
Alice’s setup:
p= 3
q= 17
e= 43
Bob’s setup:
p= 13
q= 11
e= 7
How do you encrypt your bid and decrypt Bob’s reply?
solution:
encrypt bid using Bob’s public key:
pq= 143, e= 7, msg= 3, then ciphertext=37 mod 143 = 42.
decrypt Bob’s reply using Alice’s private key.
pq= 51
φ = 32
ed ≡ 1 mod 32,d = 3
to decrypt,23 ≡ 8 mod 51.
So Bob’s reply is 8.
9. Alice and Bob are discussing a graph that has 17 vertices and 129 edges. Bob argues that the graph
is hamiltonian, while Alice says that he’s wrong. Without knowing anything more about the graph,
must one of them be right? If so, who and why, and if not, why not?
solution: The complete K17 would have 17C2 = 136 edges. So we are missing only 7 edges. Thus
every vertex has degree at least 16−7 = 9 > 17/2.
CMPSC 360, Spring 2022, Final Practice ExamSolutions 4
10. Prove that for all integer, a is odd if and only if a2 is odd.
11. Prove that if a is odd then a2 is odd. (Apply prove by contradiction and prove by contrapositive.)
12. Please check the review class, lectures notes, Book for Graph and Trees.
Finally, Practice on Textbook examples, class notes example, HWs and Class quiz related examples.
Good Luck !!!
CMPSC 360, Spring 2022, Final Practice ExamSolutions 5