# Algorithm homework

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. 
(b) Analyze the complexity of the algorithm you devised in Part (a), measured in terms of the number of comparisons

2. Homework Equations

3. The Attempt at a Solution

Last edited:

Related Calculus and Beyond Homework Help News on Phys.org
chroot
Staff Emeritus
Gold Member

- Warren

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 .

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.

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 ....

HallsofIvy
Homework Helper
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
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?

.....
.....
.....

end;

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

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;