# Pseudocode

Printable View

• Sep 27th 2006, 02:51 AM
Ideasman
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.'
• Sep 27th 2006, 03:33 AM
CaptainBlack
Quote:

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
• Sep 27th 2006, 08:42 AM
Ideasman
Thanks, Ron. That's exactly how I wanted it to look.

Anyone have any insight as to how to solve this? :confused:
• Sep 28th 2006, 08:02 AM
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
• Sep 28th 2006, 08:05 AM
CaptainBlack
Quote:

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
• Sep 28th 2006, 12:40 PM
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
• Sep 28th 2006, 06:00 PM
Ideasman
Quote:

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. :confused:
• Sep 28th 2006, 06:45 PM
Ideasman
I'm an idiot. This is completely done. Thanks again, Ron.