Continue on my unfinished doc, I have answered 7 marks, got 13 marks left now.Please write the steps and explanations of your solutions clearly.Thank you very much.
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 proper 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 array 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 array 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) brute-force [1 mark] (b) Boyer-Moore [1 mark] (c) Knuth-Morris-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="" array="" 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="" recurrence="" 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 array 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 recurrence 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. 0 1 2 3 4 5 6 7 8 9 10 11 12 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. 0 1 2 3 4 5 6 7 8 9 10 11 12 14 0 1 2 3 4 5 6 7 8 9 10 11 12 42 14 0 1 2 3 4 5 6 7 8 9 10 11 12 42 14 15 0 1 2 3 4 5 6 7 8 9 10 11 12 42 81 14 15 0 1 2 3 4