Matric No. :…………..

CPT212 -
Design & Analysis of
Algorithms
(Reka Bentuk & Analisis
Algoritma)

TEST II - SEMESTER II 2022/23

VENUE: DKG31/AUDITORIUM DATE: 5th July 2023 TIME: 1.55 pm-2.55pm (1 hour)

NAME OF STUDENT: _____________________________________________________

MATRIC. NO.: _______________________ I/C(PASSPORT) NO.:_________________________________

SIGNATURE:___________________________________

INSTRUCTIONS TO CANDIDATES (ARAHAN KEPADA CALON):

Please ensure that this test paper contains 23 questions in 6 printed pages. Questions 1-20 are of multiple-
choice type while questions 21-23 are of subjective type. You are required to answer Questions 1-20 in the
space provided below. For Questions 21-23 you are required to answer in the space provided in each
question or in other blank spaces.

NO parts of this paper should be taken out of the test venue. Any incomplete papers submitted will not be
checked and appropriate action will be taken.
You may answer in English or Malay.

FOR EXAMINER'S USE

Questions 1-20: ____/50, Q. 21: ___/20, Q. 22: ____/15, Q. 23: ____/15, Total: ____/100

Answer space for Questions 1-20: Shade the letter to indicate the chosen answer.

1) = A = = B = = C = = D = = E = 11) = A = = B = = C = = D = = E =
2) = A = = B = = C = = D = = E = 12) = A = = B = = C = = D = = E =
3) = A = = B = = C = = D = = E = 13) = A = = B = = C = = D = = E =
4) = A = = B = = C = = D = = E = 14) = A = = B = = C = = D = = E =
5) = A = = B = = C = = D = = E = 15) = A = = B = = C = = D = = E =
6) = A = = B = = C = = D = = E = 16) = A = = B = = C = = D = = E =
7) = A = = B = = C = = D = = E = 17) = A = = B = = C = = D = = E =
8) = A = = B = = C = = D = = E = 18) = A = = B = = C = = D = = E =
9) = A = = B = = C = = D = = E = 19) = A = = B = = C = = D = = E =
10) = A = = B = = C = = D = = E = 20) = A = = B = = C = = D = = E =

(50 marks)

1
 Matric No. :…………..

Questions 1-24: Answer in the space given at the front page of this test paper (50 marks).
1. What are the characteristics or attributes of a graph whose adjacency lists are as follows?

A: C → B‫ﬧ‬
A B
B: ‫ﬧ‬
C: B →D‫ﬧ‬
D: ‫ﬧ‬ C D
I. Acyclic, II. Connected, III. Has a cycle, IV. Undirected
(a) I only (b) I and II only (c) II and III only
(d) II, III and IV only (e) None of the above

2. An undirected graph application frequently requires a determination of whether a node is isolated

(a node with no incident edges). An efficient implementation of ADT graph for this application is:
(a) adjacency lists
(b) adjacency matrix
(c) Both of the above answers are efficient
(d) Both of the above answers are inefficient
(e) No answer is given above
3. When the vertices of a digraph are traversed into DFS traversal, then:
(a) The digraph must include a cycle.
(b) The order of the traversal must be unique.
(c) The order of nodes of the digraph is in ascending order of the indices.
(d) The graph must be connected.
(e) No appropriate answer is given above.
4. Which of the following terminologies for graph is WRONG?
(a) A graph is called a weighted graph if each edge has an assigned number.
(b) A connected graph is a graph where for each pair of distinct vertices there is a path
connecting them.
(c) A simple graph is a graph consisting of a possibly empty set of vertices and a possibly
empty set of edges.
(d) A vertex is isolated if its degree is 0.
(e) All the above answers are correct.

5. Find the minimum spanning tree using Prim-Jarnik algorithm to the following graph starting from
vertex A. The total minimum cost for the spanning tree is:
A
3
7
D B C
1
7
5 6 2
3
E F G
6
3
H I
4 6
1
K J
(a) 41
(b) 34
(c) 29
(d) 26
(e) 31

2
 Matric No. :…………..

6. Shortest path algorithm is applied to a weighted graph with the following adjacency matrix. The
origin for the algorithm is vertex 3. This is not an appropriate question as it was not
covered in class.
1 2 3 4 5
1| 0 8  9 4
2|  0 1  
3|  2 0 3 
4|   2 0 7
5|   1 8 0
Which of the following is TRUE?
(a) Shortest path from vertex 3 to vertex 5 has a length of 10.
(b) Shortest path from vertex 3 to vertex 4 has a length of 2.
(c) Shortest path from vertex 3 to vertex 2 has a length of 2.
(d) There is a path from vertex 3 to vertex 1.
(e) All of the above are false.

