CP5602 Assignment
SP2, Townsville
Due by Friday November 1, 2019 (no later than 5:00pm)
Aim: This assignment is designed to help you improve your critical thinking and problem solving
skills.
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. Use the master method to give tight asymptotic bounds for the following recu
ences (if the maste
method cannot be applied give your argument):
(a) T (n) = 8T (n/2) + n2.
(b) T (n) = 8T (n/2) + n2 lg n.
[2 marks]
2. Using Figure 6.3 as a model, illustrate the operation of BUILD-MAX-HEAP on the a
ay
A = 〈10, 6, 27, 121, 44, 16, 6, 32, 49〉.
[1 mark]
3. Using Figure 6.4 as a model, illustrate the operation of HEAPSORT on the a
ay
A = 〈25, 3, 12, 5, 7, 27, 20, 18, 34, 45〉.
[1 mark]
4. Using Figure 7.1 as a model, illustrate the operation of PARTITION on the a
ay
A〈3, 19, 9, 25, 12, 8, 37, 14, 33, 2, 16, 17〉.
[1 mark]
1
5. Consider inserting the keys 21, 22, 32, 10, 25, 28, 17, 38, 9 into a hash table of length m = 11 using
open addressing with the auxiliary hash function h′(k) = k. Illustrate the result of inserting these
keys
(a) using linear probing,
[1 mark]
(b) using quadratic probing with c1 = 1 and c2 = 3, and
[1 mark]
(c) using double hashing with h1(k) = k and h2(k) = 1 + (k mod (m− 1)).
[1 mark]
6. 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
[3 marks]
7. 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).
[3 marks]
8. What is an optimal Huffman code for the following set of frequencies? a:1, b:1, c:2, d:3, e:5, f:8,
g:13, h:21, i:34.
[1 marks]
9. Consider a directed graph G, where its adjacency-matrix is:
q r s t u v w x y z
q XXXXXXXXXX
XXXXXXXXXX
s XXXXXXXXXX
t XXXXXXXXXX
u XXXXXXXXXX
v XXXXXXXXXX
w XXXXXXXXXX
x XXXXXXXXXX
y XXXXXXXXXX
z XXXXXXXXXX
2
(a) Show the d and π values that result from running
eadth-first search on graph G, using vertex
q as the source.
[1 mark]
(b) Show how depth-first search works on the graph G.
[1 mark]
(c) Show the parenthesis structure of the depth-first search.
[1 mark]
(d) Show the parenthesis structure of the depth-first search on graph G.
[1 mark]
(e) Determine whether or not the graph G is strongly connected.
[1 mark]
3