Greedy Method: Assignment

  1. Scheduling to minimize mean finish time.

    Let : T1 , T 2 , . . . , T n be n jobs on a single processor. Let ti and wi represent the running time and weight associated with Ti , 1 < i < n. A schedule S is a permutation of the jobs describing the order of execution; i.e., S= { i1 , i 2 , . . . , i n} is a schedule if S is a permutation of (1, 2, . . . , n). Scheduling jobs according to S results in job Ti1 running from time 0 to time ti1, Ti2 running from time ti1 to time ti1 + ti2, and so on. Let fi(S) be the finish time of Ti. The mean weighted finish time for S is given by

    Discover a greedy strategy to find a schedule which minimizes the mean weighted finish time. Prove that your strategy works. (Hint: first try the simpler case where wi = 1, 1 < i < n).

    Dynamic Programming: Assignment

  2. Coin Changing

    Let Ami = { a1 , a 2 , . . . , a n} be a finite set of distinct coin types. Assume that each ai is an integer and that 1 = a1 < a2 < . . . < an . Each coin type is available in unlimited quantity. Let f(i) be the minimum total number of coins required to make up exact change for i. Provide a recurrance equation for f(i). Write a dynamic algorithm using the equation to construct the table for f(i) for i = 1, 2, 3, . . . , n. What is the time complexity of your algorithm?

    Hint: Assume you know how to make change for c < i. Then make change for i.