Page 1 of 2 12 LastLast
Results 1 to 15 of 21

Math Help - Algorithm

  1. #1
    Newbie
    Joined
    Apr 2008
    Posts
    19

    Algorithm

    the _ stand for subscript

    Code:
    begin
      Input X_1 , X_2 .....X_n
      count := - 
      for i:=2 to n do
        begin
          for j:=1 to (i-1) do 
            begin
              if x_i = x_j then 
                begin
                  count := count = 1
                end
            end
          output count
        end
    end
    i need to see if the algorithm works with the list 2, 3,6,2,6

    the theory would be very muc appricated

    many thanks
    Last edited by CaptainBlack; April 17th 2008 at 04:51 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Tom101 View Post
    the _ stand for subscript

    Code:
    begin
      Input X_1 , X_2 .....X_n
      count := - 
      for i:=2 to n do
        begin
          for j:=1 to (i-1) do 
            begin
              if x_i = x_j then 
                begin
                  count := count = 1
                end
            end
          output count
        end
    end
    i need to see if the algorithm works with the list 2, 3,6,2,6

    the theory would be very muc appricated

    many thanks
    It would be a good idea if you told us what you thought this did.

    As you have written it it should output "false"

    Ron:
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2008
    Posts
    19
    Quote Originally Posted by CaptainBlack View Post
    It would be a good idea if you told us what you thought this did.

    As you have written it it should output "false"
    well looking at it

    you started by inputting a sequecne of numbers
    set the count to zero
    the you see if i is equal to 2 - n and then you begin the fsecond loop which check to see if j is equal to 1 all the way to i-1 (which in the first casue is 1)
    and if that is correct then you add one to the count if x_i it equal to x_j
    you end but outputting the count
    that is what i think it does

    many thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Tom101 View Post
    well looking at it

    you started by inputting a sequecne of numbers
    set the count to zero
    the you see if i is equal to 2 - n and then you begin the fsecond loop which check to see if j is equal to 1 all the way to i-1 (which in the first casue is 1)
    and if that is correct then you add one to the count if x_i it equal to x_j
    you end but outputting the count
    that is what i think it does

    many thanks
    You assign count to "count=1" that is count becomed true if "count" is 1 otherwise count is "false"

    Also you intialised count to "-"

    RonL
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2008
    Posts
    19
    sorry that was a typo meant to inilize count to 0
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Tom101 View Post
    sorry that was a typo meant to inilize count to 0
    So you mean:

    Code:
    begin
      Input X_1 , X_2 .....X_n
      count := 0
      for i:=2 to n do
        begin
          for j:=1 to (i-1) do 
            begin
              if x_i = x_j then 
                begin
                  count := count + 1
                end
            end
          output count
        end
    end
    RonL
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by CaptainBlack View Post
    So you mean:

    Code:
    begin
      Input X_1 , X_2 .....X_n
      count := 0
      for i:=2 to n do
        begin
          for j:=1 to (i-1) do 
            begin
              if x_i = x_j then 
                begin
                  count := count + 1
                end
            end
          output count
        end
    end
    RonL
    Which can be animated so we get a trace:

    Code:
    >load "C:\Documents and Settings\Ron\My Documents\temp\test.e"
    >type test
    function test ()
      count= 0;
      x=[2,3,6,2,6];
      n=length(x);
      for i=2 to n
           for j=1 to (i-1)
               if x(i) == x(j) 
                count = count + 1;
               endif
              [i,j,count]
          end
      end
      return 0
    endfunction
    >
    >
    >..output is i, j, count
    >
    >test
                2             1             0 
                3             1             0 
                3             2             0 
                4             1             1 
                4             2             1 
                4             3             1 
                5             1             1 
                5             2             1 
                5             3             2 
                5             4             2 
                0 
    >
    RonL
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Apr 2008
    Posts
    19
    thanks


    just wondering, that the 6 is not used, is that becasue it cannot be used inthe sequence...

    cheers
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Tom101 View Post
    thanks


    just wondering, that the 6 is not used, is that becasue it cannot be used inthe sequence...

    cheers
    The 6 is used it is x(n) (which is x(5) in this case)

    RonL
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Apr 2008
    Posts
    19
    thanks a lot it has been much help
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Apr 2008
    Posts
    24
    so what you are saying that the algorithm works on the list 2,3,6,2,6.

    and could you plz tell me what is the time comlexity function for the algorithm by calculating how many times the comarison xi = xj is performed for an input sequence of length n.



    Quote Originally Posted by CaptainBlack View Post
    Which can be animated so we get a trace:

    Code:
    >load "C:\Documents and Settings\Ron\My Documents\temp\test.e"
    >type test
    function test ()
      count= 0;
      x=[2,3,6,2,6];
      n=length(x);
      for i=2 to n
           for j=1 to (i-1)
               if x(i) == x(j) 
                count = count + 1;
               endif
              [i,j,count]
          end
      end
      return 0
    endfunction
    >
    >
    >..output is i, j, count
    >
    >test
                2             1             0 
                3             1             0 
                3             2             0 
                4             1             1 
                4             2             1 
                4             3             1 
                5             1             1 
                5             2             1 
                5             3             2 
                5             4             2 
                0 
    >
    RonL
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by badi6 View Post
    so what you are saying that the algorithm works on the list 2,3,6,2,6.

    and could you plz tell me what is the time comlexity function for the algorithm by calculating how many times the comarison xi = xj is performed for an input sequence of length n.
    For each i the comparison is made i-1 times. So the total number of comparisons is:

    N(n)=\sum_{i=2}^n (i-1)=\frac{n(n-1)}{2}

    RonL
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Apr 2008
    Posts
    24

    Thank you very much!

    thanks for your quick reply but if one asks you to verify that the algorithm works on the list 2, 3, 6, 2, 6. what would be the best answer then?

    thanks again
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by badi6 View Post
    thanks for your quick reply but if one asks you to verify that the algorithm works on the list 2, 3, 6, 2, 6. what would be the best answer then?

    thanks again
    Tracing the execution is one way.

    RonL
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by CaptainBlack View Post
    Which can be animated so we get a trace:

    Code:
    >load "C:\Documents and Settings\Ron\My Documents\temp\test.e"
    >type test
    function test ()
      count= 0;
      x=[2,3,6,2,6];
      n=length(x);
      for i=2 to n
           for j=1 to (i-1)
               if x(i) == x(j) 
                count = count + 1;
               endif
              [i,j,count]
          end
      end
      return 0
    endfunction
    >
    >
    >..output is i, j, count
    >
    >test
                2             1             0 
                3             1             0 
                3             2             0 
                4             1             1 
                4             2             1 
                4             3             1 
                5             1             1 
                5             2             1 
                5             3             2 
                5             4             2 
                0 
    >
    RonL
    As it says above the output is i, j, count for each trip around the inner loop.

    The final 0 is the return value of the function to indicate successfull execution, and can be ignored.

    The only thing that might be considered slightly obscure is the line [i,j,count], which because it does not end in a semicolon echos the vector consisting ot i, j and count to the console.

    RonL
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum