Help with Algorithm Homework: Locating Last Occurrence of Smallest Element

[hyderman]

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

Homework Equations

The Attempt at a Solution

 

[chroot]

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

 

[3trQN]

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.

 

[hyderman]

okey let's 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

 

[HallsofIvy]

okey let's 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 ...

PLEASE HELP ME

 

[hyderman]

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

 

[hyderman]

thanx a lot