COMP3001 Design and Analysis of Algorithms

Examination Cover Sheet

School of Electrical Engineering, Computing and Mathematical Sciences

Discipline of Computing - Curtin University

COMP3001 Design and Analysis of Algorithms

Final Assessment - Semester 1/2020

Total Mark: 100

Time allowed: 4 hours (start to finish)

Assessment Availability: 1pm Monday 15 June 2020 to 1pm Tuesday 16 June 2020

Test mode: Online test, open-book: you are allowed to access your hand-written notes,

lecture slides, textbooks, and printed and electronic materials in your possession.

CONDITIONS

• The test must be completed by yourself only. No one else should do this test for

you. Any attempts to compromise the system are strictly prohibited. Any breaches of

this policy will be considered cheating and appropriate action will be taken as per

University policy.

• You are prohibited from communicating with people other than the unit

coordinator/lecturer and the tutors during the test.

• You are prohibited from providing information about your work and your test to

others during and outside your test within two days. Some students may sit in the test

after you.

• You must complete and submit the "Student Declaration Form".

• Some students sitting the test will be invited to an online interview. In the interview,

students will be asked to explain their solutions and demonstrate their knowledge for

randomly selected questions. Students will be shown the questions, as well as their

written answers.

INSTRUCTION

• This assessment consists of four questions: QUESTION ONE to QUESTION FOUR

of different types, with a total of 100 marks. Attempt ALL questions.

• You can submit your answers multiple times during the assessment, but only the last

submission would be used for marking.

• You are allowed to use (i) n^2 for n2 and n_2 for n2, (ii) floor(x) for ⎣x⎦ and ceiling(x)

for ⎡x⎤, (iii) Big Theta(n) for Θ(n) and Big Omega (n) for Ω(n), (iv) lg x for log2x, log

x for log10x, and log_b(a) for logba, (v) >= for ≥, <= for ≤, and != for ≠.

End of Semester 1, 2020

COMP3001 Design and Analysis of Algorithms

Page 1 of 6

QUESTION ONE (Total: 25 marks).

Q1 a) (5 marks). Consider the following algorithm to print out all the keys in a binary

search tree in an inorder tree walk.

INORDER-TREE-WALK (x)

if x ≠ NIL then

INORDER-TREE-WALK (left[x])

Print key[x]

INORDER-TREE-WALK (right[x])

The recurrence of the running time complexity of the algorithm is T(n) = T(k) + T(n-k-1) + 1,

where k is the number of nodes in the left subtree and n-k is the number of nodes in the right

subtree.

Use induction to prove that the recurrence is O(n).

Q1 b) (Total: 10 marks). It is known that no comparison-based sorting algorithm has a

running time complexity less than Ω(n lg n).

(i) (5 marks). Suppose that your friend A claims to have a comparison-based sorting

algorithm that satisfies a recurrence T(n) = 3T(n/4) + cn. Is your friend’s claim

reasonable? Justify your answer.

(ii) (5 marks). Suppose that your friend B claims to have a comparison-based sorting

algorithm that satisfies a recurrence T(n) = 5T(n/4) + cn. Would you use your friend’s

algorithm over merge sort for large n? Justify your answer.

Hint: Solve the recurrence functions in (i) and (ii) to justify your answers. You don’t need to

check for the regularity condition in your solution.

Q1 c) (4 marks). Without using Stirling’s formula, prove that log(n!) is O(n log n). You need

to give the values of n0 and c.

Hint: log (a * b) = log a + log b.

n! = n * (n-1) * (n-2) * … * 2 * 1.

End of Semester 1, 2020

COMP3001 Design and Analysis of Algorithms

Page 2 of 6

Q1 d) (Total: 6 marks).

for (i ! 0 to n) do

for (j ! 0 to n) do

if (A[i] = B [j]) then

return (TRUE)

(i) (2 marks). What does the algorithm do?

(ii) (2 marks). What is the best case upper bound running time complexity of the algorithm?

Justify your answer.

(iii) (2 marks). What is the worst case upper bound running time complexity of the

algorithm? Justify your answer.

END OF QUESTION ONE

End of Semester 1, 2020

COMP3001 Design and Analysis of Algorithms

Page 3 of 6

QUESTION TWO (Total: 26 marks).

Q2 a) (Total: 10 marks). Suppose you were to run a marathon from a point A to another

point B along a given route. In the marathon, you were allowed to stop and get water as many

times as needed. However, since each stop takes time, you want to minimize the total number

of stops as possible. Assume you know that you can run for up to k km after every stop.

Further, you were given information about the locations and distances between water stations

along the route. Let S = (s1, s2, …, sn) be the set of n water stations along the route, and D =

(d1, d2, …, dn) be the set of their corresponding distances from point A to the station. In

other words, si is the water station with distance di from point A. Note that d1 < d2 < … < dn,

and assume the distance between neighbouring stations is at most k kms, and the distance

between the last station and point B is k km. For example, consider for k = 15 kms and D =

(5, 10, 13, 16, 20, 24, 27, 31, 36, 40, 45, 50). The optimal sequence of stops is (s3, s7, s10,

s12), i.e., 4 stops.

(i) (6 marks). Write the pseudo code of your algorithm to determine a set of water stations

si that minimizes the total number of stops.

(ii) (2 marks). Explain the idea of your algorithm, and use the given example for k=12 km

to illustrate the working of your algorithm.

(iii) (2 marks). Analyse the time complexity of your algorithm as a function of n, where n is

the total number of water stations along the route fro A to B. Also, argue why your

algorithm is the most efficient possible.

Q2 b) (Total: 8 marks). Consider d sequences of elements. The elements in each sequence

