undefined

1. Given a list of n elements, 21, 22, ..., an, drawn from a totally ordered set. Present an O(nlg n)-time algorithm that counts the number of ordered pairs, (ai, a;), in the list such that i 2a;. Hint: Use a divide-and-conquer approach. 2. You are given an algorithm, called Interactive-Median, that determines the medians of a list of elements (drawn from a totally ordered set) interactively in the following sense: On reading in the first element a1, it outputs an; On reading in the second element a2, it outputs the median of the list a1, 22; On reading in the ith element di, it outputs the median of the list a1, 42, ..., di, and so on. (a) Show that using this algorithm, you can sort a list of n elements by giving an O(n)-time reduction from sorting to this problem of finding medians interactively. You may assume that Algorithm Interactive-Median takes O(1) time to determine each of the medians. (6) Deduce an (n lg n) lower bound for the problem of finding medians interactively. 3. Given an n x n array of distinct real numbers A. The neighbours of an entry A[i,j], 1 Si, j