FIT3155 SAMPLE EXAM PAPER
FIT3155 SAMPLE EXAM PAPER
INSTRUCTIONS
• This exam is worth 60 marks.
• Answers to each question should be in the space DIRECTLY BELOW the questions and (if
required) on the blank page overleaf of each question.
• Script book may be used if ADDITIONAL SPACE is required for answering these questions
General exam technique
Some students throw marks away by not attempting ALL questions. Let us say you get 5/7 on a question after spending 15 minutes on it. Spending another 10 minutes on the same question gets at most 2 marks. On the other hand, if you spend the same amount of time on a new question, you might get another 5 marks, or more.
It is a good technique to first answer questions you are very confident of, before answering the rest.
Answer the question that is asked. Where necessary justify your answer with a clear and concise explanation, without being too wordy.
Write neatly and use either a black or a blue colored pen. Strictly avoid using a pencil or pens of other colors.
Best of luck!
Page 2 of 22
FIT3155 SAMPLE EXAM PAPER
Question 1 (5 marks)
A string str[1..n] has a 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 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 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.
5
Page 3 of 22
FIT3155 SAMPLE EXAM PAPER
(Page intentionally left blank for working space)
Page 4 of 22
FIT3155 SAMPLE EXAM PAPER
Question 2 (5 marks)
Describe the good suffix (pattern shift) rule in Boyer-Moore’s algorithm. Reason why this shift-rule never shifts the pattern incorrectly past (and hence never overlooks) an exact match in the reference text.
5
Page 5 of 22
FIT3155 SAMPLE EXAM PAPER
(Page intentionally left blank for working space)
Page 6 of 22
FIT3155 SAMPLE EXAM PAPER
Question 3 (5 marks)
What is the worst-case space complexity of representing a suffix tree for any string str[1..n]. Justify your answer.
5
Page 7 of 22
FIT3155 SAMPLE EXAM PAPER
(Page intentionally left blank for working space)
Page 8 of 22
FIT3155 SAMPLE EXAM PAPER
Question 4 (7 marks)
In union-by-size implementation of the disjoint set data structure, each disjoint set can be conceptually described as a tree of nodes/elements where each node/element in the disjoint set points to its immediate parent node/element, and the root node/element r of that tree represents the ‘leader’ (denoting the equivalence class) of the nodes/elements in that tree.
For any resultant tree using union-by-size with root node r, show that: size(r) ≥ 2height(r)
where size(r) is the number of elements in the tree rooted at r, and height(r) is the largest number of hops required (i.e., edges traversed) to reach the node r from any of the leaf nodes in the tree rooted at r.
7
Page 9 of 22
FIT3155 SAMPLE EXAM PAPER
(Page intentionally left blank for working space)
Page 10 of 22
FIT3155 SAMPLE EXAM PAPER
Question 5 (7 marks)
What is the amortized complexity to insert n elements into a binomial heap. Justify your answer
7
Page 11 of 22
FIT3155 SAMPLE EXAM PAPER
(Page intentionally left blank for working space)
Page 12 of 22
FIT3155 SAMPLE EXAM PAPER
Question 6 (6=3+3 marks)
For any B-tree with a branching factor of t containing n elements:
1. What is the minimum possible height of the B-tree? (Show the working of how you
arrived at your answer.)
2. What is the maximum height of the B-tree? (Show the working of how you arrived at your answer.)
6
Page 13 of 22
FIT3155 SAMPLE EXAM PAPER
(Page intentionally left blank for working space)
Page 14 of 22
FIT3155 SAMPLE EXAM PAPER
Question 7 (6 marks)
Transform the multiplication of any two 2n-bit (non-negative) integers u and v into a problem that can be solved using the divide-and-conquer approach.
6
Page 15 of 22
FIT3155 SAMPLE EXAM PAPER
(Page intentionally left blank for working space)
Page 16 of 22
FIT3155 SAMPLE EXAM PAPER
Question 8 (5=2+3 marks)
(i) Does Huffman encoding always yield prefix-free code words for the characters it is encoding? If yes, why? If no, why not?
(ii) Write the Elias code for the integer 1023. (No explanation necessary; simply write down the resultant code.)
5
Page 17 of 22
FIT3155 SAMPLE EXAM PAPER
(Page intentionally left blank for working space)
Page 18 of 22
FIT3155 SAMPLE EXAM PAPER
Question 9 (7 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.)
Subject to the constraints:
Maximize z=x+y
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.
7
Page 19 of 22
FIT3155 SAMPLE EXAM PAPER
(Page intentionally left blank for working space)
Page 20 of 22
FIT3155 SAMPLE EXAM PAPER
Question 10 (7 marks)
In a flow network with positive capacities, prove that the minimum capacity of a cut is equal to the maximum feasible flow in that network.
7
Page 21 of 22
FIT3155 SAMPLE EXAM PAPER
(Page intentionally left blank for working space)
Page 22 of 22 End of Exam
FIT3155 SAMPLE EXAM PAPER