Results 1 to 3 of 3

Math Help - Algorithm

  1. #1
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1

    Algorithm

    Hello-

    a.) I have to write an algorithm, that, if given n numbers (all distinct), say a_1, a_2, a_3, ...., a_n, the algorithm will return the smallest and largest numbers in the list. Then, determine the exact number of comparisons that the algorithm performs.

    b.) I have to design an algorithm which will perform ONLY [(3n)/2] (its square brackets but doesn't have the horizontal line at the top; it only does at the top] comparisons to determine the smallest and largest #s in the list.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    [quote=fifthrapiers;25338]Hello-

    a.) I have to write an algorithm, that, if given n numbers (all distinct), say a_1, a_2, a_3, ...., a_n, the algorithm will return the smallest and largest numbers in the list. Then, determine the exact number of comparisons that the algorithm performs.[/tex]

    Code:
     
    function FindSmallestAndLargest(a)
    //
    //  a an array containing numerical values
    //
    //  the function returns {smallest,largest} which are the 
    //  smallest and largest values in array a.
    //
      smallest=inf;
      largest=-inf;
     
      n=length(a);
     
      for idx=1 to n
     
          if a(idx)>largest then
             largest=a(idx);
          endif
     
          if a(idx)<smallest then
              smallest=a(idx);
          endif
     
      endfor
     
      return {smallest, largest}
    endfunction
    This code performs 2 comparisons for each trip around the loop, which
    is performed n times where n is the length of the array to be processed.

    Thus the total number of comparisons is 2n.

    RonL

    (Part b will have to wait as at present I can think only of an algorithm
    with average performance comparable to the target, not one with
    a deterministic performance)
    Last edited by CaptainBlack; November 2nd 2006 at 01:23 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Part B (I claim no credit for the idea in the following algorithm it
    is the result of researching the field to find the same. The best
    I could come up with of off my own bat was an algorithm with
    an average number of comparisons ~3n/2)

    Code:
     
    function FindSmallestAndLargest(a)
    //
    //  a an array containing numerical values
    //
    //  the function returns {smallest,largest} which are the 
    //  smallest and largest values in array a.
    //
      smallest=inf;
      largest=-inf;
     
      n=length(a);
     
    //  if list length not even add a dummy element
    //  to make it so
     
      if !even(n)
        a=a|a(n);
        n=n+1;
      endif
     
    //  loop over idx=1, 3, .. n-1
     
      for idx=1 to n-1 step 2
     
     
          if a(idx)>a(idx+1)
              if a(idx)>largest then
                 largest=a(idx);
              endif
              if a(idx+1)<smallest then
                  smallest=a(idx+1);
              endif
          else
              if a(idx+1)>largest then
                 largest=a(idx+1);
              endif
              if a(idx)<smallest then
                  smallest=a(idx);
              endif
          endif
     
      endfor
     
      return {smallest, largest}
    endfunction
    This works by first comparing a pair of elements then comparing the larger
    with the current largest, and the smaller with the current smallest for a
    total of three comparisons for every two elements in the list, ie for 3n/2
    comparions for an even length list and 3(n+1)/2 comparisons for an odd
    length list (the list having had to be padded with an extra element in this
    case to make the length even).

    This may be summarise using the ceiling function \lceil . \rceil, as:

    <br />
CC=\lceil 3n/2 \rceil<br />

    Where the ceiling function gives the smallest integer larger than its argument.

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. algorithm
    Posted in the Advanced Applied Math Forum
    Replies: 3
    Last Post: January 19th 2010, 03:46 AM
  2. Algorithm
    Posted in the Advanced Math Topics Forum
    Replies: 7
    Last Post: November 22nd 2009, 08:11 AM
  3. algorithm
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: July 16th 2008, 02:29 PM
  4. Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 27th 2008, 02:02 PM
  5. gcd algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 5th 2007, 12:47 AM

Search Tags


/mathhelpforum @mathhelpforum