Recently, the discovery of a new data structure WONDER HEAP was announced. A WON
ID: 2247710 • Letter: R
Question
Recently, the discovery of a new data structure WONDER HEAP was announced. A WONDER HEAP has the same functionality and worst case behaviour as a binary heap except for DELETE MAX, which is implemented in O(log log n) (instead of O(log n) for binary heaps) a. Give 4 algorithms/data structures from CSC 505 which could be improved by WONDER HEAP. b. Do you believe in the existence of WONDER HEAPS? Justify your answer. c. Give a one-sentence definition of i) worst-case running time, ii) tractable problems, iii) the Subset Sum Problem.Explanation / Answer
Solution :
Binary heap :
Insert : O(log n)
Delete_max : O(log n)
Find_max : O(1)
Remove : O(log n)
Wonder heap :
Insert : O(log n)
Delete_max : O(log log n)
Find_max : O(1)
Remove : O(log n)
a) Here we need to find data structures or algorithms that uses Heap data structure and delete_max function is used in it.
- Prim's minimum spanning tree algorithm
- Dijkstra's shortest path algorithm
- Heap short
- Huffman coding
- Priority queue
Note that these algorithms are the one that uses binary heap data structures and its performance can be improved if delete_min can be performed in O(log log n ) time.
in question it is written to list algorithms or data structures that you have studied in class. So check the list and only write down those, that are in CSC 505 course.
B)
No . If delete_min can be done in O(log log n) time then it means that tree can be heapified in O(log log n) time. Which is not possible.
If it was possible then inserting in heap would also be O(log log n).
So Wonder heap data structure is not possible.
C)
Worst case running time : Maximum time that can be taken by the algorithm is cosindered as worst case running time of algorithm.
tractable problems : problem that is solved by a polynomial time algorithm is tractable problem.
i.e the uppder bound of algorithm is polynomial.
subset sum problem : Is there a non empty subset of a set, such that sum of elements of subset is 0.?
This problem is called subset sum problem.
If you have any doubts then you can ask in comment section.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.