# Math Help - Algorithm

1. ## 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

2. 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:

3. 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

4. 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

5. sorry that was a typo meant to inilize count to 0

6. 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

7. 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

8. thanks

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

cheers

9. 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

10. thanks a lot it has been much help

11. 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

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

13. ## 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

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

15. 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

Page 1 of 2 12 Last