CS2040 AY2024/2025 Sem2 – Final Assessment

NATIONAL UNIVERSITY OF SINGAPORE

SCHOOL OF COMPUTING
FINAL ASSESSMENT
AY2024/25 Semester 2

CS2040 – Data Structures and Algorithms

26 April 2025 Time allowed: 120 minutes

INSTRUCTIONS TO CANDIDATES
1. Do NOT open the question paper until you are told to do so.

2. This question paper contains THREE (3) sections with sub-questions. Each section has a
different length and different number of sub-questions. It comprises FORTEEN-plus-TWO
(16) printed pages, including this page (and 2 scratch pages).

3. Answer all questions in this paper itself. Answer the questions in Examplify, NOT on this
paper.

4. This is an Open Book Quiz. You can check the lecture notes, tutorial files, problem set files,
CP4 book, or any other books that you think will be useful. But remember that the more time
that you spend flipping through your files implies that you have less time to actually answer
the questions. No code editors or IDEs are allowed.

5. When this Final Assessment starts, please enter your answers into the Exemplify software.

6. The total marks for this paper is 100.

TUTORIAL GROUP

STUDENT NUMBER:
A

For examiners’ use only

Question Max Marks
Q1–10 40
Q11–13 21 (3 × 7)
Q14–16 39 (3 × 13)
Total 100

-1-
 CS2040 AY2024/2025 Sem2 – Final Assessment

NATIONAL UNIVERSITY OF SINGAPORE

SCHOOL OF COMPUTING
FINAL ASSESSMENT
AY2024/25 Semester 2

CS2040 – Data Structures and Algorithms

26 April 2025 Time allowed: 120 minutes

INSTRUCTIONS TO CANDIDATES
1. Do NOT open the question paper until you are told to do so.

2. This question paper contains THREE (3) sections with sub-questions. Each section has a
different length and different number of sub-questions. It comprises FORTEEN-plus-TWO
(16) printed pages, including this page (and 2 scratch pages).

3. Answer all questions in this paper itself. Answer the questions in Examplify, NOT on this
paper.

4. This is an Open Book Quiz. You can check the lecture notes, tutorial files, problem set files,
CP4 book, or any other books that you think will be useful. But remember that the more time
that you spend flipping through your files implies that you have less time to actually answer
the questions. No code editors or IDEs are allowed.

5. When this Final Assessment starts, please enter your answers into the Exemplify software.

6. The total marks for this paper is 100.

TUTORIAL GROUP

STUDENT NUMBER:
A

For examiners’ use only

Question Max Marks
Q1–10 40
Q11–13 21 (3 × 7)
Q14–16 39 (3 × 13)
Total 100

-1-
 CS2040 AY2024/2025 Sem2 – Final Assessment

MCQ: 40 marks, 10 Questions

Q1. A graph G(V,E) is represented as an "adjacency list" with each array entry Adj[u]
being a hash table containing the vertices v for which (u, v)  E. If all edge lookups are
equally likely, what is the expected/average time to determine whether an edge is in
the graph?

a. O(1)
b. O(V) θ
c. O(E) )
d. O(V2) Sime for DES!!

efficient time complexity to traverse the graph breadth-first? /

Q2. Given a complete undirected graph G(V, E) with V vertices and E edges. What is the most
In complete Gruph, the starting
a

connected to all other nosks

Holl is

a. O(V) .

b. O(E) c) 4 ) that mewns BES Visity one dode

,
thee visiol
c. O(V + E) other
d. O(V2)
all modes
immediately
- You
-
don't need to explore ele one
by
one
Q3. Given an adjacency matrix as follows. How many minimum spanning trees do/does the
graph have? bC
an b
0 1 1 a -
3 Vertich
ร
b A = [1 0 1]
( 1 1 0 \
a. 1 2 unmented emph
b. 2 a) x)
32
here
c. 3 3
d. 0 3 ∠

Q4. You are given a maximum binary heap A of N distinct elements, as well as a maximum
binary heap B of M distinct elements. J -
oCNs

