two algorithm problems

This is a discussion on two algorithm problems within the C++ Programming forums, part of the General Programming Boards category; hey all, its nearing the end of semester and my professor assigned a couple extra credit problems. I'm posting to ...

  1. #1
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572

    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.

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  2. #2
    RoD
    RoD is offline
    Redundantly Redundant RoD's Avatar
    Join Date
    Sep 2002
    Location
    Missouri
    Posts
    6,331
    hmmm

    ttt

  3. #3
    Registered User
    Join Date
    Apr 2004
    Posts
    4
    Uhmm, you've tried bubble sort algorithm with array?

  4. #4
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,669
    Quote Originally Posted by eifersucht
    Uhmm, you've tried bubble sort algorithm with array?
    (n^2) > (n log d)

    ...

    Duh!!

    gg

  5. #5
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    the only idea I have for part 1 is a modified version of quicksort

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  6. #6
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,548
    In response to your other thread, how about http://nist.gov/dads/
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. String Manipulation problems -_-
    By Astra in forum C Programming
    Replies: 5
    Last Post: 12-13-2006, 04:48 PM
  2. Steering Algorithm Problem
    By Warlax in forum Game Programming
    Replies: 2
    Last Post: 10-17-2006, 12:00 PM
  3. Rendering problems (DirectX?)
    By OnionKnight in forum Tech Board
    Replies: 0
    Last Post: 08-17-2006, 12:17 PM
  4. First "big" project and having problems...
    By rabbit in forum C++ Programming
    Replies: 1
    Last Post: 02-11-2006, 08:34 PM
  5. Algorithm question
    By PJYelton in forum C++ Programming
    Replies: 2
    Last Post: 10-28-2002, 09:52 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21