FIT3155 SAMPLE EXAM PAPER
FIT3155 SAMPLE EXAM PAPER
INSTRUCTIONS
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 4/7 on a question after spending 15 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 7 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.
When needed, math notations can be typed in plain text. As some random example PN 10 log(i) + 2i can be typed as sum_{i=1}^N (10*log(i)+2^i/(i+3)).
Answers to the sample question will not be provided up front. This is mainly to get you to attempt these questions first without peeking at the answers. Once you have attempted these questions, send your solutions you want to clarify to via email or as a ‘private’ post on the Ed forum, and you will receive prompt feedback of your attempt.
Page 2 of 22
FIT3155 SAMPLE EXAM PAPER
Question 1 (6 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.
Page 3 of 22
FIT3155 SAMPLE EXAM PAPER
(Page intentionally left blank for working space)
Page 4 of 22
FIT3155 SAMPLE EXAM PAPER
浙大学霸代写 加微信 cstutorcs
Question 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.
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) Briefly describe the show stopper rule employed in Ukkonen’s algorithm for constructing a suffix tree. Justify why it is correct.
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.
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 (6 marks)
What is the amortized complexity of inserting n elements into a binomial heap. Justify your answer
Page 11 of 22
FIT3155 SAMPLE EXAM PAPER
(Page intentionally left blank for working space)
Page 12 of 22
FIT3155 SAMPLE EXAM PAPER
Programming Help
Question 6 (6 marks)
Write a pseudocode describing the merge function that takes two Fibonacci heaps as inputs and returns a merged Fibonacci heap as output.
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)
For any B-tree with a mininum degree of t, and containing N elements, what is the minimum possible height of the B-tree? (Show the working of how you arrived at your answer.)
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 (6 marks)
Write pseudocode for Miller-Rabin’s randomized method for primality testing.
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 (5 marks)
For the string abcabcdabcbcde, using the LZ77 method of encoding, list all the encoding tuples that LZ77 will generate, assuming the dictionary and lookahead buffer sizes are both infinitely long.
In your answer, list the tuples in a human readable form (without converting them into a binary stream). For example, the first tuple that LZ77 produces for the above string is: [0, 0, ’a’].
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)
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.
Page 21 of 22
FIT3155 SAMPLE EXAM PAPER
程序代写 CS代考 加微信: cstutorcs
(Page intentionally left blank for working space)
Page 22 of 22 End of Exam
FIT3155 SAMPLE EXAM PAPER