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)
This question relates to Gusfield’s Z-algorithm.
Recall that the Z-algorithm takes as input a string S[1 . . . n] and, for each position k > 1, computes the length (Zk) of the longest substring that matches the prefix of the string.
Consider the Z-algorithm scenario depicted below, where we are computing the Z-value at position k – which we denote Zk – using the previously computed value of Zk left+1 at position k left + 1. In this scenario Zk left+1 is strictly less than right k + 1. Note that (left, right) are positions such that left < k right and Zleft = right left + 1.
How many explicit character matches are necessary to compute Zk? Justify your answer with a clear explanation and be sure to state any definitions and properties you use in your answer.
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 su x (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)
This question relates to Ukkonen’s linear time su x tree construction algorithm.
Suppose that you applied rule 3 to complete the su x extension j in some phase i + 1 of the algorithm. Prove that
all the remaining extensions in phase i + 1 (j + 1, j + 2, . . . , i + 1) will be performed using rule 3. (Note: You may assume the input string is S[1 . . . n].)
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 Hu↵man 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