Homework 5 due 4/10/7.  

1.  I need to find the k best solutions to knapsack of capacity C and
    n items.  Give an algorithm that will take time o(kCn) -- note
    this is little o -- the time should be strictly less than kCn.

2.  Suppose T[1..n], D[1..n] and P[1..n] denote the time required, the
    deadline, and the penalty to be paid in case the deadline is not
    met for n tasks.  Give an algorithm for finding a schedule which
    minimizes the penalty paid.  

3.  Solve the recurrences T(n) = 4T(n/2)+ O(n), and
    T(n)=4T(n/2)+O(nlogn).  Draw out the recursion trees and generally
    do a careful accounting.