1. ## two algorithm problems

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.

2. hmmm

ttt

3. Uhmm, you've tried bubble sort algorithm with array?

4. Originally Posted by eifersucht
Uhmm, you've tried bubble sort algorithm with array?
(n^2) > (n log d)

...

Duh!!

gg

5. the only idea I have for part 1 is a modified version of quicksort