7. Which of the following properties of Bellman- Ford’s and Dijkstra’s shortest path algorithm is
WRONG?
(a) Ford’s gives all-to-all shortest paths while Dijkstra’s gives only one-to-all shortest paths.
(b) Bellman-Ford’s is more powerful than Dijkstra’s in that it can process graphs with negative
weights.
(c) Dijkstra’s algorithm is based on the greedy method while Bellman-Ford’s is not.
(d) Bellman-Ford’s is more efficient than Dijkstra’s.
(e) None of the above.

8. Complexity of depth-first search is

(a) O(n+m) (b) O(nm) (c) O(n2) (d) O(m2) (e) O(nm2)
where n is the number of vertices and m is the number of edges.

9. Complexity of breadth-first search is

(a) O(n+m) (b) O(nm) (c) O(n2) (d) O(m2) (e) O(nm2)
where n is the number of vertices and m is the number of edges.

10. A strongly connected component is a subgraph such that

(a) each vertex can reach all other vertices in the graph.
(b) each vertex can reach all other vertices in the subgraph.
(c) it is the largest possible subgraph and each vertex can reach all other vertices in the
subgraph.
(d) vertices of the subgraph are reachable from only a single vertex.
(e) None of the above.
11. A hash function should
(a) minimise collision and thus improving search performance.
(b) maximise collision and thus reducing search performance.
(c) minimise collision and thus badly affecting search performance
(d) maximise collision without badly affecting search performance.
(e) None of the above is a suitable answer.
12. If someone is very careful in selecting a hash function, searching may take place in most of the
time in:
2
(a) O(1), (b) O(log n), (c) O(n), (d) O(n * log n), (e) O(n )

13. A hash table is indexed 0..1011, with a hash function h(key) = key % 11. How many
collisions will occur when key 7, 0, 4, 8, 1 are inserted into the hash table?
(a) 0 (b) 1 (c) 3 (d) 4 (e) 5 7 % 11= 4, 0 % 11= 11, 4 % 11= 7, 8% 11= 3, 1 % 11 = 10

14. A hash table contains 8 slots and is indexed 0..7. The hash function used on the hash table is
(Key+1) % 8. Separate Chaining is used to resolve collision. The following keys are inserted into
the hash table: 23, 34, 8, 6, 7, 14, 28. The longest chain of the hash table is of length:
(a) 1 (b) 2 (c) 3 (d) 4 (e) 5
0: 23,7/- 1: 8,6 /- 2: /- 3: 34/- 4:/- 5: 28:/- 6: /- 7: 14/-

3
 Matric No. :…………..

15. Which of the following is TRUE WRONG?

(a) In linear probing, the time to search for a free cell can be very large.
(b) If the table is relatively empty, blocks of occupied cells start forming (primary clustering) in
quadratic probing.
(c) In linear probing, as long as the table is large enough, a free cell will always be found
(d) Secondary clustering is caused by the fact that keys that hash to the same home position
will probe the same alternative cells
(e) None of the above.

16. Pattern matching problem is:

(a) Given a text string of length 𝑛 and a pattern string of length 𝑚>𝑛, determine if the pattern
is a substring of the text.
(b) Given a text string of length 𝑛 and a pattern string of length 𝑚<𝑛, determine if the pattern
is a substring of the text.
(c) Given a text string of length 𝑛 and a pattern string of length 𝑚>𝑛, determine if the pattern
is a suffix of the text.
(d) Given a text string of length 𝑛 and a pattern string of length 𝑚<𝑛, determine if the pattern
is a prefix of the text.
(e) None of the above.

17. Brute-force method for pattern matching:

(a) enumerate all possible configurations of inputs involved and pick the worst of all these
enumerated configurations.
(b) enumerate all possible configurations of inputs involved and pick the best of all these
enumerated configurations.
(c) enumerate some possible configurations of inputs involved and pick the best worst average
of all these enumerated configurations.
(d) enumerate some possible configurations of inputs involved and pick the best of all these
enumerated configurations.
(e) no appropriate answer is given above.

18. In Boyer-Moore algorithm, if there is a mismatch of character 𝑡𝑒𝑥𝑡[𝑖]=𝑐 with corresponding

