## Description

Instructions:

• The assignment is due at the time and date specified. Late assignments will not be accepted.

• You must work on all the problems and write the solutions by yourself! Finding solutions to homework

problems on the web, or by asking students in and outside the course is strictly prohibited. This would be

defeat the purpose of learning by doing the assignment.

• You must submit typed solutions. You may use plain text or a word processor like Microsoft Word or LaTeX

for your submissions. You may hand-sketch and scan any diagrams that you support your answer.

• If you are not comfortable with Word or Latex, please solve these problems by hand before devoting time to

typing them. Do not waste precious time investigating typesetting up front!

You are provided some starter code with this assignment, that you are expected to use and extend in

some of these questions. The code is complete with some JUnit tests. If you are not familiar with setting

up a Java environment that works with JUnit, please see the video on blackboard on how to work with

IntelliJ. You are not required to use this IDE.

1. (30 points)

A priority queue has the following operations:

1. add(item,priority)

2. getItemWithHighestPriority()

The priority is assumed to be a non-negative integer. The item can be anything in general. The items

may be orderable (comparable).

A priority queue is normally implemented using a binary heap. A binary heap can be efficiently

implemented using an array as a complete binary tree. Both the above operations on a binary heap can be

implemented in O(log n) worst case time. To summarize, both operations move several array elements

around to maintain the heap structure (operations often called “percolate”). See Chapter 6 of the book

for more details.

As an implementation detail, each node of a binary heap (i.e. each element in the underlying array) stores directly the item and its priority (instead of a pointer/reference to the actual data). Storing

everything in the heap itself avoids indirection, which improves cache performance of the heap contents.

1

A useful, but non-standard operation is changePriority(item,new priority). This operation can be

used to increase or decrease an existing item’s priority. Once the item is found in the binary heap, this

operation can be implemented in O(log n) time. The problem is finding this item efficiently: the binary

heap is arranged by priority, not item. Thus searching a binary heap by item amounts to a linear-time

search of the underlying array, which causes the change priority operation to run in linear time.

Provide a design that implements a priority queue using an ordinary binary heap, supports all operations

including changePriority(item,new priority) in O(log n) worst case time. Your answer must consist of any

algorithms and data structures you use, and must prove that the overall running time is within the specified

bounds. Your answer must specify everything so that an average graduate student in CS 5800 should be

able to implement your idea by reading only your answer, and assuming knowledge of how a binary heap

is normally implemented.

2. (30 points)

You are given a binary search tree T without any balancing mechanisms that stores n items. Due to

repeated additions and deletions, the tree has become lopsided/unbalanced, which is having an adverse

effect on its efficiency.

• Provide an efficient way to create a binary search tree T

0

that has the same data as T, that also

does not have any balancing mechanisms, and yet implements search in O(log n) time after it has

been fully created. You may assume that once T

0

is created, it is not changed (alternatively, if it is

changed, this process can be repeated to get back the efficient run times). Analyze your algorithm

in space and time.

• You are provided two implementations for such a “normal” binary search tree. Add code to both

implementations wherever applicable to implement this feature. You may add any additional tests

as well, but we will not grade them.

Please submit both answer and code for this question.

3. (30 points)

• Provide an algorithm that checks whether two binary search trees are the same. Two binary search

trees are the same if they contain the same data, and they have the same structure (i.e. if you draw

them on paper they will look identical). Analyze your algorithm in time and space.

• Provide an algorithm that will create an identical copy (i.e. same as above) of a binary search tree.

Analyze your algorithm in time and space.

• Implement both these algorithms in the given code (both implementations).

Please submit both answer and code for this question. You may implement all questions in one code

base, instead of separating them for different questions.

4. (10 points)

Briefly discuss the differences between the two approaches of implementing a binary search tree provided

and extended by you, in terms of how algorithms are implemented, ease of use and understanding, efficiency,

etc.

2