Description
2 Background 2.1 Timing Analysis Questions 1 through 8 in Section 3 concern timing analysis. These questions are not programming questions and should be submitted in one of the acceptable document formats listed above. 2.2 Arrayed Trees Question 9 is about a bounded binary tree implementation. You should remember binary trees from CMPT 115 (or similar course) – they are trees in which each node has at most two children. What you probably didn’t know is that binary trees can be stored using an array, rather than a linked structure. In such an array, the contents of the root node are stored in offset 1 of the array (offset 0 is unused). The contents of the children of the node whose contents are stored at offset i are stored at offset 2i and 2i + 1, respectively. Thus, the left child of the root is at offset 2 × 1 = 2, the right child of the root is at offset 2 × 1 + 1 = 3, the left child of the left child of the root is at offset 2 × 2 = 4, and so on. The parent of the node whose contents are at offset i, is at offset i/2 (integer division). Thus, the parent of node at offset 7 is at offset 3. Example 1 Here is the array representation of a tree storing the elements 1 through 10, in no particular order. The array – 7 1 4 3 9 10 2 8 5 6 is a representation of the tree: 7 1 3 8 5 9 6 4 10 2 Note that we do not allow any unused entries in the array between used ones. All the data items in the array are stored contiguously. This means that we can represent only a particular subset of binary trees with this representation. Namely, it is the set of trees where all levels except possibly the last level are complete (full) and the nodes in the bottom level are all as far to the left as possible. You might be thinking that this is too restrictive and not very useful because we can’t represent all binary trees with this data structure. However, as we will see on future assignments, this array-based tree data structure is highly useful and efficient as a basis for implementing certain other important data structures. Also note that if we read off the items from left to right in each level of the tree, starting from the top level, we get the items in the same order as they appear in the array. Page 2 3 Your Tasks Question 1 (): Suppose the exact time required for an algorithm A is given by the function TA(n) = 280n + 21n 2.5(log2 n) + 12n 3 + 101 + 42√ n (a) (2 points) Which of the following statements are true? 1. Algorithm A is O(log n) 2. Algoirthm A is O(n) 3. Algoirthm A is O(n 3 ) 4. Algoirthm A is O(2 n ) (b) (1 point) Give the correct time complexity for A in big-Θ notation. Question 2 (): For each of the following functions, give the tightest upper bound chosen from among the usual simple functions listed in Section 4.5 of the course readings. Answers should be expressed in big-O notation. (a) (1 point) f1(n) = n log2 n + n 4 log2 n + 2 n 4200 (b) (1 point) f3(n) = 0.8n 3 + n 2 log2 n 2 + log2 (2 n ) (c) (1 point) f2(n) = 4n 0.5 + log2 n n + 1234 Question 3 (): If possible, simplify the following expressions. Hint: See slide 11 of topic 4 of the lecture slides! (a) (1 point) O(n 2 ) + O(log n) + O(n log n) (b) (1 point) O(2 n ) · O(n 2 ) (c) (1 point) 42O(n log n) + 18O(n 3 ) (d) (1 point) O(n 2 log2 n 2 ) + O(m) (yes, that’s an ‘m’, not a typo; note that m is independent of n) Question 4 (5 points): Consider the function f(n) = 2n 3 + 5n 2 + 42. Use the definition of big-O to prove that f(n) ∈ O(n 3 ). Question 5 (5 points): Consider the function g(n) = 12n 2 log n 2 + 6n + 42. Use the definition of big-O to prove that g(n) ∈ O(n 2 log n 2 ). Question 6 (3 points): Consider again the function g(n) = 12n 2 log n 2 + 6n + 42. Use the definition of big-O to prove that g(n) is not in O(n). Question 7 (): Consider the following Java code fragment: // Print out all ordered pairs of numbers between 1 and n for ( i = 1; i <= n; i ++) { for ( j = 1; j <= n; j ++) { System . out . println ( i + ” ,␣ ” + j ) ; } } (a) (3 points) Determine the exact number of statements (i.e. the statement counting approach) that are executed when we run this code fragment as a function of n. Show all of your calculations. (b) (1 point) Express the function you obtained in part a) in big-Θ notation. Page 3 Question 8 (): Consider the following pseudocode: Algorithm roundRobinTournament ( a) This algorithm generates the list of matches that must be played in a round – robin pirate – dueling tournament ( a tournament where each pirate duels each other pirate exactly once ). a is an array of strings containing names of entrants into an tournament n = a . length for i = 0 to n -1 for j = i +1 to n -1 print a [ i ] + ” ␣ duels ␣ ” + a [ j ] + ” ,␣ Yarrr !” (a) (5 points) Determine the exact number of statements (i.e. use the statement counting approach that are executed by the above algorithm. Express your answer as a function of n. Show all your calculations. (b) (1 point) Express the function you obtained in part a) in big-Θ notation. Question 9 (20 points): Your task is to write a Java class called ArrayedBinaryTreeWithCursors280 which extends and implements the abstract class ArrayedBinaryTree280 (provided in the lib280-asn2.tree package as part of lib280-asn2). This week’s lab will also talk more about array-based trees. Methods to be Implemented Some of the work of implementing ArrayedBinaryTreeWithCursors280 has already been done, but there is more to do. Firstly, there are several methods in ArrayedBinaryTreeWithCursors280 which are defined but not implemented; these are marked with //TODO comments. You must implement these methods. Secondly, since ArrayedBinaryTreeWithCursors280 implements the interfaces Dict280 and Cursor280, there are several missing methods required by these interfaces that also needed to be implemented. The headers for these methods are not yet present in ArrayedBinaryTreeWithCursors280 – you must add them. The interfaces Dict280 and Cursor280 and their ancestors (yes, they have ancestor interfaces!) document what these methods are supposed to do. Until the missing methods are added, the compiler will complain on line 15 that there are unimplemented abstract methods inherited from the interfaces. This is normal, and will disappear once all required methods have been added. Hint: You can automatically generate the missing method headers in IntelliJ by pressing CTRL-i. Implementation Requirements and Hints You may not modify any of the existing code in the provided ArrayedBinaryTreeWithCursors280.java file, but you can add to it. You may also not modify any other files within lib280-asn2. There is already a regression test included in ArrayedBinaryTreeWithCursors280. Your completed implementation of the arrayed binary tree should pass the given regression test. If all the regression tests are successful, the only output should be: Regression test complete. Hint: You don’t need to declare an array instance variable to hold the data items in ArrayedBinaryTreeWithCursors280. There is already one inherited from ArrayedBinaryTree280. You should look at the other inherited instance variables too! Page 4 Hint: one of your first major decisions after adding the appropriate method headers for the inherited abstract methods will be to start implementing the insert method and decide where the new element should be inserted. If you think about it, there’s really only one place it can go… Hint: The algorithm for deleting an element is to replace the element to be deleted by the right-most element in the bottom level of the tree, then delete the right-most element in the bottom level of the tree. Reminder: the elements of the items array (defined in the abstract class ArrayedBinaryTree280 ) represent the nodes of the tree. You are storing the contents of nodes in the array. There is no node class. It is very important that the contents of the root are stored in offset 1 and we don’t use offset 0 of the array, otherwise, the given formulae for finding the child or parent of a node at offset i will not work correctly. 4 Files Provided lib280-asn2: A copy of lib280 which includes solutions to assignment 1, the ArrayedBinaryTree280 abstract class, and the partially completed ArrayedBinaryTreeWithCursors280 class for Question 11. The ArrayedTree280 interface can be found in the lib280-asn2.tree package. 5 What to Hand In You must submit the following files: Q1-8.doc/docx/rtf/pdf/txt – your answers to questions 1 through 10. Digital images of handwritten pages are also acceptable, provided that they are clearly legible. ArrayedBinaryTreeWithCursors280.java – your arrayed binary tree implementation and regression test. Page 5
