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 ofndistinct numbersa1, a2,...anwhich 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 distancedfrom 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(nlogd) time.

2. You are given a set ofnhorizontal line segments {(l1,r1),(l2,r2), ...(ln,rn)" whereliandrigive the leftmost and rightmost points on thei'th line segment. Devise an O(nlogn) time algorithm to find a point x of maximum overlap amongnline segments (a point x which is "covered" by a maximum number of segments).

any ideas appreciated.