Results 1 to 8 of 8

Math Help - Pseudocode

  1. #1
    Member
    Joined
    Sep 2006
    Posts
    221

    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.'
    Last edited by Ideasman; September 27th 2006 at 02:52 AM. Reason: Didnt format indentation!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Ideasman View Post
    *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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2006
    Posts
    221
    Thanks, Ron. That's exactly how I wanted it to look.

    Anyone have any insight as to how to solve this?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Sep 2006
    Posts
    221
    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
    Last edited by Ideasman; September 28th 2006 at 08:03 AM. Reason: Change in post.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Ideasman View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Sep 2006
    Posts
    221
    Quote Originally Posted by CaptainBlack View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Sep 2006
    Posts
    221
    I'm an idiot. This is completely done. Thanks again, Ron.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pseudocode
    Posted in the Calculators Forum
    Replies: 1
    Last Post: April 25th 2009, 12:03 AM
  2. Algorithm pseudocode
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 16th 2008, 01:46 PM
  3. pseudocode algorithm in C++
    Posted in the Math Software Forum
    Replies: 3
    Last Post: July 5th 2008, 09:49 PM

Search Tags


/mathhelpforum @mathhelpforum