of his nuts and bolts - show how to use deterministic ( )-time selection algorithm to sort sequence of elements in ( log nworst-case time - given an unsorted sequence of comparable elementsand an integer kgive an (nlogkexpected-time algorithm for finding the (kelements that have rank / / / and so on - let be sequence of insert and removemin operationswhere all the keys involved are integers in the range [ , describe an algorithm running in (nlognfor determining the answer to each removemin - space aliens have given us programaliensplitthat can take sequence of integers and partition in (ntime into sequences sk of size at most / eachsuch that the elements in si are less than or equal to every element in si + for , for fixed numberk show how to use aliensplit to sort in (nlogn/logktime - karen has new way to do path compression in tree-based union/find partition data structure starting at node she puts all the nodes that are on the path from to the root in set then she scans through and sets the parent pointer of each node in to its parent' parent pointer (recall that the parent pointer of the root points to itselfif this pass changed the value of any node' parent pointerthen she repeats this processand goes on repeating this process until she makes scan through that does not change any node' parent value show that karen' algorithm is correct and analyze its running time for path of length - this problem deals with modification of the quick-select algorithm to make it deterministic yet still run in (ntime on an -element sequence the idea is to modify the way we choose the pivot so that it is chosen deterministicallynot randomlyas follows