Semester / Academic year 2 2020-2021

FINAL EXAM
Date empty
Course title Discrete Structure for Computing
UNIVERSSITY OF TECHNOLOGY Course ID CO1007
FACULTY OF CSE Duration 90 mins Question sheet code 2024
Notes: - Student does not use course materials except one A4 (single side) hand-writing document.
- Submit the question sheet together with the answer sheet.
- Choose the best answer (only 1) for each question.

I. Multiple choices (10.0p):

1. [L.O.1.2] [Definition]: A r-regular graph G is an undirected graph in which every vertex of G has degree r.
Which one of the following is TRUE?
(a) Any r-regular graph where r is an even number has a Eulerian circuit
(b) The cube Qn is regular for all values of n ≥ 0
(c) The wheel Wn is regular if and only if n > 3
(d) None of these answers is correct.
2. [L.O.4.1] Given a simple graph G. Which of the following statements is correct:
(a) If G is a connected graph, then it is possible to remove vertices to disconnect G iff G is a complete graph.
(b) A simple graph G is bipartite if and only if it has no circuits with an odd number of edges.
(c) A simple graph G with n vertices is connected if it has more than (n − 1)(n − 2)/3 edges.
(d) If a connected simple graph G is the union of the graphs G1 and G2 , then G1 and G2 have at least two common
vertex.
3. [L.O.4.1] Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of
components in the resultant graph must necessarily lie down between
(a) k and n
(b) k − 1 and n − 1
(c) k − 1 and n + 1
(d) k + 1 and n − k
4. [L.O.4.1] Given two graphs G1 and G2:

Which of the following statements is TRUE?

(a) G1: Not planar, G2: Planar
(b) G1: Not planar, G2: Not planar
(c) G1: Planar, G2: Planar
(d) G1: Planar, G2: Not planar

Stu.: .......................................... Stu. Fullname: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page: 1

5. [L.O.4.1] Given two graphs G3 and G4:

Which of the following statements is TRUE?

(a) G3: Exists Hamilton circuit, G4: Exists Hamilton circuit
(b) G3: Exists Hamilton circuit, G4: No Hamilton circuit
(c) G3: Exist Euler circuit, G4: Exist Euler circuit
(d) G3: No Hamilton circuit, G4: No Euler path
6. [L.O.4.1] What is the number of vertices in an undirected connected graph with 27 edges, 6 vertices of degree 2, 3
vertices of degree 4 and remaining of degree 3?
(a) 18
(b) 19
(c) 20
(d) 21
7. [L.O.2.3] Find the shortest distance from A to J on the network below.

(a) The shortest distance is 26, and the path is ACDFGIJ

(b) None of these answers is correct.
(c) The shortest distance is 28, and the path is ACDFGHJ
(d) The shortest distance is 28, and the path is ABDFGHJ
8. [L.O.1.2] Are the following graphs isomorphic?

(a) G5 and G6 are isomorphic

(b) G6 and G7 are isomorphic
(c) All of thess graphs are isomorphic
(d) All of these graphs are not isomorphic

Stu.: .......................................... Stu. Fullname: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page: 2

9. [L.O.1.2] What is the chromatic number of the following graph?

(a) 3
(b) 4
(c) 5
(d) 6
10. [L.O.4.1] What is the stopping matrix of the Floyd-Warshall algorithm when we apply it to the following graph?

(a) L3
(b) L5
(c) L4
(d) L2
11. [L.O.1.2] Which of the following statement(s)is/are correct regarding Bellman-Ford shortest path algorithm?
1. Always finds a negative weighted cycle, if one exists.

2. Finds whether any negative weighted cycle is reachable from the source.
(a) 1 only
(b) 2 only
(c) Both 1 and 2
(d) Neither 1 nor 2
12. [L.O.1.2] Let T = (V, E) be a tree and let d(v) be the degree of a vertex. Which of the following statement(s)is/are
correct?
1. if T has a vertex of degree m ≥ 2, then it has at least m vertices of degree 1.
P
2. v∈V (2 − d(v)) = 2

(a) Neither 1 nor 2

(b) Both 1 and 2
(c) 1
(d) 2

Stu.: .......................................... Stu. Fullname: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page: 3

13. [L.O.4.1] Use Kruskal’s algorithm to find a minimal spanning tree for the graph below. What is the number of edge
(N ) of the minimum spanning tree and its total weight (W )?

(a) N=10 and W=36

