CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 10 of 10
  1. #1
    Join Date
    Jan 2013
    Posts
    8

    Writing algorithms.

    Suppose we have a file of n records which are partially sorted as x1 <= x2 <= x3 <= … <= xm, and xm+1 <= ….. <= xn, is it possible to sort the entire file in time O(n) using only a small fixed amount of additional storage?

  2. #2
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,016

    Re: Writing algorithms.

    Yes, this is part of how one of the commonly-taught sorting algorithms builds a final result, by merging together partial results after a divide-and-conquer step. Any guess which algorithm?

    alternatively, how would you build an algorithm to solve it in O(n) time?
    Best Regards,

    BioPhysEngr
    http://blog.biophysengr.net
    --
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  3. #3
    Join Date
    Jan 2013
    Posts
    8

    Re: Writing algorithms.

    I don't know which algorithm is used and more over i am not building the algorithm. So the basic question is is it possible to sort in O(n) time and by using only small amount of additional storage??

  4. #4
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,016

    Re: Writing algorithms.

    Wouldn't want you to have to run a google search or think about how algorithms might work. Shock! Horror!

    This article should point you in the right directions: http://akira.ruc.dk/~keld/teaching/a...04/Huang88.pdf
    Best Regards,

    BioPhysEngr
    http://blog.biophysengr.net
    --
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  5. #5
    Join Date
    May 2009
    Posts
    2,413

    Re: Writing algorithms.

    Quote Originally Posted by psk_002 View Post
    I don't know which algorithm is used and more over i am not building the algorithm. So the basic question is is it possible to sort in O(n) time and by using only small amount of additional storage??
    Just to make sure. Are you allowed to create a new sorted file (leaving the old file unchanged)?

  6. #6
    Join Date
    Jan 2013
    Posts
    8

    Re: Writing algorithms.

    Write an algorithm that takes an array containing zeroes and ones, and returns true, if every sequence of consecutive ones is even. Else, it returns false. Analyze the running time of the algorithm.

  7. #7
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,016

    Re: Writing algorithms.

    So, first, if you have a new question, please create a new thread. It makes it easier for others to discover the discussion via search.

    Second, we're happy to help you learn, but you need to show some degree of effort. If you have a specific question, show us what you have got so far and explain where you are stuck and we will try to help you learn, probably by providing a hint or a helpful link. You will, in general, not find people willing to solve your homework problems for you though.
    Best Regards,

    BioPhysEngr
    http://blog.biophysengr.net
    --
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  8. #8
    Join Date
    Jan 2013
    Posts
    8

    Re: Writing algorithms.

    yup i will post in new thread with a new question and in the second question i am done with my algorithm but the analysg the time is bit cnfusing

    secondly the the problem with the file sytem s solved from the paper which u posted
    Last edited by psk_002; January 17th, 2013 at 11:14 PM.

  9. #9
    Join Date
    Jan 2013
    Posts
    8

    Re: Writing algorithms.

    yes we are allowed to create a new stored file or we can use the old file.

  10. #10
    Join Date
    May 2009
    Posts
    2,413

    Re: Writing algorithms.

    Quote Originally Posted by psk_002 View Post
    yes we are allowed to create a new stored file or we can use the old file.
    If you're allowed to create a new file for the sorted output the problem is easy and equivalent to merging two sorted files (which has a well known O(N) solution, just search the net).

    You need to treat your partially sorted file P as two sorted files A and B. A starts at the beginning of P and ends where the sorting on P breaks. This is where B starts and it ends where P ends.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured