FIT3155 SAMPLE EXAM PAPERFIT3155 SAMPLE EXAM PAPER
FIT3155 SAMPLE EXAM PAPERINSTRUCTIONS
ˆ This exam is worth 60 marks.
General exam technique
Some students throw marks away by not attempting ALL questions. Let us say you are likely
to get 3/6 on a question after spending 10 minutes on it. Spending another 10 minutes on the
same question gets at most 3 marks. On the other hand, if you spend the same amount of
time on a new question, you might get another 6 marks.
It is a good technique to first answer questions you are very confident of, before answering
the rest. In other words, answering questions serially during an exam can be a suboptimal
approach.
Answer the question that is asked. Where necessary justify your answer with a clear and
concise explanation, without being too wordy.
When needed, math notations can be typed in plain text. As some random example∑N
i=1
(
10 log(i) + 2
i
i+3
)
can be typed as sum_{i=1}^N (10*log(i)+2^i/(i+3)).
Page 2 of 22
FIT3155 SAMPLE EXAM PAPERQuestion 1 (6 marks)
A string str[1..n] has a full period of p, if and only if str[1...p] is the shortest prefix in str
that repeats k times, such that k×p = n (where n, p, k are all positive integers). Otherwise,
the string is not fully periodic.
Example: str[1..24] = abcdabcdabcdabcdabcdabcd has a period p = 4, since the prefix
abcd repeats k = 6 times.
Write pseudocode describing an efficient algorithm that accepts any input string str[1..n]
and outputs its full period if it has one, or output “string not periodic” if it does not have
one.
ˆ You are free to assume any named algorithm taught in this unit (eg. Z-algorithm) as
an in-built function call within your pseudocode without having to describe its logic.
6
Page 3 of 22
FIT3155 SAMPLE EXAM PAPER(Page intentionally left blank for working space)
Page 4 of 22
FIT3155 SAMPLE EXAM PAPERQuestion 2 (6 marks)Prove that the shift-rule Knuth-Morris-Pratt employs is always a ‘safe shift’. That is, during
each shift, KMP never overlooks an exact match in the reference text.
6
Page 5 of 22
FIT3155 SAMPLE EXAM PAPER(Page intentionally left blank for working space)
Page 6 of 22
FIT3155 SAMPLE EXAM PAPERQuestion 3 (6 marks)Reason the time complexity to invert a given Burrows-Wheeler Transform (BWT) of a string
S[1 . . . n]$. In reasoning this, specify clearly any extra space (i.e. auxiliary space) you are
assuming when arriving at your characterization of the complexity, beyond the space require
to store the BWT you are inverting and the string S being generated from that process.
6
Page 7 of 22
FIT3155 SAMPLE EXAM PAPER(Page intentionally left blank for working space)
Page 8 of 22
FIT3155 SAMPLE EXAM PAPERQuestion 4 (6 marks)Briefly describe the show stopper rule employed in Ukkonen’s algorithm for constructing
a suffix tree. Justify why it is correct.
6
Page 9 of 22
FIT3155 SAMPLE EXAM PAPER(Page intentionally left blank for working space)
Page 10 of 22
FIT3155 SAMPLE EXAM PAPERQuestion 5 (6 marks)
1. For the string abcabcdabcbcde, using the LZSS method of encoding, list all the encoding
tuples that LZSS will generate, assuming the dictionary and lookahead buffer sizes are
both infinitely long. (In your answer, Format-1 tuple should be written in the form
[1,] and Format-0 tuple is written in the form: [0,,]).
2. The following tuples were derived using the LZ77 method of encoding:
[0,0,p]
[0,0,q]
[0,0,r]
[3,3,s]
[7,6,t]
Decode these LZ77 tuples to regenerate the original string.
6
Page 11 of 22
FIT3155 SAMPLE EXAM PAPER(Page intentionally left blank for working space)
Page 12 of 22
FIT3155 SAMPLE EXAM PAPERQuestion 6 (6 marks)Describe the steps that Miller-Rabin’s randomized method uses to test the primality of any
given integer n.
6
Page 13 of 22
FIT3155 SAMPLE EXAM PAPER(Page intentionally left blank for working space)
Page 14 of 22
FIT3155 SAMPLE EXAM PAPERQuestion 7 (6 marks)
Your lecture on amortized analysis introduced an idealized k-bit binary-counter data struc-
ture that supports an increment (by 1) operation, starting with all the k bits of the counter
initialized to 0.
For this data structure, reason the amortized complexity of an increment operation. You
are free to use any method of amortization to reason this complexity.
6
Page 15 of 22
FIT3155 SAMPLE EXAM PAPER(Page intentionally left blank for working space)
Page 16 of 22
FIT3155 SAMPLE EXAM PAPERQuestion 8 (6 marks)
Write a pseudocode describing the merge function that takes two Fibonacci heaps as inputs
and returns a merged Fibonacci heap as output.
6
Page 17 of 22
FIT3155 SAMPLE EXAM PAPER(Page intentionally left blank for working space)
Page 18 of 22
FIT3155 SAMPLE EXAM PAPERQuestion 9 (6 marks)For any B-tree with a minimum degree of t, and containing N elements, what is the lower
bound on the minimum possible height of the B-tree? (Type the working of how you arrived
at your answer.)
6
Page 19 of 22
FIT3155 SAMPLE EXAM PAPER(Page intentionally left blank for working space)
Page 20 of 22
FIT3155 SAMPLE EXAM PAPERQuestion 10 (6 marks)
Solve the following optimization problem using the simplex method. (You can answer this
using either the tableau simplex method or the algebraic simplex method.)
Maximize z = x + y
Subject to the constraints:
x + 2y ≤ 4
4x + 2y ≤ 12
−x + y ≤ 1
x ≥ 0, y ≥ 0
At the end of your solution, write the optimal value of z and the corresponding values of
(x, y) that resulted its maximization.
6
Page 21 of 22
FIT3155 SAMPLE EXAM PAPER(Page intentionally left blank for working space)
Page 22 of 22
End of Exam