After sorting, what is the amortized time per step of Graham's algorithm?
Let p1, ..., pn be a list of points in the plane whose y-coordinates are all positive. The polar angle of point (x, y) is the angle formed with the x-axis by the vector from the origin (0,0) to point (x,y). For example, the polar angle of point (1,1) is 45 degrees (or π/4 radians).
Give an O(n log(n)) time algorithm to sort list of points p1, ..., pn into counterclockwise order by polar angle.
How does a dynamic programming algorithm avoid the work associated with recomputation of values?
The fibonacci numbers f0, f1, f2, ... are define by
| f0 | = | 0 |
| f1 | = | 1 |
| fn | = | fn-1 + fn-2 (for n > 1) |
f(n)
if(n < 2) return n
else return f(n-1) + f(n-2)
Is that an efficient algorithm? If so, explain why. If not, explain not and describe
how to make the algorithm efficient.
The coin changing problem is as follows. You are given a list of integer coin values c1, ..., ck, where c1 = 1 and c1 < c2 < ... < ck. You are also given a desired amount A of change, where A is a positive integer. The goal is to find out the fewest coins whose values total exactly A, where each coin must have one of the given values. You do not need to list the coins, only say how many are used.
For a given list of coin values, let C(A) be the smallest number of coins whose total value is exactly A. Then the goal is to determine C(A).
For example, suppose the coin values are 1, 5, 10 and 25. (So you have pennies, nickles, dimes and quarters.) You can make 30 cents as 25 + 5, so C(30) = 2 (for these coin values), and you can make 52 cents as 25 + 25 + 1 + 1, so C(52) = 4 (again, for these coin values).
Write recurrences for C(A). What is C(1)? What is C(A) for A > 1? You can make use of the coin values c1, ..., cn.
Give an efficient algorithm to compute C(A) for a given positive integer A. If must work for any list that satisfies the requirements of the problem.