Programs must be written in Java.

If you are using Eclipse (or similar development environment), do not submit the workspace (project). Hand in only those files identified in Section 5. Export your .java source files from the workspace and submit only the .java files.

No late assignments will be accepted. See the course syllabus for the full late assignment policy for this class.

Background

Timing Analysis

Questions 1 through 10 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.

Arrayed Trees

Question 11 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.

Question 1 ():

Suppose the exact time required for an algorithm A is given by:

T_A(n) = 1234n + 19n³ + 99 + 27n^5.5(log₂n) + 42√n

(a) 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³)
4. Algoirthm A is O(2n )
(b)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)  f₁(n) = 12nlog₂n + n²log₂n + 2ⁿ/4200

(b)  f₃(n) = n²log₂n² + 8n³ + log₂(2ⁿ)

(c)  f₂(n) = 4n^0.5 + log₂n/n + 1234

Question 3 ():

If possible, simplify the following expressions. Hint: See slide 11 of topic 4 of the lecture slides!
(a) O(n²) + O (log n) + O (n log n)
(b) O(2ⁿ) O(n²)
(c) 42O (n log n) + 18O(n³)
(d) O (n²log₂ n²) + O (m) (yes, that's an ‘m', not a typo; note that m is independent of n)

Question 4: Consider the function f (n) = 2n³ + 5n² + 42. Use the definition of big-O to prove that f (n) ? O(n3).

Question 5 :

Consider the function g(n) = 12n2 log n2 + 6n + 42. Use the definition of big-O to prove that g(n) ∈ O(n² log n²).

Question 6 :

Consider again the function g(n) = 12n² log n² + 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) 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) Express the function you obtained in part a) in big-Θ notation.

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 a 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) 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) Express the function you obtained in part a) in big-Θ notation.

Question 9 ():

Consider the following pseudocode:

Algorithm moveDown (a) a is an array of numbers int i = 1
n = a.length
while (a[i] > a[2*i] || a[i] > a[2*i+1]) && 2*i+1 < n) if a[2*i] >= a[2*i +1]
largest = 2*i

else

temp = a[i]

largest = 2*i + 1

a[i] = a[largest] a[largest] = temp i = largest
(a) Determine the exact number of statements (i.e. use the statement counting approach) that are executed during one iteration of the while loop in the worst case. Your answer should be expressed in terms of n (the length of the array) Show all calculations.

(b) Determine the exact number of times the while loop executes in the worst case.

(c) Determine the exact number of statements executed in the worst case by the whole algorithm.

(d) Identify an Active Operation

(e) Determine the exact number of times the active operation is executed.

(f) Express the answers to parts c) and e) in big-O notation.

Question 10:

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.