memory management and -trees - describe an external-memory data structure to implement the queue adt so that the total number of disk transfers needed to process sequence of enqueue and dequeue operations is ( /bc- describe an external-memory version of the positionallist adt (section )with block size bsuch that an iteration of list of length is completed using ( /btransfers in the worst caseand all other methods of the adt require only ( transfers - change the rules that define red-black trees so that each red-black tree has corresponding ( treeand vice versa - describe modified version of the -tree insertion algorithm so that each time we create an overflow because of split of node wwe redistribute keys among all of ' siblingsso that each sibling holds roughly the same number of keys (possibly cascading the split up to the parent of wwhat is the minimum fraction of each block that will always be filled using this schemec- another possible external-memory map implementation is to use skip listbut to collect consecutive groups of (bnodesin individual blockson any level in the skip list in particularwe define an order- -skip list to be such representation of skip list structurewhere each block contains at least / list nodes and at most list nodes let us also choose in this case to be the maximum number of list nodes from level of skip list that can fit into one block describe how we should modify the skip-list insertion and removal algorithms for -skip list so that the expected height of the structure is (log nlog bc- describe how to use -tree to implement the partition (union-findadt (from section so that the union and find operations each use at most (log nlog bdisk transfers - suppose we are given sequence of elements with integer keys such that some elements in are colored "blueand some elements in are colored "red in additionsay that red element pairs with blue element if they have the same key value describe an efficient externalmemory algorithm for finding all the red-blue pairs in how many disk transfers does your algorithm performc- consider the page caching problem where the memory cache can hold pagesand we are given sequence of requests taken from pool of possible pages describe the optimal strategy for the offline algorithm and show that it causes at most / page misses in totalstarting from an empty cache - describe an efficient external-memory algorithm that determines whether an array of integers contains value occurring more than / times