• Support PF! Buy your school textbooks, materials and every day products Here!

Algorithm homework

  • Thread starter hyderman
  • Start date
30
0
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. Homework Equations



3. The Attempt at a Solution
 
Last edited:

Answers and Replies

chroot
Staff Emeritus
Science Advisor
Gold Member
10,165
34
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
 
334
1
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.
 
30
0
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
 
HallsofIvy
Science Advisor
Homework Helper
41,734
893
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 ....

PLEASE HELP ME
 
30
0
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
 
30
0
thanx alot
 

Related Threads for: Algorithm homework

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
13
Views
937
  • Last Post
Replies
1
Views
7K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
6
Views
5K
  • Last Post
Replies
5
Views
2K
Top