# two algorithm problems

• 04-26-2004
axon
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.
• 04-27-2004
RoD
hmmm

ttt
• 04-27-2004
eifersucht
Uhmm, you've tried bubble sort algorithm with array?
• 04-27-2004
Codeplug
Quote:

Originally Posted by eifersucht
Uhmm, you've tried bubble sort algorithm with array?

(n^2) > (n log d)

...

Duh!!

gg :)
• 04-27-2004
axon
the only idea I have for part 1 is a modified version of quicksort
• 04-29-2004
Salem