1. Coin changing

   Let A_n={a_1,...,a_n} be a finite set of distinct coin types. We can assume that each a_i is a positive integer and a_1,...,a_n are in descending order of their value. Each type of coin is available in unlimited quantity. The coin-changing problem is to make up an exact amount C using a minimum total number of coins. C is a positive integer.
   
   a. Show that if a_n is not equal to 1, then there exists a finite set of coin types and a C for which there is no solution to the coin-changing problem.
   b. Show that there is always a solution when a_n=1.
   c. When a_n=1, a greedy solution is to make change by using the coin types in the order a_1,...,a_n. When coin type a_i is being considered, as many coins of this type as possible are given. Write an algorithm based on this strategy. Show that this algorithm does not necessarily generate optimal solutions.
   d. Show that if A_n={k^{n-1},...,k^0} for some positive integer k, then the above greedy method always yeilds an optimal solution.




2. Optimal Assignment

   Assume that there are n workers and n jobs. Let v_{ij} be the value of assigning worker i to job j. An assignment of workers to jobs corresponds to the assignment of 0 or 1 to the variables x_{ij}, where i and j are integers between 1 and n. A valid assignment is one in which each worker is assigned to exactly one job and exactly one worker is assigned to each job. The value of the assignment is sum over v_{ij}x_{ij}. We want to find an assignment of maximum value.
   
   Consider two greedy strategies. One assigns to each worker the best possible job and another assigns to each job the best possible worker. Show that neither of these schemes gives an optimal solution. Is either scheme better than the other?
   Suggest an algorithm to get an optimal solution.



3. Let S be a set of n points in the plane. It is given that there is only a constant say c number of points on the convex hull of S. Can you design an algorithm to find the convex hull of S that runs in time o(nlog n)? Conceive of special algorithms for c=3 and c=4 first and then generalize.