1. Questions on Big-Oh, Theta, etc.: (a) Give the standard Theta (e()) form for each of...

 

Transcribed Image Text:

1. Questions on Big-Oh, Theta, etc.: (a) Give the standard Theta (e()) form for each of the following func- tions. (E.g., 2n+3 would be written as e(n).) [10 marks] 1. 2n+3n2(logn)3+2 2. 7n logn+2n+1234 3. 5n log(n) 4. (2n+7+5)(n+1) 5. 21n (log n) +2n4 + 2n (logn)" (b) Put the following Theta classes in order of increasing growth (e.g.. increasing running times). [10 marks] e(logn), (n2), O(nlogn), (1), e (ing) (3"), (n!), log e(n) Remark: It is more important that you get the order right between the first four classes listed than that the last four are placed correctly. (c) Following are some big-Oh relationships. For each, give witnesses no and c that can be used to prove the relationship. [9 marks] 1. 7n is O(n) 2. 4+3 is O(22) 3. 5n logn is O(n). 19 36 47 11 32 42 65 27 (a) A BST for questions 2(b)-(d). (b) The BST for question 2(e). Figure 1: An empty BST for questions 2(b), 2(c), and 2(d) on left and the BST for question 2(e) on right. 2: Binary Search Trees (BSTs) (a) Insert the following items into a BST, in the following order: [11, 5, 10, 21, 49, 35, 8, 46]. Show the resulting tree. [6 marks] (b) Put the following items into the BST in Figure la [28, 37, 13, 48, 56, 9, 50, 62]. Is this always unique for a fixed array and a fixed BST? Justify your answer. [6 marks] (c) Mark all non-balanced nodes in the BST in Figure la. Justify your answer. [6 marks] (d) In the BST you got in the part (b) delete the following items, in the following order: [9, 50, 28] (So when deleting 50, 9 is not in the tree any-more...). Show how the BST changes in each deletion. [6 marks] (e) Consider the AVL Tree in Figure 1b. Delete the number 11 to the tree. Note that you might need to do some rotations to preserve the AVL property. [6 marks] 3: Express your answers for the following two questions in Big-Oh notation. Justify your answers. (a) Show an upper bound on the running time of the following function. [5 marks] void fnA (int[] array, int n) { int counter 1; int sum = 0; while (counter < n) { for (int i=0; i < n; i++) { } sum += array[i]; counter += 1; (b) The following is a sorting algorithm that uses the same merge routine as merge sort. Show an upper bound on its running time. [10 marks] Recall that the merge (A, low, mid, high) routine call joins the sorted segments A [low...mid] and A[mid+1...high] into a new sorted list, then copies it into A [low...high]. void sort2 (int[] array, int n) { int chunk-1; while (chunk < n) { for (int low 0; low chunk < n; low + 2*chunk) { } merge (array, low, low+chunk-1, low+2*chunk-1); chunk chunk*2; } 5. Consider the following function fn. 1 23456789 int fn(n) { if (n 0) { } } 10 } return 1; int sum = 0; for (int i=0; i 1. Questions on Big-Oh, Theta, etc.: (a) Give the standard Theta (e()) form for each of the following func- tions. (E.g., 2n+3 would be written as e(n).) [10 marks] 1. 2n+3n2(logn)3+2 2. 7n logn+2n+1234 3. 5n log(n) 4. (2n+7+5)(n+1) 5. 21n (log n) +2n4 + 2n (logn)" (b) Put the following Theta classes in order of increasing growth (e.g.. increasing running times). [10 marks] e(logn), (n2), O(nlogn), (1), e (ing) (3"), (n!), log e(n) Remark: It is more important that you get the order right between the first four classes listed than that the last four are placed correctly. (c) Following are some big-Oh relationships. For each, give witnesses no and c that can be used to prove the relationship. [9 marks] 1. 7n is O(n) 2. 4+3 is O(22) 3. 5n logn is O(n). 19 36 47 11 32 42 65 27 (a) A BST for questions 2(b)-(d). (b) The BST for question 2(e). Figure 1: An empty BST for questions 2(b), 2(c), and 2(d) on left and the BST for question 2(e) on right. 2: Binary Search Trees (BSTs) (a) Insert the following items into a BST, in the following order: [11, 5, 10, 21, 49, 35, 8, 46]. Show the resulting tree. [6 marks] (b) Put the following items into the BST in Figure la [28, 37, 13, 48, 56, 9, 50, 62]. Is this always unique for a fixed array and a fixed BST? Justify your answer. [6 marks] (c) Mark all non-balanced nodes in the BST in Figure la. Justify your answer. [6 marks] (d) In the BST you got in the part (b) delete the following items, in the following order: [9, 50, 28] (So when deleting 50, 9 is not in the tree any-more...). Show how the BST changes in each deletion. [6 marks] (e) Consider the AVL Tree in Figure 1b. Delete the number 11 to the tree. Note that you might need to do some rotations to preserve the AVL property. [6 marks] 3: Express your answers for the following two questions in Big-Oh notation. Justify your answers. (a) Show an upper bound on the running time of the following function. [5 marks] void fnA (int[] array, int n) { int counter 1; int sum = 0; while (counter < n) { for (int i=0; i < n; i++) { } sum += array[i]; counter += 1; (b) The following is a sorting algorithm that uses the same merge routine as merge sort. Show an upper bound on its running time. [10 marks] Recall that the merge (A, low, mid, high) routine call joins the sorted segments A [low...mid] and A[mid+1...high] into a new sorted list, then copies it into A [low...high]. void sort2 (int[] array, int n) { int chunk-1; while (chunk < n) { for (int low 0; low chunk < n; low + 2*chunk) { } merge (array, low, low+chunk-1, low+2*chunk-1); chunk chunk*2; } 5. Consider the following function fn. 1 23456789 int fn(n) { if (n 0) { } } 10 } return 1; int sum = 0; for (int i=0; i