character 𝑝𝑎𝑡𝑡𝑒𝑟𝑛[𝑘],
(a) if 𝒄 does exist anywhere in the pattern, shift the pattern completely past 𝑡𝑒𝑥𝑡[𝑖]=𝑐.
(b) if 𝒄 does not exist anywhere in the pattern, shift the pattern completely past 𝑡𝑒𝑥𝑡[𝑖]=𝑐.
(c) if 𝒄 does exist anywhere in the pattern, shift until the character 𝒄 gets aligned with the first
character of 𝑡𝑒𝑥𝑡[𝑖].
(d) if 𝒄 does not exist anywhere in the pattern, shift until the character 𝒄 gets aligned with
𝑡𝑒𝑥𝑡[𝑖].
(e) None of the above.

19. What is the worst-case complexity of the brute force search?

(a) 𝑶(𝒎𝒏)
(b) 𝑶(𝒎(𝒏−1))
(c) 𝑶(𝒎(𝒏2))
(d) 𝑶(𝒎(log 𝒏)
(e) 𝑶(𝒎(𝒏−𝒎))

20. Looking-Glass Heuristics is that:

(a) Given a text string of length 𝑛 and a pattern string of length 𝑚>𝑛, determine if there is a
need to jump some characters
(b) Given a text string of length 𝑛 and a pattern string of length 𝑚>𝑛, determine if there is a
need to work backward.
(c) When testing a pattern against the text, perform comparisons against the pattern from left
to right.
(d) When testing a pattern against the text, perform comparisons against the pattern from
right to left.
(e) None of the above.

4
 Matric No. :…………..

Questions 21-23: Answer in the space provided in each question. If the space is insufficient use
other blank spaces or please get additional papers.

21 A function is required to determine the number of isolated vertices (vertices with no incident
edges) in a directed graph.
(a) How can we determine it if we are given the graph in adjacency lists representation? Give
also the pseudocode for the purpose.
(10 marks)
Scan each chain, and count the no. of empty chains.

isolated :=0
For i:=0; I < n; i++ {
If adjlist [i] = null;
isolated++;
}

This is not required in the answer, just for illustration no. of isolated vertices = 2
A: C → B‫ﬧ‬
B: ‫ﬧ‬
C: B →D‫ﬧ‬
D: ‫ﬧ‬
Note: The question is a bit unclear, i.e., the intended meaning of “isolated vertices”, I will consider your
own interpretation in your answer, but it must be sensible. Here it means “no outgoing edges”. To
count the no. of incoming edges, there is no direct info. Same for Question 21 (c).

(b) What is the complexity of the algorithm in (i) (a) above? Justify your answer.
(5 marks)

O(n) as we only have to check n chains to see if they are empty.

(c) What would happen to the complexity of the algorithm in 21 1(a)/(b) above if we are given
the graph in adjacency matrix representation? Justify your answer.
(5 marks)

O(n2)
For each vertex (n vertices) we need to check whether there is an edge to other
vertices (n vertices), if there is none then we increment the no. of isolated vertices.

This is not expected in the answer, just to illustrate the algorithm, no. of isolated vertices = 1
0 1 0 1
0 0 0 0
1 0 0 0
0 0 0 1

5
 Matric No. :…………..

22. (a) A hash table uses a hash function hash(key) = (key+3) % 13 and the table size is 14 12 13. Is
the hash function a good hash function? Why?
(5 marks)
Good
Fast computation,
Modulo base is a prime number

(b) Show the configuration of the hash table using the above hash function in (a) above and
quadratic probing technique to resolve collisions after the insertion of the keys 13, 14, 11, 40,
22, 30 into an initially empty table.
(10 marks)

0 1 2 3 4 5 6 7 8 9 10 11 12
11 13 14 40 30 22

hash (13)=(16+0^2 )𝑚𝑜𝑑 13=3

hash (14)=(17+0^2 )𝑚𝑜𝑑 13=4
hash (11)=(14+0^2 )𝑚𝑜𝑑 13=1
hash (40)=(43+0^2 )𝑚𝑜𝑑 13=4 Collision
hash (40)=(43+1^2 )𝑚𝑜𝑑 13=5
hash (22)=(25+0^2 )𝑚𝑜𝑑 13=12
hash (30)=(33+0^2 )𝑚𝑜𝑑 13=7

22 23 (a) Describe how Boyer-Moore algorithm overcome the weaknesses of Brute-Force

Algorithm for pattern matching.
(5 marks)

Improves the brute-force algorithm by adding two potentially time-saving heuristics, i.e.,
Looking-Glass Heuristic and Character-Jump Heuristic and they have to work together.

occur = 0;
occur++;
return occur;

(b) Given below is the pseudocode for Brute-Force algorithm for pattern matching.

The above algorithm reports only one occurence of the pattern which is the location of the first
ocurrence of the pattern in the text. A pattern may occur several times in a text. Modify the
above pseudocode so the algorithm reports the number of occurrences of the pattern in the
text.
(10 marks)