You want to create a new maximum binary heap C containing the N+M distinct elements
from A and B. State the time complexity of the most efficient algorithm to do so, in terms of N
and/or M only.

All 3 binary heaps are array-based, as described in lectures.

a.
b.
c.
O(log (N+M)) ?
O(N+M) ?
O((N+M) log (N+M))
)
d. O(NM)

Q5. You are given a binary search tree A of N distinct elements, as well as a binary search tree
B of M distinct elements. It is possible that A and/or B is NOT balanced.
You want to create a new AVL tree C containing the N+M distinct elements from A and B.
State the time complexity of the most efficient algorithm to do so, in terms of N and/or M only.

a. O(log (N+M)) Inorder Traversel A &B to get

a )
X b )
-

b. O(N+M) 2 sorted Sequence in OCNS & OCMS

time respectively
-2-
-

Merce the 2
sequences GCNtm)
INTM/ [-Pecsvey cte an Abyplinaptnla
~ e
「
 CS2040 AY2024/2025 Sem2 – Final Assessment

c. O((N+M) log (N+M))

d. O(NM)
: : :
Q6. A 0-based UFDS of 8 elements, as implemented in lectures using both union-by-rank and
path compression, was initialized as usual into 8 disjoint sets. After some operations, the
underlying parents array currently has the following contents:
[1, 1, 2, 2, 1, 2, 2, 4]

"
.
How many of the following statements are correct:
i. The UFDS currently has 3 disjoint sets. ッ
ii. From initialization to the current state, among all unionSet(x, y) operations performed,

there
exactly 6 of them joined different sets together. X
iii. Currently, there exists at least 2 disjoint sets having the same size (number of
elements in the set). _
8 Sets
-
wory originally

by
a. 0
b. 1 ( x C, ~
now there are 2 sets
c. 2
d. 3X
4
: 6 successful uniors
wore formed
Q7. Consider an unweighted DAG with V vertices and E edges. While we know that we can use

\
BFS or a one‑pass Bellman‑Ford to solve for SSSP in an unweighted DAG, we sometimes need
to compute the longest path from a single source instead.
Let’s try augmenting algorithms that you have learnt in this course.
Which of the following approaches is the best in terms of runtime for finding the longest path
in an unweighted DAG?
!! 6
thisX
d*

→
A. Make use of an O(V+E) algorithm — adapt traversal and/or topological sort and/or one-pass
Bellman-Ford in some way.
B. Make use of an O(E log V) algorithm — adapt MST algorithms in some way. X x
C. Make use of an O((V+E) log V) algorithm — adapt O. or M. Dijkstra’s algorithm in some way.
D. Make use of an O(VE) algorithm — adapt Bellman-Ford in some way.
E. Make use of an O(V2) algorithm — scan the adjacency-matrix to compute chain lengths.X
A )
F. Make use of an O(V3) algorithm — adapt Floyd-Warshall for longest paths in some way.
X
Q8. Let G be a directed graph composed of only two strongly connected components, A and B.
There is only one edge from a vertex in one SCC to a vertex in the other, which is a->b where a
∈ A and b ∈ B.
Now construct an augmented graph G’ by adding three new vertices p, q, and r and the
following additional directed edges:
↑ 0x
- p -> a’ for some a’ ∈ A
- b’ -> q for some b’ ∈ B a > be

£ I
-
- p -> r, r -> q and q -> p
- b’’ -> p for some b’’ ∈ B
How many SCC(s) do/does G’ have?

A. 1 p--
“ ↑
必妙
B. 2 v
C. 3
D. 4
Wait
,
this is
literally one
giant
scl

-3-
「
「
鼠
 CS2040 AY2024/2025 Sem2 – Final Assessment

Q9. Suppose G = (V, E) is a connected, undirected, weighted graph. There exists T, a

shortest‑path spanning tree of G, rooted at source vertex s.
Pick an edge (u, v) in G, and decrease the weight by a constant C > 0. The edge (u, v) can now
have a negative weight.
Which of the following must be true for the new shortest‑path spanning tree T'?
X
A. The tree structure remains the same as T; only the weight of edge (u, v) is smaller. X
B. The tree structure remains the same as T; only the distance to v decreases by C; all other
distances stay the same.
C. A shortest-path spanning tree of G rooted at s still exists; every shortest-path distance
for a vertex reached from s via v decreases.
)
D. A shortest-path spanning tree of G rooted at s still exists; only vertices not reached via v
can now find shorter paths (by rerouting through (u, v)); distances to vertices reached via v
remain unchanged.
E. None of the above are required to be true; T’ may not exist. -
โ A negative cycly my occur
> making
? El
the graph unsolventle
.

