Thread: 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

Originally Posted by Tom101

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:

Originally Posted by CaptainBlack

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

Originally Posted by Tom101

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

sorry that was a typo meant to inilize count to 0

Originally Posted by Tom101

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

Originally Posted by CaptainBlack

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

thanks


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

cheers

Originally Posted by Tom101

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

thanks a lot it has been much help

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.

Originally Posted by CaptainBlack

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

Originally Posted by badi6

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 the comparison is made times. So the total number of comparisons is:



RonL

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

Originally Posted by badi6

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

Originally Posted by CaptainBlack

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