CMPT 280– Intermediate Data Structures and Algoirthms

Assignment 2

Total Marks: 53

1 Submission Instructions

• Assignments must be submitted using Moodle.

• Responses to written (non-programming) questions must be submitted in a PDF file, plain text file

(.txt), Rich Text file (.rtf), or MS Word’s .doc or .docx files. Digital images of handwritten pages

are also acceptable, provided that they are clearly legible, and in a common format such as JPEG or

PNG.

• 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.

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<I which extends and implements the abstract class ArrayedBinaryTree280<I (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<I has already been done,

but there is more to do.

Firstly, there are several methods in ArrayedBinaryTreeWithCursors280<I which are defined but

not implemented; these are marked with //TODO comments. You must implement these methods.

Secondly, since ArrayedBinaryTreeWithCursors280<I implements the interfaces Dict280<I and

Cursor280<I, 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<I

– you must add them. The interfaces Dict280<I and Cursor280<I 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<I. 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<I.

There is already one inherited from ArrayedBinaryTree280<I. 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<I ) 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<I

abstract class, and the partially completed ArrayedBinaryTreeWithCursors280<I class for Question 11. The ArrayedTree280<I 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