(b) N=9 and W=36
(c) N=10 and W=37
(d) N=9 and W=38
14. [L.O.4.1] Given a graph G = (V, E) (loops allowed), and two properties:
1. If n ≥ 0, G is connected, and G has v vertices and v + n edges, then G has at least n + 1 cycles.
2. If G has v vertices, e edges and c components, then G has at least c + e − v cycles.
Which of the following statements is correct?
(a) 1 is correct, 2 is incorrect
(b) Both of 1 and 2 are correct
(c) Neither 1 nor 2
(d) 1 is incorrect, 2 is correct
15. [L.O.4.1] Pre-order and In-order traversal of a given binary search tree, T produces the following sequence of keys
{1, 2, 4, 8, 9, 5, 3, 6, 7} and {8, 4, 9, 2, 5, 1, 6, 3, 7}. Which of the following sequences of keys can be the result of a Post-
order traversal of the tree T ?
(a) {8, 4, 2, 9, 1, 5, 6, 3, 7}
(b) {8, 9, 4, 5, 2, 6, 7, 3, 1}
(c) {8, 4, 9, 1, 2, 5, 6, 3, 7}
(d) {7, 4, 9, 2, 1, 5, 6, 3, 8}
16. [L.O.1.2] Choose as the root, what is the depth-first (start from a) search of the given the graph G: (assume that the
vertices are ordered alphabetically)

(a) abcdefghijklmnopqrst
(b) abcdfejghiklmnopqrst
(c) abcdfeghijklmnopqrst
(d) None of these answers is correct

Stu.: .......................................... Stu. Fullname: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page: 4

17. [L.O.4.1] What is the correct Post-fix expression for the following expression (↑ means power)?

A + B × C/(E − F ) − 3 ↑ (C − D) − (2 × G + H) + 1

(a) ABC × EF − / + 3CD− ↑ −2 × GH + −1+

(b) ABC × EF − / + 3CD− ↑ −2G × H + −1+
(c) ABCEF × −/ + 3CD− ↑ −2G × H + −1+
(d) Another answer
18. [L.O.3.2] There are 100 people attending an environmental conference. Each member can use one of three languages
English, Russian, French. Based on a survey, there are 60 members who can only speak one kind of language, 180
members can only speak two languages English and French, 150 members can only speak two languages English and
Russian, 170 members can only speak two languages Russian and French. How many members can speak all three
languages?
(a) 50
(b) 60
(c) 70
(d) 80
19. [L.O.3.1] Lets a, b, c be the number of elements in three sets A, B, C (a, b, c > 0), respectively. We know that a = 2b,
and b > c. The number of the subset of A is greater than the number of the subset of B (the difference is x). The
number of the subset of B is greater than the number of the subset of C (the difference is 15). Find x
(a) 230
(b) 240
(c) 250
(d) 260
20. [L.O.4.2] In a residential area, the probability that a person smokes is 30%. Know the rate of sore throat among smokers
is 60%, among non-smokers is 30%. Random examination of 1 person and found that person has a sore throat. Find
the probability that the person is a smoker.
(a) 36.2%
(b) 46.2%
(c) 56.2%
(d) Another answer.
21. [L.O.4.2] Suppose A and B are finite sets with cardinalities |A| = n and |B| = m. How many functions f : A → B are
there?
(a) m! × n!
(b) mn
(c) m!/n
(d) None of these answers is correct.
22. [L.O.4.2] There are n bags each containing n + 1 balls such that the ith bag contains i white balls and (n + 1 − i) red
balls. Let ui be the event of selecting an ith bag, i = 1, 2, . . . n; P (ui ) = n1 . w denote the event of getting a white ball.
If n is even and E denotes the event of choosing an even-numbered bag, then the value of P (w|E) is:
n+2
(a) 2n+1
n+2
(b) 2n+2
n
(c) n+1
1
(d) n+1

Stu.: .......................................... Stu. Fullname: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page: 5

23. [L.O.3.1] According to statistics, it is shown that 85% of the products of the COMP company meet the requirements
of the clients. Assume this factory’s productivity is 20 pieces per hour. What is the probability that there will be 8 or
9 satisfactory products in 30 minutes?
(a) 61.33%
(b) 62.33%
(c) 63.33%
(d) 64.33%
24. [L.O.4.2] There is a game, such that people have to pay x USD to play. In this game the player will roll a normal dice
(6 faces: 1 to 6) three times. If all three times the number of the face is 6, the player can get back 6 USD. If two times
the number of the face is 6, the player can get back 4 USD. If only one time the number of the face is 6, the player can
get back 2 USD. Otherwise, the player will be lost x USD. Calculate the value of x so that the game is fair.
(a) x ≈ 0.8
(b) x ≈ 1.0
(c) x ≈ 1.2
(d) x ≈ 1.4

25. [L.O.4.2] If P (A|C) > P (B|C) and P (A|C) > P (B|C) then:
(a) P (A) = P (B)
(b) P (A) > P (B)
(c) P (A) ≤ P (B)
(d) P (A) ≥ P (B)

Stu.: .......................................... Stu. Fullname: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page: 6

Solution 2021
I. Multiple choices (10.0p):

