CP5602 Assignment
SP2, Townsville
Due by Friday October 26, 2018 (no later than 5:00pm)
Aim: This assignment is designed to help you improve your critical thinking and problem solving skills, as
well as your information literacy skills (i.e. the ability to select and organise information and to communicate
it effectively and ethically).
Requirements, Method of Submission, and Marking Criteria:
• Answer all of the following questions in a single document. Each question should begin on a new page.
• Include your name on the first page. Include list of references (if any) for each question with prope
in-text citations.
• Show all your work.
• Upload your solution to the Assignment Box, located in the subject’s site.
1. Searching Problem:
Input: an a
ay A[1..n] of n elements and a value v.
Output: an index i such that A[i] = v or the special value NIL if v does not appear in A.
Assuming that a
ay A is sorted (in ascending order):
(a) Write pseudo-code for an iterative binary search algorithm, looking for v. Show that the running
time of your algorithm is Θ(lg n).
[1 mark]
(b) Write pseudo-code for a recursive binary search algorithm, looking for v. Show that the running time
of your algorithm is Θ(lg n).
[1 mark]
2. Draw the 13-entry hash table that results from using the hash function h(i) = (3i + 5) mod 13 to hash
the keys 14, 42, 15, 81, 27, 92, 3, 39, 20, 16, and 5, assuming collisions are handled by:
(a) separate chaining;
[1 mark]
(b) linear probing.
[1 mark]
(c) quadratic probing (up to the point where the method fails).
[1 mark]
(d) Using the secondary hash function h′(i) = 11 − (i mod 11).
[1 mark]
1
3. Insert entries with keys, 2, 7, 3, 12, 5, 20, 14, 6, 11, 8, 15, 17, 1, 19, 23, 14 (in this order), into an empty:
(a) heap.
[1 mark]
(b) binary search tree.
[1 mark]
(c) AVL tree.
[1 mark]
(d) (2, 4) tree.
[1 mark]
4. Consider the set of keys, 2, 15, 7, 33, 21, 5, 14, 17, 19, 11, 9, 41, 31, 71, 52, 67, 29, 27, 49. Using
prune-and-search paradigm by picking the first element as pivot, determine the 9th element of these keys
when they are sorted in ascending order.
[1 mark]
5. Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is (7, 10, 5, 18,
20, 40, 10, 15). That is:
matrix dimension
———– —————
A1 7 × 10
A2 10 × 5
A3 5 × 18
A4 18 × 20
A5 20 × 40
A6 40 × 10
A7 10 × 15
[2 marks]
6. Determine an LCS (Longest Common Subsequence) of sequences A = (1, 1, 1, 0, 0, 0, 1, 0, 1) and B =
(0, 1, 0, 1, 0, 0, 1, 1).
[2 marks]
7. Show all the steps for performing any of the following algorithms for matching the pattern ‘belabela’ in
the text ‘bellisalabelabelbelabela’.
(a)
ute-force
[1 mark]
(b) Boyer-Moore
[1 mark]
(c) Knuth-Mo
is-Pratt
[1 mark]
2
8. Consider a directed graph G, where its adjucency list is:
Vertex Adjacent Vertices
————– ————————–
A B, C, D, E
B D, E
C A, B, E
D B, C, F
E A, C, F
F A, C, E
(a) Determine whether or not the graph G is strongly connected.
[1 mark]
(b) Draw the transitive closure of graph G (show graphs GA, GB, GC , GD, GE , GF after each step of the
Floyd-Warshall algorithm).
[1 mark]
3
1.
(a)
Algorithm iterative_binary_search(A, v)
left = A[0];
right=A[length[A] – 1];
while left <= right
mid = (left + right) / 2;
if v == A[mid]
return mid;
else if v < A[mid]
right = mid – 1;
else
left = mid +1;
return Nil
The length of A is n, then let’s apply recursive binary search to it, the length of the next a
ay we deal with is about n/2, and next one after that is about n/4 and so on. Therefore, the time complexity for the recursive binary search applied on A, is T(n) = T(n/2) + c, c is a constant.
Let’s use the Master method, then we can see a=1, b=2, f(n)=c, and thus ===1. Since f(n) = c = Θ ()= Θ (1), case 2 applies.
The solution to this recu
ence will be T(n)= Θ (lgn)= Θ (lgn). Therefore, the running time
of the algorithm is Θ(lg n).
(b)
Algorithm recursive_binary_search(A, left, right, v):
if right >= left
mid = left + (right – left) / 2;
if A[mid] == v
return mid;
else if A[mid] > v
return recursive_binary_search(A, left, mid-1, v);
else
return recursive_binary_search(A, mid+1, right, v);
else
return Nil;
The length of A is n, then let’s apply recursive binary search to it, the length of the next a
ay we deal with is about n/2, and next one after that is about n/4 and so on. Therefore, the time complexity for the recursive binary search applied on A, is T(n) = T(n/2) + c, c is a constant.
Let’s use the Master method, then we can see a=1, b=2, f(n)=c, and thus ===1. Since f(n) = c = Θ ()= Θ (1), case 2 applies.
The solution to this recu
ence will be T(n)= Θ (lgn)= Θ (lgn). Therefore, the running time
of the algorithm is Θ(lgn).
2.
The hash value of each key:
h(14)= (3*14+5) mod 13=8
h(42)= (3*42+5) mod 13=1
h(15)= (3*15+5) mod 13=11
h(81)= (3*81+5) mod 13=1
h(27)= (3*27+5) mod 13=8
h(92)= (3*92+5) mod 13=8
h(3)= (3*3+5) mod 13=1
h(39)= (3*39+5) mod 13=5
h(20)= (3*20+5) mod 13=0
h(16)= (3*16+5) mod 13=1
h(5)= (3*5+5) mod 13=7
(a)
Put the keys under the cells, their hash value should match the index of the cell above.
The hash table is shown in Figure 1.
XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX12
14
27
92
15
39
5
20
42
81
3
16
Figure 1: Hash table, using separate chaining collision resolution.
(b)
Process of generating the hash table using linear probing collision resolution.
XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX12
14
XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX12
42
14
XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX12
42
14
15
XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX12
42
81
14
15
XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX