1. Describe an algorithm that locates the last occurrence of the smallest elemen

Question

1. 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. Write pseudocode for such an algorithm in the spirit of the pseudocode presented in lecture.

2. Use the greedy algorithm to make change (i) using quarters, dimes, nickels, and pennies and (ii) using quarters, dimes, and pennies (but no nickels) for the following amounts. For each algorithm and amount decide whether the greedy algorithm returns the optimal solution (i.e. uses the fewest coins possible)? (a) 87 cents (b) 80 cents

3. Use the definitions of big-O, big-, and big- to show the following: (a) 10n + n log n is O(n^2 ) but it is not (n^2 ) (b) f(n) = 5n^2 n log n is (n^2 )

4. The following algorithms evaluate the polynomial p(x) = anx^n + an-1x^n1 + · · · + a1x + a0 at a point x = c in two different ways.

procedure polynomial(c, a0, a1, . . . , an)

power := 1

y := a0

for i := 1 to n

power := power c

y := y + ai power

return y

procedure Horner(c, a0, a1, . . . , an)

y := an

for i := 1 to n

y := y c + an-i

return y

(a) Evaluate 3x^2 + x + 1 at x = 2 using each of the two procedures. Show your steps.

(b) Exactly how many multiplications and additions are used by each of the two procedures for a polynomial of degree n at x = c? (Do not count additions used to increment for-loops). Which procedure is more efficient?

Explanation / Answer

Question 4

3*x2 + x + 1 at x = 2

a) polynomial ( 2 , 1 ,1 ,3 )
y = 1
Step 1 : i = 1
y = 1 + 1*2
y = 3
Step 2 : i = 2
y = 3 + 3*4
y = 15



b) Horners ( 2 , 1 ,1 ,3 )
y = 3
Step 1 : i = 1
y = 1 + 3*2
y = 7
Step 2 : i = 2
y = 1 + 7*2
y = 15




b) . Both the procedure takes O(n) times , But the number of multiplication required in polynomial is more than number of multiplication in Horners.



Multiplication by Polynomial . : 2n multiplications
Multiplication by Horners : n multiplications


Thanks, let me know if there is any concern.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.