Thread: Algorithm help

I am terrible with algorithms but here goes

Suppose one wants to find, for a given list of distinct numbers, the sum of the products of every pair of different numbers in the list. For example, if the list consists of 4, 10, 20, 100 then we would compute 4*10 + 4*20 + 4*100 + 10*100 + 20*100 = 3720

The task is to write out an algorithm for the above calculation for an arbitrary list of n distinct numbers.

I am lost and don't know where to begin

Originally Posted by minkyboodle

I am terrible with algorithms but here goes

Suppose one wants to find, for a given list of distinct numbers, the sum of the products of every pair of different numbers in the list. For example, if the list consists of 4, 10, 20, 100 then we would compute 4*10 + 4*20 + 4*100 + 10*100 + 20*100 = 3720

The task is to write out an algorithm for the above calculation for an arbitrary list of n distinct numbers.

I am lost and don't know where to begin

Why didn't you have 10*20?

because I missed it

Originally Posted by minkyboodle

because I missed it

Algo Hint

For i = 1 to n-1
For j = (i+1) to n
sum = sum + a_i*a_j

Can you complete?

Suppose there were n numbers in the list. Then if you simply multiply all the pairs together, which seems to be what aman_cc is suggesting you have to do n*(n-1)/2 multiplications. So for 10 numbers that would be 45 multiplications. But you can do it with only 11 multiplications and one division like this:
Add all the numbers together, and square the result
Add the squares of all the numbers together.
Subtract the second number from the first and divide by 2.

Originally Posted by alunw

Suppose there were n numbers in the list. Then if you simply multiply all the pairs together, which seems to be what aman_cc is suggesting you have to do n*(n-1)/2 multiplications. So for 10 numbers that would be 45 multiplications. But you can do it with only 11 multiplications and one division like this:
Add all the numbers together, and square the result
Add the squares of all the numbers together.
Subtract the second number from the first and divide by 2.

so to write that it would be?

I get what you are saying but I can't figure out how to put it into math writing

I think you should try to do a little more work yourself now. In any case I don't know what system you are supposed to be using for writing down your algorithm. I've used a form of the binomial theorem here, or whatever its equivalent for more than two terms is called.
Why not try to use the same kind of language aman_cc used, but to describe my algorithm instead.