End of Semester 1, 2020 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 =
and P = , the algorithm requires 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 
