20-CS-472-001 Design and Analysis of Algorithms II Winter 2011

Greedy Algorithms

Due: January 30, 2011

  1. Consider the following problem, known as the Traveling Salesperson Problem:
           Instance: a graph G=(V,E), and a weighting function w:EN+
           Find:     a cycle connecting all the vertices of V of minimum
                     total cost.
    Here is a proposed (greedy) algorithm for this problem:
           order edges by weight in increasing order - call the list L
           T  Null  (T is initialized to the empty list)
           while the number of edges in T is less than the number of vertices
                 in V minus 1 do the following:
              e  popL
              suppose e = <x,y>
              if there do not exist vertices a,b such that either edges <a,x> and 
              <b,x> are in T or edges <a,y> and <b,y> are in T, and
              there is no path <x...y> in T then T  T U {e}
           add to T the edge from L which completes the cycle
    Show that this algorithm can not be used to solve the Traveling Salesperson problem exactly.

  2. Consider the problem of making change for n cents using the minimum number of coins.
    1. Describe a greedy algorithm to make change consisting of quarters, dimes, nickels, and pennies. Prove that your algorithm always works.
    2. Suppose that the available coins are in denominations c0, c1,...,ck for some integers c > 1 and k > 0. Show that the greedy algorithm always gives an optimal solution.
    3. Give a set of coin denominations for which the greedy algorithm does not yield an optimal solution.