Question

a) Please Select All That Apply:

What are the possible applications of Priority Queue?     

• CPU Scheduling
• All queue applications where priority is involved.              
• kernel of NT for keep track of process information

b) Running Time Analysis: Give the tightest possible big-O upper bound for the worst case running time for each operation listed below in terms of N. Assume no duplicate values and that you can implement the operation as a member function of the class – with access to the underlying data structure, including knowing the number of values currently stored. For array-based implementations, assume that the array is large enough – does not need to be grown: Finding minimum in a Priority Queue implemented with a binary search tree.

c)

When it comes to "Locality" in splay trees, mark the all correct answers:

i) Accessing k nodes in m >= n accesses in AVL trees is O(mlogn) time.

ii) The idea of splaying is to apply "Locality" principle - if an item is accessed, it is likely to be accessed again soon.

iii) In splaying, when k distinct items are accessed in m >= n accesses will improve the height of the k nodes to be accessed in O(mlogk) times instead of O(mlogn) times as in AVL trees.

iv) Accessing k nodes in m >= n accesses in Splay trees is amortized O(mlogn) time

Answer 1

A. CPU scheduling

All queue applications where priority is involved.

B. Give the tightest possible big-O upper bound for the worst case running time for each operation listed below in terms of N

  Assume no duplicate values and that you can implement the operation as a member function of the class – with access to the underlying data structure, including knowing the number of values currently stored

  For array-based implementations, assume that the array is large enough – does not need to be grown.

C. i) Accessing k nodes in m >= n accesses in AVL trees is O(mlogn) time.

ii) The idea of splaying is to apply "Locality" principle - if an item is accessed, it is likely to be accessed again soon.

I hope it helps.