1. [L.O.1.2] [Definition]: 2. [L.O.4.1] Given a sim- 4. [L.O.4.1] Given two 5. [L.O.4.1] Given two
A r-regular graph G is ple graph G. Which graphs G1 and G2: graphs G3 and G4:
an undirected graph in of the following state-
which every vertex of G ments is correct:
has degree r.
(a) If G is a con-
Which one of the fol-
nected graph,
lowing is TRUE?
then it is pos-
(a) Any r-regular sible to remove
graph where r vertices to dis-
is an even num- connect G iff G
ber has a Eule- is a complete Which of the follow-
rian circuit graph. ing statements is Which of the follow-
(b) The cube Qn is (b) A simple graph TRUE? ing statements is
regular for all G is bipartite TRUE?
(a) G1: Not pla-
values of n ≥ 0 if and only if (a) G3: Exists
nar, G2: Planar
it has no cir- Hamilton
(c) The wheel Wn cuits with an circuit, G4:
odd number of (b) G1: Not pla-
is regular if and Exists Hamil-
only if n > 3 edges. nar, G2: Not
planar ton circuit
(d) None of these (c) A simple graph
G with n (c) G1: Planar,
answers is cor- G2: Planar (b) G3: Exists
rect. vertices is
Hamilton
connected if it (d) G1: Planar,
circuit, G4:
has more than G2: Not planar
No Hamilton
(n−1)(n−2)/3
circuit
edges.
(c) G3: Exist Euler
(d) If a connected circuit, G4: Ex-
simple graph G ist Euler circuit
is the union of
the graphs G1 (d) G3: No Hamil-
and G2 , then ton circuit, G4:
G1 and G2 No Euler path
have at least
two common
vertex.

3. [L.O.4.1] Let G be an
arbitrary graph with
n nodes and k com-
ponents. If a vertex 6. [L.O.4.1] What is the
is removed from G, number of vertices in an
the number of compo- undirected connected
nents in the resultant graph with 27 edges, 6
graph must necessarily vertices of degree 2, 3
lie down between vertices of degree 4 and
remaining of degree 3?
(a) k and n
(a) 18
(b) k − 1 and n − 1
(b) 19
(c) k − 1 and n + 1 (c) 20
(d) k + 1 and n − k (d) 21

Stu.: .......................................... Stu. Fullname: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page: 1

7. [L.O.2.3] Find the 9. [L.O.1.2] What is the 11. [L.O.1.2] Which of 13. [L.O.4.1] Use Kruskal’s
shortest distance from chromatic number of the following state- algorithm to find a
A to J on the network the following graph? ment(s)is/are correct minimal spanning tree
below. regarding Bellman- for the graph below.
Ford shortest path What is the number
algorithm? of edge (N ) of the
minimum spanning tree
1. Always finds a and its total weight
negative weighted (W )?
cycle, if one ex-
ists.
2. Finds whether
any negative
weighted cycle is
reachable from
(a) 3 the source.
(b) 4 (a) 1 only
(a) The shortest (c) 5 (b) 2 only
distance is 26,
(d) 6 (c) Both 1 and 2
and the path is
(d) Neither 1 nor 2 (a) N=10 and
ACDFGIJ
W=36
(b) None of these
(b) N=9 and
answers is cor-
W=36
rect.
(c) N=10 and
(c) The shortest
W=37
distance is 28,
and the path is (d) N=9 and
ACDFGHJ W=38
(d) The shortest
distance is 28,
and the path is
ABDFGHJ

14. [L.O.4.1] Given a graph

G = (V, E) (loops al-
lowed), and two proper-
ties:
10. [L.O.4.1] What is the
8. [L.O.1.2] Are the 1. If n ≥ 0, G is con-
stopping matrix of the
following graphs iso- nected, and G has
Floyd-Warshall algo-
morphic? v vertices and v +
rithm when we apply it
n edges, then G
to the following graph? 12. [L.O.1.2] Let T =
has at least n + 1
(V, E) be a tree and
cycles.
let d(v) be the de-
gree of a vertex. Which 2. If G has v ver-
of the following state- tices, e edges and
ment(s)is/are correct? c components,
then G has at
1. if T has a ver-
least c + e − v
tex of degree m ≥
cycles.
2, then it has at
(a) G5 and G6 are least m vertices of Which of the follow-
isomorphic degree 1. ing statements is cor-
(b) G6 and G7 are
P rect?
2. v∈V (2−d(v)) =
isomorphic 2 (a) 1 is correct, 2 is
(c) All of thess incorrect
graphs are (a) Neither 1 nor 2
(a) L3 (b) Both of 1 and 2
isomorphic are correct
(b) L5 (b) Both 1 and 2
(d) All of these (c) Neither 1 nor 2
4
graphs are not (c) L (c) 1
(d) 1 is incorrect, 2
isomorphic (d) L2 (d) 2 is correct