are already sorted in increasing order, and there are in total n elements. Design an O(n lg d)

algorithm to merge all the sequences into one sorted sequence (in increasing order). As an

example, for four sequences: (2, 5, 7), (4, 6), (1, 8), and (3, 8, 9), we have d = 4 and n = 10.

Your algorithm should produce a sorted sequence (1, 2, 3, 4, 5, 6, 7, 8, 8, 9).

(i) (6 marks). Describe your algorithm. Show that the time complexity of your algorithm is

O(n lg d). You can assume d is in a power of 2, e.g., 4, 8, 16. You are NOT required to

write the pseudocode of your algorithm.

(ii) (2 marks). Show how your algorithm merges the d=4 sequences in the example.

Q2 c) (8 marks). Consider an array of records, A, whose keys to be sorted only consist of F’s

and M’s, for Female and Male respectively. For example, array A may contain the a list of

keys A=(F M M M F F F M F M F M M F F M).

• Write the pseudo code of a O(n) algorithm to sort the array in place, i.e., using memory

storage of no more than constant size in addition to that of the array.

• Illustrate the working of your algorithm using the example as its input.

• Analyse the time complexity of the algorithm and show that its complexity is O(n).

END OF QUESTION TWO

End of Semester 1, 2020

COMP3001 Design and Analysis of Algorithms

Page 4 of 6

QUESTION THREE (Total: 17 marks).

Q3 a) (Total: 6 marks).

(i) (3 marks). Working modulo 11, list all spurious hits that the Rabin-Karp matcher

encounters in the text T = 3142531653586797 when looking for pattern P = 53.

(ii) (3 marks). Given t3 = 3 for T = 3142531653586797, show in detail how Rabin-Karp

matcher computes t4.

Q3 b) (2 marks). Consider the following BF_String_Matcher (T, P) algorithm (from Lecture

Slide).

BF_String_Matcher(T, P)

1 n = length [T]

2 m = length[P]

3 for s = 0 to n - m

4 do if P[1..m] = T[s+1..s+m]

5 then shift s is valid

For T =

A. 3 comparisons between characters in T and P.

B. 14 comparisons between characters in T and P.

C. 24 comparisons between characters in T and P.

D. 21 comparisons between characters in T and P.

E. None of the answers are correct.

Q3 c) (Total: 9 marks). Data compression.

A file has alphabets {A, B, C, D, E}, where A has frequency 32, B has frequency 64, C has

frequency 8, D has frequency 16, and E has frequency 8.

(i) (3 marks). Give the Huffman code for each of the alphabets.

(ii) (3 marks). How many bits are needed to represent the alphabets in the file? Explain

your answer.

(iii) (3 marks). Use the Shannon’s entropy to show that the computed Huffman code is

optimal. Give the details of you computation.

END OF QUESTION THREE

End of Semester 1, 2020

COMP3001 Design and Analysis of Algorithms

Page 5 of 6

QUESTION FOUR (Total: 32 marks).

Q4 a) (4 marks). Explain if the following statement is True or False. Your explanation must

include detailed computation of the number of scalar multiplications of the two alternative

full parenthesizations.

Consider the matrix chain multiplication problem with p0=1000, p1=100, p2=20, p3=10, and

p4=1000. A full parenthesization (((A1A2)A3)A4) requires more scalar multiplications than

another full parenthesization ((A1(A2A3))A4).

Q4 b) (Total: 10 marks). Consider the following incomplete tables generated by the

dynamic programming algorithm (discussed in the lecture) for solving the matrix chain

problem, where the four consecutive matrices are A, B, C, and D.

(i) (2 marks). If matrices A and D have dimensions A = 6×4, and D = 3×2, what are

the dimensions of matrices B and C? Explain your answer.

(ii) (6 marks). Calculate m[1, 4] and s[1, 4]. Show your detailed calculations.

(iii) (2 marks). Show the optimal bracketing of the matrices in part (i) that produces

the number of multiplications in m[1, 4].

0 ? 42 18 4

108 36 0 3

72 0 2

0 1

1 2 3 4 m

j

i

? 2 3 4

1 2 3

1 2

1

1 2 3 4 s

j

i

End of Semester 1, 2020

COMP3001 Design and Analysis of Algorithms

Page 6 of 6

Q4 c) (Total: 8 marks). Consider 5 items with weights w = (2, 6, 2, 4, 5) and values v =

(40, 40, 25, 30, 50). For example, the weight of item 1 is 2 and its value is 40, while item 5

has a weight of 5 and a value of 50.

(i) (6 marks). Use the 0/1 Knapsack dynamic programming algorithm (discussed in the

lecture) to fill out the following Table P, assuming the total weight of the selected items

is at most 9 units. In your answer, you can represent the entry at row i and column k in

Table P as P[i, k]. For example, P[5, 9] = x and P[3, 7] = y.

i / k 0 1 2 3 4 5 6 7 8 9

5 x

4

3 y

2

1

(ii) (2 marks). Use Table P to determine what items should be selected to achieve maximum

values. Explain your answer

Q4 d) (Total: 10 marks). Consider the following parallel search algorithm that requires

CRCW model.

Algorithm Parallel_Search (x, A[1 .. n])

index ! -1

forall Pi do in parallel

if A[i] = x then

index ! i

endif

endfor

(i) (4 marks). Modify the algorithm to find each index in array A that stores x. Use array B

to store the indices. Hint. B[i] = -1 means A[i] ≠ x.

(ii) (2 marks). Is the modified algorithm cost optimal? Justify your answer.

(iii) (2 marks). Compute the speedup of the modified algorithm.

(iv) (2 marks). Does the modified algorithm also require CRCW model? Explain your

answer.

END OF EXAMINATION