Thread: Pseudocode

*EDIT*: Since it didnt indent, I will show indent by *INDENT 1* *INDENT 2*, etc for degree of how much it has to be indented, 1 being first indentation, 2 the 2nd, and so forth.

Suppose we have the polynomial:

a_(n)*x^n + a_(n-1)*x^(n-1) + ... + a_2*x^2 + a_1*x + a_0 for real a_k k = 0, 1, 2, ..., n and x.

We are able to compute the value of the polynomial by using the following 3 algorithms by:

Calculating each term separately, starting with a_0 and adding each of the terms onto an accumulating sum.

First: Poly(1)

sum <-- a_0
for i <-- 1 to n
*INDENT 1*product <-- 1
*INDENT 1*for j <-- 1 to i
*INDENT 2*product <-- product * x
*INDENT 1*next j
*INDENT 1*sum <-- sum + a_i * product
next i
return sum

Second: Poly(2)

Calculating x^k by using the prev. result of x^(k-1) and multip. it by x, instead of recomputing x^k by multip. x by itself k-1 times as in the first part. Like the first part, each of the terms is added to an accumulating sum.

sum <-- a_0
product <-- 1
for i <-- 1 to n
*INDENT 1*product <-- product * x
*INDENT 1*sum <-- sum + a_i * product
next i
return sum

Third: Poly (3)

By clustering successive additions and mult.'s as shown by the following example:

2*x^3 - 7*x^2 + 5*x - 14 = -14 + x*(5 + x*(-7 + x*(2)))

The above is known as Horner's Method.

result <-- a_n
for i <-- 1 to n
*INDENT 1*result <-- result * x + a_(n-1)
next i
return result

QUESTIONS:

a.) For each of the above algorithms, what is the trace for the input?

b.) Determine the total # of operations for the input of the first part, where operations are multiplications and additions.

c.) Let T_i(n) = total # of operations (multiplications and additions) to eval. a polynomial of degree n using Poly(i) for i = 1, 2, 3. Compute T_i(n) for i = 1, 2, 3.


Thanks. I don't think the math is as hard as trying to figure out what to calculate based on the 'pseudocode.'

Originally Posted by Ideasman

*EDIT*: Since it didnt indent, I will show indent by *INDENT 1* *INDENT 2*, etc for degree of how much it has to be indented, 1 being first indentation, 2 the 2nd, and so forth.

Enclose code in [ code ] [ /code ] (without the spaces) tags to
get spaces displaed reasonably. Example:

Code:

sum <-- a_0
for i <-- 1 to n
  product <-- 1
  for j <-- 1 to i
    product <-- product * x
  next j
  sum <-- sum + a_i * product
next i
return sum

RonL

Thanks, Ron. That's exactly how I wanted it to look.

Anyone have any insight as to how to solve this?

Ahh, maybe this is why I wasn't getting responses. I left out one piece of information. Ugh, sorry.

The input is:
a_3 = 2
a_2 = -4
a_1 = 7
a_0 = -9

Originally Posted by Ideasman

Ahh, maybe this is why I wasn't getting responses. I left out one piece of information. Ugh, sorry.

The input is:
a(3) = 2
a(2) = -4
a(1) = 7
a(0) = -9

That's not why I hadn't responded, I was/am waiting to have enough time.

By the way what do you want the "trace for the input" to mean
(not that not knowing will stop me from doing the rest when I get time).

RonL

Poly(1)

sum <-- a_0
for i <-- 1 to n
...product <-- 1
...for j <-- 1 to i
......product <-- product * x
...next j
...sum <-- sum + a_i * product
next i
return sum


Operations count (mults and adds) - assume fast integer registers to handle
loop overheads so can be ignored.

inner most loop 1 mult per trip i trips
outer loop n trips - {sum(i=1 to n) i = n(n+1)/2 mults in the inner loop} + {1
add and 1 multiply per trip =n adds and n mults=2n ops}

Total ops =n(n+1)/2+2n=(n^2)/2+5n/2 ~ (n^2)/2 = O(n^2)

================================================== =======

Poly(2)

sum <-- a_0
product <-- 1
for i <-- 1 to n
...product <-- product * x
...sum <-- sum + a_i * product
next i
return sum

loop contains 3 ops and has n trips so op count is 3n

================================================== ===

Poly (3)

result <-- a_n
for i <-- 1 to n
...result <-- result * x + a_(n-1)
next i
return result

loop has 2 ops and a trip count of n so total ops is 2n.


RonL

Originally Posted by CaptainBlack

Poly(1)

sum <-- a_0
for i <-- 1 to n
...product <-- 1
...for j <-- 1 to i
......product <-- product * x
...next j
...sum <-- sum + a_i * product
next i
return sum


Operations count (mults and adds) - assume fast integer registers to handle
loop overheads so can be ignored.

inner most loop 1 mult per trip i trips
outer loop n trips - {sum(i=1 to n) i = n(n+1)/2 mults in the inner loop} + {1
add and 1 multiply per trip =n adds and n mults=2n ops}

Total ops =n(n+1)/2+2n=(n^2)/2+5n/2 ~ (n^2)/2 = O(n^2)

================================================== =======

Poly(2)

sum <-- a_0
product <-- 1
for i <-- 1 to n
...product <-- product * x
...sum <-- sum + a_i * product
next i
return sum

loop contains 3 ops and has n trips so op count is 3n

================================================== ===

Poly (3)

result <-- a_n
for i <-- 1 to n
...result <-- result * x + a_(n-1)
next i
return result

loop has 2 ops and a trip count of n so total ops is 2n.


RonL

Thanks, Ron.

"By the way what do you want the "trace for the input" to mean"

I managed to do this part

I'm totally lost what part c is even looking for though.

I'm an idiot. This is completely done. Thanks again, Ron.