Stu.: .......................................... Stu. Fullname: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page: 2

15. [L.O.4.1] Pre-order and 17. [L.O.4.1] What is the 19. [L.O.3.1] Lets a, b, c be 22. [L.O.4.2] There are n
In-order traversal of correct Post-fix expres- the number of elements bags each containing
a given binary search sion for the follow- in three sets A, B, C n + 1 balls such that
tree, T produces the fol- ing expression (↑ means (a, b, c > 0), respec- the ith bag contains i
lowing sequence of keys power)? tively. We know that white balls and (n +
{1, 2, 4, 8, 9, 5, 3, 6, 7} a = 2b, and b > c. The 1 − i) red balls. Let ui
and A+B×C/(E−F )−3 ↑ (C−D)−(2×G+H)+1
number of the subset of be the event of select-
{8, 4, 9, 2, 5, 1, 6, 3, 7}. A is greater than the ing an ith bag, i =
Which of the following number of the subset of 1, 2, . . . n; P (ui ) = n1 . w
sequences of keys can (a) ABC × EF − B (the difference is x). denote the event of get-
be the result of a Post- / + 3CD− ↑ The number of the sub- ting a white ball. If n
order traversal of the −2×GH+−1+ set of B is greater than is even and E denotes
tree T ? the number of the sub- the event of choos-
(b) ABC × EF − set of C (the difference ing an even-numbered
(a) {8, 4, 2, 9, 1, 5,
is 15). Find x bag, then the value of
6, 3, 7} / + 3CD− ↑
P (w|E) is:
(b) {8, 9, 4, 5, 2, 6, −2G×H+−1+ (a) 230
n+2
(b) 240 (a) 2n+1
7, 3, 1}
(c) ABCEF × (b) n+2
(c) {8, 4, 9, 1, 2, 5, (c) 250 2n+2
−/ + 3CD− ↑ n
6, 3, 7} (d) 260 (c)
−2G×H+−1+ n+1
(d) {7, 4, 9, 2, 1, 5, (d) 1
(d) Another an- n+1
6, 3, 8}
swer

20. [L.O.4.2] In a residen-

tial area, the proba-
bility that a person
smokes is 30%. Know
the rate of sore throat
among smokers is 60%,
16. [L.O.1.2] Choose as among non-smokers is
the root, what is the 30%. Random examina-
depth-first (start from tion of 1 person and
a) search of the given found that person has
the graph G: (assume 18. [L.O.3.2] There are 100 a sore throat. Find
that the vertices are people attending an the probability that the
ordered alphabetically) environmental confer- person is a smoker.
ence. Each member (a) 36.2%
can use one of three
(b) 46.2%
languages English,
Russian, French. Based (c) 56.2%
on a survey, there are (d) Another an-
60 members who can swer.
only speak one kind of 23. [L.O.3.1] According to
language, 180 members statistics, it is shown
can only speak two that 85% of the prod-
languages English and ucts of the COMP com-
French, 150 members pany meet the require-
can only speak two 21. [L.O.4.2] Suppose ments of the clients. As-
(a) abcdefghi languages English and A and B are finite sume this factory’s pro-
jklmnopq Russian, 170 members sets with cardinalities ductivity is 20 pieces
rst can only speak two |A| = n and |B| = m. per hour. What is the
(b) abcdfejgh languages Russian and How many functions probability that there
iklmnopq French. How many f : A → B are there? will be 8 or 9 satis-
rst members can speak all factory products in 30
three languages? (a) m! × n! minutes?
(c) abcdfeghi
jklmnopq (b) mn
(a) 50 (a) 61.33%
rst (c) m!/n
(b) 60 (b) 62.33%
(d) None of these (d) None of these
(c) 70 (c) 63.33%
answers is cor- answers is cor-
rect (d) 80 rect. (d) 64.33%

Stu.: .......................................... Stu. Fullname: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page: 3

24. [L.O.4.2] There is a 25. [L.O.4.2] If P (A|C) >
game, such that people P (B|C) and P (A|C) >
have to pay x USD to P (B|C) then:
play. In this game the
(a) P (A) = P (B)
player will roll a nor-
mal dice (6 faces: 1 to (b) P (A) > P (B)
6) three times. If all (c) P (A) ≤ P (B)
three times the num- (d) P (A) ≥ P (B)
ber of the face is 6, the
player can get back 6
USD. If two times the
number of the face is 6,
the player can get back
4 USD. If only one time
the number of the face
is 6, the player can get
back 2 USD. Otherwise,
the player will be lost
x USD. Calculate the
value of x so that the
game is fair.
(a) x ≈ 0.8
(b) x ≈ 1.0
(c) x ≈ 1.2
(d) x ≈ 1.4

Stu.: .......................................... Stu. Fullname: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page: 4