This will result

in T not existing
Q10. Referring to the implementation of Floyd-Warshall algorithm in the lecture notes, after at al
completing iteration k=3 (i.e., after using the first 3 vertices as intermediates) for a graph with >
4 vertices, the state of the distance matrix is best described by which option?

A. The distance matrix contains correct values only for pairs where both endpoints are among
the first 3 vertices.
B. Only direct edge weights are used; no intermediate improvements are applied.
(
(F(
C. All shortest paths are finalized; further iterations won’t change the matrix. X
D. Only paths with no intermediates or with one intermediate from the first 3 are computed
correctly.
E. The matrix shows, for each pair of vertices (x, y) among the first 3 vertices, whether there
exists a path from x to y involving vertices from among the first 3 vertices only.
¥
F. Shortest paths using only the first 3 vertices as intermediates are optimal.
ร
25 Min
Analysis: 21 marks, 3 Questions – 7 marks each.
Q11 [7 marks]. It is impossible to have a binary tree containing unique integers with more than
1 node that is both an AVL tree and a valid binary max heap.
True / False? Explain your answer.

Q12 [7 marks]. A UFDS, as implemented in lectures using both union-by-rank and path
compression, has 5,000 elements. Within the UFDS, 2 of the disjoint sets are A and B:
Set A has 1,000 elements with the same representative
Set B has only 10 elements, and its representative has a rank of 3
Claim: It is possible that unionSet(A, B) places the representative of set A under the
representative of set B.

a) Is the claim True/False?

b) Give your rationale for your answer to (a).

Q13 [7 marks]. A weighted connected undirected graph G is made up of 2 trees A and B, as

well as 4 additional edges. This means that, if A and B contain N and M vertices respectively,
then G contains N+M vertices and exactly N+M+2 edges.
Each of the 4 additional edges (u, v) is such that u is a vertex in A, while v is a vertex in B.

For a tree E ニレート

-4- ,
面
 Scie .Itis possila nodes both
the Hop
with roof , this free may
,
per mode
being the is a

and ArL

(12) True ·

for the A have

then
to rock boer
It is
possible representative of set a

To create a setA where representative is of rank) :

Union 2 distine elements together first

Union the roof of this Set 199 times With distinct elements

A B
(3 .

"

" "

~ 3
6

_
N= =4

m =
5

(a) Fake .
It could include more than 1 of the additional edges

(b) If all the additional edges lighter then Within A & B all of them
are existing edges ,

Woul be included in the MST

.
」
 CS2040 AY2024/2025 Sem2 – Final Assessment

Trees A and B each contains at least 4 vertices, and do not share any vertices between them.
The weights of ALL the N+M+2 edges in G are distinct.

Claim: The Minimum Spanning Tree of G will include exactly one of the 4 additional edges
mentioned above.

a) Is the claim True/False?

b) Give your rationale for your answer to (a).

Structured: 39 marks, 3 Questions – 13 marks each.

Q14 [13 marks]. Range of Orange

Ivan has N (which can be very large) orange slices, each having a volume (positive floating
point number with no fixed precision). Ivan takes out a sharp knife and makes C cuts on the
oranges.
When Ivan makes a cut, he takes the slice with the largest volume and splits it into two equal
volumes (which add up to the original slice’s volume). After each cut, you are to output the
range of the oranges’ volume, i.e. Vlargest_slice – Vsmallest_slice.

