hey all, its nearing the end of semester and my professor assigned a couple extra credit problems. I'm posting to of which I haven't given much thought to yet, because I think they are the toughest ones.
What I'm looking for from you guys is suggestions for the solution, thanks.
1. You are given an array of n distinct numbers a1, a2,...an which you are to sort. You are given the additional information that the array is already "d-nearly sorted"; this means that the position of each number in the given array is no more that distance d from its position in the sorted array. For instance, if an array is "0-nearly sorted", it is in fact sorted; if an array is "(n-1)-nearly sorted", then you have the traditional sorting problem. Devise an algorithm that sorts a d-nearly sorted array in O(n logd) time.
2. You are given a set of n horizontal line segments {(l1,r1),(l2,r2), ...(ln,rn)" where li and ri give the leftmost and rightmost points on the i'th line segment. Devise an O(n logn) time algorithm to find a point x of maximum overlap among n line segments (a point x which is "covered" by a maximum number of segments).
any ideas appreciated.
Originally Posted by eifersucht
