Quiz 7-- Princeton Algorithm

Dynamic median. Design a data type that supports insert in logarithmic time, find-the-median in constant time, and remove-the-median in logarithmic time.

Hint: maintain two binary heaps, one that is max-oriented and one that is min-oriented.


maintain two equal size heap, one max heap which holds the smallest half items and one min heap which holds the largest half items.


when inserting an element, if it's greater than the max element of max heap, then insert it to min heap, else insert it to max heap. After insertion, if the inserted heap's size is two more than the size of the other heap, remove the top  element of the inserted heap and insert it to the other heap.


Randomized priority queue. Describe how to add the methods 𝚜𝚊𝚖𝚙𝚕𝚎() and 𝚍𝚎𝚕𝚁𝚊𝚗𝚍𝚘𝚖() to our binary heap implementation. The two methods return a key that is chosen uniformly at random among the remaining keys, with the latter method also removing that key. The 𝚜𝚊𝚖𝚙𝚕𝚎() method should take constant time; the 𝚍𝚎𝚕𝚁𝚊𝚗𝚍𝚘𝚖() method should take logarithmic time. Do not worry about resizing the underlying array.

get a random number form 1 - N, and get the element of that index in the array as the sample() result. for DelRandom(), swap that element with the last element, and sink and swim in that index.

Taxicab numbers. A taxicab number is an integer that can be expressed as the sum of two cubes of integers in two different ways: a3+b3=c3+d3. For example, 1729=93+103=13+123. Design an algorithm to find all taxicab numbers with a, b, c, and d less than n.

• Version 1: Use time proportional to n2logn and space proportional to n2.
• Version 2: Use time proportional to n2logn and space proportional to n.

Hints:

• Version 1: Form the sums a3+b3 and sort.
• Version 2: Use a min-oriented priority queue with n items.

Version 1: for any a , b less than n , store a^3 + b ^3 in an array, there are O(n^2) such element, sort the array using n^2logn time, and then scan the array, to compare adjacent elements