You are given the integer C, as well as a nonempty array A which contains the N volumes, one
for each orange slice.
Example: C = 5, A = [8.0, 4.0, 6.0] N ==3
the 5 outputs in sequence are: 2.0 1.0 2.0 2.0 1.0
because
after 0 cuts: 8.0 4.0 6.0 range : 2.0 but not in output
after 1 cuts: 4.0 4.0 4.0 6.0 range : 2.0
after 2 cuts: 4.0 4.0 4.0 3.0 3.0 range : 1.0
after 3 cuts: 4.0 4.0 3.0 3.0 2.0 2.0 range : 2.0
after 4 cuts: 4.0 3.0 3.0 2.0 2.0 2.0 2.0 range : 2.0
after 5 cuts: 3.0 3.0 2.0 2.0 2.0 2.0 2.0 2.0 range : 1.0
Design a most efficient algorithm to output the C ranges, stating clearly any data structures
required where they matter.
A correct O(N + C log C) algorithm will score full marks, while a O(N log N + C log C) algorithm
will score “high” but not full marks.

Q15 [13 marks].

TransferWise, a global money transfer company, needs a system to compute processing fee
differences between banks. Each of the N banks charges a fee, but the exact fees are not known.
However pairwise information about the differences between some bank’s fees are known (e.g.,
Bank A is $5 cheaper than Bank B).

Design a system to answer customer queries about fee differences between any two banks.
Assume all queries can be answered based on the given pairwise information.

Sample data, queries and answers are provided below:

Consider 3 banks OSBC, MBS, HCBC along with the following information.
K1. Transferring through OSBC costs 4 dollars more than transferring through MBS.

-5-
 CS2040 AY2024/2025 Sem2 – Final Assessment

K2. Transferring through OSBC costs 3 dollars less than transferring through HCBC.

Query 1: How much more expensive it is to transfer through MBS than OSBC?
Answer: -4 dollars. (From K1)

Query 2: How much more expensive it is to transfer through MBS than HCBC?
Answer: -7 dollars. (-4-3, where -4 is because of K1 and -3 is because of K2)

Ensure you clearly indicate and answer these three parts:

1. Model the given scenario as a graph.

tree
2. Assume the number of pairwise information available is N-1, design an algorithm to
_
answer Q queries efficiently.

3. Assuming the number of pairwise information is available is M, where M is much higher

than (N-1), design an algorithm to answer Q queries efficiently.

For this problem, you can assume that the transfer fees are not uniform, i.e., the relative
difference in transfer fees may vary across different pairs of banks.

Q16 [13 marks]. Static vs. Current Electricity

Tom has K (which can be very large) steel plates numbered 0 to K-1 (in that order) in a line
from left to right. All plates do not touch each other. Initially, a plate is connected to either
one power source or to nothing.

There are only two power sources – a positive source, and a negative source. The positive
source always remains positive, and the negative source always remains negative.

Subsequently, wires are secured between 2 plates so that electricity can pass between them:
- Current electricity flows along paths from the positive to the negative source
- However, if there is a path to only one source (but not both), then current does NOT
flow, but the plate becomes positively or negatively charged instead (static electricity).

Hence, each plate takes one of four states:

N Neutral – Plate is not in any way connected to any power source
+ charged – The only source that the plate is connected to is the positive source
- charged – The only source that the plate is connected to is the negative source
C Current – There is current flowing through some part of the circuit this plate is
connected to (to be precise, current may not be flowing through this plate itself).

Design an algorithm for each of the 2 operations:

Init(int K, int[] P, int[] N) – There are K plates. P, N are lists of plate
numbers that are connected to the positive, negative source respectively. Perform any
initialization on data structures to support the Wire operations.

Wire(int L, int R) – Secure a wire between plate L and plate R and return the state
of the plates on both sides of the wire after it is secured (Think about it, the states of both
plates will always be the same after the wire is secured…).

-6-
 CS2040 AY2024/2025 Sem2 – Final Assessment

