DIDATES
This is a OPEN book examination.
All submitted work must be done individually without consulting someone
Section in a separate book……
Semester 2, 2005 Page X of XY
This information is only necessary if
Semester 1- Practice, 2021
SEAT NUMBER: _______________________________
comp2123 Data Structures and Algorithms FULL NAME: _______________________________
SID: _______________________________
2 hours
10 minutes
Duration: 2h30m Reading time: 10 mins
Computer Science EXAMINATION
EXAM WRITING TIME:
the paper is NOT TO BE REMOVED
READING TIME: FROM EXAM ROOM.
EXAM CONDITIONS:
comp2123 final exam (s1, 2021)
Faculty of ECONOMICS & BUSINESS
CONFIDENTIAL EXAM PAPER
ECON2002 – INTERMEDIATE MICROECONOMICS
This paper is not to be removed from the exam venue.
else’s help, in accordance with the University’s “Academic Dishonesty and Plagiarism” policies.
MATERIALS PERMITTED IN THE EXAM VENUE:
MATERIALS TO BE SUPPLIED TO STUDENTS:
INSTRUCTIONS TO STUDENTS:
Type your answers in your text editor (Latex, Word, etc.) and convert it into a pdf file.
Submit this pdf file via Canvas. No other file format will be accepted. Hand- written responses will not be accepted.
Start by typing you student ID at the top of the first page of your submission. Do not type your name.
Submit only your answers to the questions. Do not copy the questions.
Do not copy any text from the permitted materials. Always write your answers
in your own words.
For examiner use only:
Problem
1
2
3
4
Total
Marks
Out of
10
10
20
20
60
Dennis\Desktop\Exam Typing
Page 2 of 4
page 1 of 5
N
Practice Exam
Problem 1.
a) Analyze the time complexity of this algorithm.
[3 marks]
comp2123 final exam (s1, 2021)
1: 2: 3: 4: 5:
6:
def Compute(A) result ← 0
for i = 0; i < n; i + + do if A[i] > i then
result ← result + A[i] return result
b) Solve the following recursion:
T(n/2) + O(1)
c) We are planning a board games event and we’re using one of the shelves in my office to store the games. Unfortunately the shelf only has a certain amount of space S, so we need to carefully pick which games we want to bring. Every game takes some space si and has a fun factor fi that indicates how much fun it is to play that game (for 1 ≤ i ≤ n).
We want to maximize the amount of fun we’ll have, so we want to maximize the sum of the fun factors of the games we pick (i.e., max ∑ fi), while
picked game i
making sure that the games fit on my shelf, so the sum of the space the games we pick take should be at most S (i.e., ∑ si ≤ S). For simplicity, you can
picked game i
assume that all fi, si, and S are all distinct positive integers.
The strategy of PickLargest is to always pick the game with the highest fun factor until my shelf is full: it sorts the games by their fun factor fi in decreasing order and adds a game when its required space is less than the remaining space on the shelf.
[3 marks]
[4 marks]
T(n)= O(1)
for n > 1 forn=1
1: 2: 3: 4: 5: 6: 7: 8:
9:
def PickLargest(all fi and si, S)
currentSpace ← 0
currentFun ← 0
Sort games by fi and renumber such that f1 ≥ f2 ≥ … ≥ fn fori←1;i≤n;i++do
if currentSpace + si ≤ S then
currentSpace ← currentSpace + si ◃ Pick the ith game currentFun ← currentFun + fi
return currentFun
Show that PickLargest doesn’t always return the correct solution by giving a counterexample.
page 2 of 5
comp2123 final exam (s1, 2021)
Problem 2. Consider the following edge weighted undirected graph G:
B5C
10 2
A74F
6
3
D1E
Your task is to:
a) Compute a minimum spanning tree T of G. List the edges in T.
b) Indicate the order in which the edges are added by Kruskal’s algorithm.
(You do not have to explain your answer.)
[7 marks] [3 marks]
page 3 of 5
comp2123 final exam (s1, 2021)
Problem 3. Consider the Dynamic Matrix ADT for representing an matrix A = {ai,j}n
that supports the following operations:
• create(): creates a 1 × 1 matrix where a1,1 = 0.
• set/get(i, j): set or get the value of the entry ai,j.
• increase-size: If the current size of the matrix is n×n, increase it to n+1×n+1
such that the new entries are set of 0. In other words, A becomes A′ such that
a′ =ai,j if1≤i,j≤n,anda′ =0otherwise. i,j i,j
Your task is to come up with a data structure implementation for the Dynamic Matrix ADT that uses O(n2) space, where n is the size of the matrix, and create, set, get take O(1) and increase-size takes O(n) time. Remember to:
a) Describe your data structure implementation in plain English. b) Prove the correctness of your data structure.
c) Analyze the time and space complexity of your data structure.
[8 marks] [7 marks] [5 marks]
i,j=1
page 4 of 5
comp2123 final exam (s1, 2021)
Problem 4. Let G be a connected undirected graph on n vertices. We say that two distinct spanning trees T and S of G are one swap away from each other if |T ∩ S| = n − 2; that is, T and S differ in only one edge.
For two distinct spanning trees T and S we say that R1, R2, . . . , Rk form a swapping sequence from T to S if:
1. R1 = T,
2. Rk =S,and
3. for any 1 ≤ i < k, the trees Ri and Ri+1 are one swap away from each other
Your task is to design a polynomial time algorithm that given G and two spanning trees T and S of G, constructs a minimum length swapping sequence. Remember to:
a) Describe your algorithm in plain English.
b) Prove the correctness of your algorithm.
c) Analyze the time complexity of your algorithm.
[8 marks] [7 marks] [5 marks]
page 5 of 5