1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Algorithm homework

  1. Jan 10, 2007 #1
    hello
    any one can help me with this
    thanx

    The Horner’s method is an algorithm that evaluates polynomials. The following pseudocode shows how to use this method to find the
    value of anxn + an-1xn-1 + . . . + a1x + a0 at x = c.
    procedure Horner(c, a0, a1, a2, . . . , an : real numbers)
    y := an
    for i := 1 to n
    y := y × c + an-i
    end {y = ancn + an-1cn-1 + . . . + a1c + a0}

    (a) Describe an algorithm that locates the last occurrence of the smallest element in a finite list of integers, where the integers in the list are not necessarily distinct. [5]
    (b) Analyze the complexity of the algorithm you devised in Part (a), measured in terms of the number of comparisons



    2. Relevant equations



    3. The attempt at a solution
     
    Last edited: Jan 10, 2007
  2. jcsd
  3. Jan 10, 2007 #2

    chroot

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    We will not do your homework for you. Please explain to us your thoughts, and why you're stuck, and we'll try to help you.

    - Warren
     
  4. Jan 10, 2007 #3
    Think about how many times you would need to iterate such a list, for the simplest case. Generally they (computer scientists) refer to best, worst and average cases [1].

    If you look specifically at the O(1) and O(n) cases, constant and linear respectively. O(1) is a single comparison, O(n) depends on the magnitude (number of elements therein) of the list directly. If you iterate the list once you make n comparisons.
     
  5. Jan 10, 2007 #4
    okey lets try answer part a

    procedure LocSmallest(a1, a2, . . . , an : integers) m := a1
    location := 1 for i := 2 to n
    begin
    if ai =< m then
    begin

    NOW HOW WHAT NEXT
    .....
    .....
    .....

    end;

    FOR PART B
    CAN WE COUNT THE COMPARISON STATEMENT AND WHAT ALGORITHM WE CAN USE ....

    PLEASE HELP ME
     
  6. Jan 10, 2007 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    What do you think you should do next? What do you WANT m to eventually be? I can assume that a1, 2, ..., an are the original list, but you haven't said what m is. Is it the variable the procedure will return? Okay, if you find a number on the list less than m, what should you do?

     
  7. Jan 10, 2007 #6
    thanx for replying .... so far i establisshed that minimum=m

    i am not sure how to rwrite the next code but i will try

    i think
    procedure LocSmallest(a1, a2, . . . , an : integers) m := a1
    location := 1 for i := 2 to n
    begin
    if ai =< m then
    begin
    let ai= m
    continue
    location=m
    end

    end;


    is the whole procedure right and if not how to fix it.... please help
     
  8. Jan 12, 2007 #7
    thanx alot
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Algorithm homework
  1. Euclid's Algorithm (Replies: 5)

  2. Euclidean algorithm (Replies: 3)

  3. Division Algorithm (Replies: 3)

  4. Reme's algorithm (Replies: 5)

  5. Division algorithm (Replies: 13)

Loading...