For full credit, both operations should run correctly, and the Wire operation should run as
efficiently as possible (“not far from O(1) time” on average) while the Init operation should
support the given implementation of Wire as efficiently as possible.
Example:
Init(6, {1}, {5, 4}) <-- the metal plates have states [‘N’, ‘+’, ‘N’, ‘N’, ‘-’, ‘-’] in sequence
Wire(3, 2) returns ‘N’ <-- states are still [‘N’, ‘+’, ‘N’, ‘N’, ‘-’, ‘-’] though wire secured
Wire(1, 2) returns ‘+’ <-- states are now [‘N’, ‘+’, ‘+’, ‘+’, ‘-’, ‘-’] as plates 2,3 are + charged
Wire(3, 4) returns ‘C’ <-- states are now [‘N’, ‘C’, ‘C’, ‘C’, ‘C’, ‘-’] as plates 1 to 4 are
connected to a circuit with current flowing through
Wire(0, 1) returns ‘C’ <-- states are now [‘C’, ‘C’, ‘C’, ‘C’, ‘C’, ‘-’] as plate 0 is ALSO
connected to a circuit with current flowing through, even though current doesn’t take a
path through plate 0.

-7-
14
. Initialize a
MinHemp & Mayheap with the volumes in

array A [OCNs ]

Looping through [tires : 20 (Clog 3

1 Extract May from May Hemp

bith
.

2
. Divide the value by 2 and insert if twise into the
Maxheep & MinHap
.
3 Return Maxherp
. peek 1s -

MinHerp .
peek (
 5
( .

SMBS

the banks there

Betren
HCBC are 2 edges
HCBC world huve
OSB( >
-

1. Model the problem as a weighted directed graph a weight

of -3

vertises : Banks
Eclyes : A directed ealge represents the fee difference letron any two banks
e.

g HCBC + OSB) mans

transferring through HSBs costs 4 more

2
. Since the number of eless are N this is free and there should be

]
, graph a an

unique path between every vertices

When a regarding the fee difference between2 banks are asked :

query
- Start DFS from both podes
of the other bank

T
-

Only one DFS will beach the Vertey

Track the the from the to the destination
-

weight along path source vertex

Vertex and sum it
up
~
The start Vertey would be the (sum of the edge weights) more expensive ‰

[
than the bank at the end
process a verty Vertel

.Use
3
Dijstra to fins the Shortest path between the start Vertey & and Vertof
the to the
Find cost of
travelling end vertex
-

correct idea to me Diskton

2
2 The tree
correct idea
graph is a

1. Run DAS from the sturting vetery to usp

mantein ACT where Adxy cost difference

[
=
an
nury
between X & the stating Viney DFS
siurher
traversing set feeos feecus the

(
ele We n ,
=

For !
each query <A , By
Answer = feecky-teo [B]

3
. Dikstin
「
、
。
 ⑥ ① ②③④ ⑤
- —
— —
-

16
'
.

"
…

This problem can be solved with an UFDS both structure

Fnit (int K int C > P1 in + ( > NS

,

~ Initiative an array of size K , mapping the inity of ech

plate to a

Minim
State

=
'
-
Label the rost as
-

NS
-

Initialize a UFES ofk disjoint Sets

wore (L , RI

Acroti
perform both L R

#Acti
unionset &
-

on

-
If ACD: :
"
tI 1 ALR ] ユ =
"
N
"
: +
Chure Accs all the was to

Urse verse
Vairset V
, R

*[ firket (v1) :

攻能品希鳴 たい ee
Wire (r , R)

"
-

IF AC findsetcu ) ) : :
"

t
"
θ A Cfinlselcr , ) : :
“
f
"
or
"

N :

newstate :
"
+ 11

Uniose + (2
,
R )
# [findset &WCT only the roof since it
= new state Je deed to update represents
return new State the whole set

-
If AffindSec] =:
- "@ A[finGate] = -"-" or "N" ,

"
newffrty
-
に

Unioset (L , R]
New Steff
# [findset(2) J =
retur new Stete

:
Vise versi
十
In UFDS :

every plate belongs to one connected component

-
each connected component has a
single root

When you do findset ex) always get the root of X's component

Δ
you
~

- We can store only ONE state for

wholethe set
for You store the roof
-
You do not need to store the state individually every plate >
- it only at

-
All plates
in the
set query
their roof's
State
Statesroots updates the
updating entire component logically