[SOLVED] Cs5800: algorithms assignment 5

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 differences between the two approaches of implementing a binary search tree 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