The selection sorting algorithm, for sorting a collection $X$ of ordered elements, can be described by the following pseudocode:
while $X$ has elements that have not yet been output: output the smallest remaining element of $X$
Write an expanded version of pseudocode for this algorithm that makes explicit use of the data structure operations allowed by a priority queue to make the algorithm efficient. Your answer should use an operation to initialize a priority queue from a given collection of elements, and another operation to find and remove the minimum-value element from the priority queue. Do not describe how to implement these operations.
Many balanced binary tree data structures maintain a collection of elements, subject to element insertion and element deletion operations that both take worst-case time proportional to the logarithm of $n$, the number of elements in the tree. Find a potential function $\Phi$ for which (without changing the data structure, only its analysis) the amortized time per deletion is $O(1)$, while the amortized time per insertion is still only $O(\log n)$. Show how this choice of $\Phi$ gives these amortized time bounds.
Suppose that we maintain a dynamic array data structure, subject to "append" operations that increase the number of elements in the array by one, but we modify the standard dynamic array (which doubles its capacity whenever it overflows) so that, instead of always choosing the new capacity to be a power of two, we choose the new capacity to be the next larger square number. That is, the sequence of capacities used by the modified data structure is $1, 4, 9, 16, \dots$ instead of $1, 2, 4, 8, \dots$. Each time the array is resized, the actual time for the resizing operation is proportional to the new capacity. Calculate the average actual time per append operation, for a sequence of $n$ append operations. You should express your answer using $O$-notation as a function of $n$ Is it possible for the amortized time per operation of this modified data structure to be less than the average actual time? Why or why not?