Week 9: Notes

dynamic programming

Dynamic programming is a general technique that we can use to solve a wide variety of problems. Many of these problems involve optimization, i.e. finding the shortest/longest/best solution to a certain problem.

Problems solvable using dynamic programming generally have the following characteristics:

Usually we can dramatically improve the running time by arranging so that each subproblem will be solved only once. There are two ways to do that:

Generally we prefer a bottom-up solution, because

This week we will study one-dimensional dynamic programming problems, which have a straightforward recursive structure. Next week we will look at two-dimensional problems, which are a bit more complex.

Fibonacci numbers

Computing the Fibonacci number Fn is a trivial example of dynamic programming. Recall that the Fibonacci numbers are defined as

yielding the sequence 1, 1, 2, 3, 5, 8, 13, 21, …

Here is a recursive function that naively computes the n-th Fibonacci number:

  static int fib(int n) => n < 3 ? 1 : fib(n - 1) + fib(n – 2);

What is this function's running time? The running time T(n) obeys the recurrence

T(n) = T(n – 1) + T(n – 2)

This is the recurrence that defines the Fibonacci numbers themselves! In other words,

T(n) = O(Fn)

The Fibonacci numbers themselves increase exponentially. It can be shown mathematically that

Fn = O(φn)

where

φ = (1 + sqrt(5)) / 2

So fib runs in exponential time! That may come as a surprise, since the function looks so direct and simple. Fundamentally it is inefficient because it is solving the same subproblems repeatedly. For example, fib(10) will compute fib(9) + fib(8). The recursive call to fib(9) will compute fib(8) + fib(7), and so we see that we already have two independent calls to fib(8). Each of those calls in turn will solve smaller subproblems over and over again. In a problem with a recursive structure such as this one, the repeated work multiplies exponentially, so that the smallest subproblems (e.g. fib(3)) are computed an enormous number of times.

top-down dynamic programming (memoization)

As mentioned above, one way we can eliminate the repeated work is to use a cache that stores answers to subproblems we have already solved. This technique is called memoization. Here is a memoized implementation of fib, using a local function:

  static int fib(int n) {
        int[] cache = new int[n + 1];
        
        int f(int i) {
            if (cache[i] == 0)
                cache[i] = i < 3 ? 1 : f(i - 1) + f(i - 2);
            return cache[i];
        }
        
        return f(n);
    }

Above, the cache array holds all the Fibonacci numbers we have already computed. In other words, if we have already computed Fi, then cache[i] = Fi. Otherwise, cache[i] = 0.

This memoized version runs in linear time, because the line

runs only once for each value of i. This is a dramatic improvement!

bottom-up dynamic programming

In this particular recursive problem, the subproblem structure is quite straightforward: each Fibonacci number Fn depends only on the two Fibonacci numbers below it, i.e. Fn-1 and Fn-2. Thus, to compute all the Fibonacci numbers up to Fn we may simply start at the bottom, i.e. the values F1 and F2, and work our way upward, first computing F3 using F1 and F2, then F4 and so on. Here is the implementation:

  static int fib(int n) {
      int[] a = new int[n + 1];
      a[1] = a[2] = 1;
      for (int k = 3 ; k <= n ; ++n)
          a[k] = a[k - 1] + a[k - 2];
      return a[n];
  }

Clearly this will also run in linear time. Note that this implementation is not even a recursive function. This is typical: a bottom-up solution consists of one or more loops, without recursion.

This example may seem trivial. But the key idea is that we can efficiently solve a recursive problem by solving subproblem instances in a bottom-up fashion, and as we will see we can apply this idea to many other problems.

rod cutting

The rod cutting problem is a classic dynamic programming problem. Suppose that we have a rod that is n cm long. We may cut it into any number of pieces that we like, but each piece's length must be an integer. We will sell all the pieces, and we have a table of prices that tells us how much we will receive for a piece of any given length. The problem is to determine how to cut the rod so as to maximize our profit.

We can express an optimal solution recursively. Let prices[i] be the given price for selling a piece of size i. We want to compute profit(n), which is the maximum profit that we can attain by chopping a rod of length n into pieces and selling them. Any partition of the rod will begin with a piece of size i cm for some value 1 ≤ i ≤ n. Selling that piece will yield a profit of prices[i]. The maximum profit for dividing and selling the rest of the rod will be profit(n – i). So profit(n), i.e. the maximum profit for all possible partitions, will equal the maximum value for 1 ≤ i ≤ n of

prices[i] + profit(n – i)

naive recursive solution

Here is a naive recursive solution to the problem:

  // Return the best price for cutting a rod of length n, given a table
  // with the prices for pieces from lengths 1 .. n.
  static int profit(int n, int[] prices) {
      int best = 0;
      for (int i = 1 ; i <= n ; ++i)
          best = Max(best, prices[i] + profit(n - i, prices));
      return best;
  }

This solution runs in exponential time, because for each possible size k it will recompute profit(k, prices) many times.

bottom-up dynamic programming

This solution uses bottom-up dynamic programming:

  // Return the best price for cutting a rod of length n, given a table
  // with the prices for pieces from lengths 1 .. n.
  static int profit(int n, int[] prices) {
      int[] best = new int[n + 1];  // best possible price for each size

      for (int k = 1 ; k <= n ; ++k) {
          // Compute the best price best[k] for a rod of length k.
          best[k] = 0;
          for (int i = 1 ; i <= k ; ++i)
              best[k] = Max(best[k], prices[i] + best[k - i]);
      }

      return best[n];  // best price for a rod of length n
  }

Once again, this bottom-up solution is not a recursive function. Notice its double loop structure. Each iteration of the outer loop computes best[k], i.e. the solution to the subproblem of finding the best price for a rod of size k. To compute that, the inner loop must loop over all smaller subproblems, which have already been solved, looking for a maximum possible profit.

This version runs in O(N2).

bottom-up dynamic programming, extended

Often when we use dynamic programming to solve an optimization problem such as this one, we want not only the value of the optimal solution, but also the solution itself. For example, the function in the previous section tells us the best possible price that we can obtain for a rod of size n, but it doesn't tell us the sizes of the pieces in which the rod should be cut!

So we'd like to extend our solution to return that information. To do that, for each size k < n we must remember not only the best possible prices for a rod of size k, but also the size of the first piece that we should slice off from a rod of that size in order to obtain that price. With that information, we can reconstruct the solution at the end:

  // Return the best price for cutting a rod of length n, given a table
  // with the prices for pieces from lengths 1 .. n.
  static int profit(int n, int[] prices, out int[] sizes) {
      int[] best = new int[n + 1];   // best possible price for a given rod size
      int[] cut = new int[n + 1];    // size of first piece to slice from a given rod size

      for (int k = 1 ; k <= n ; ++k) {
          best[k] = 0;
          for (int i = 1 ; i <= k ; ++i) {      // for every size <= k
              int p = prices[i] + best[k - i];
              if (p > best[k]) {
                  best[k] = p;
                  cut[k] = i;  // remember the best size to cut
              }
          }
      }

      List<int> l = new List<int>();
      for (int s = n ; s > 0 ; s -= cut[s])
          l.Add(cut[s]);
      sizes = l.ToArray();
      return best[n];
  }

Study this function to understand how it works. Like the preceding version, it runs in O(N2).

smallest number of coins

Here is another classic dynamic programming problem. We would like to write a method int numCoins(int sum, int[] coins) that takes a integer and an array of coin denominations. The method should determine the smallest number of coins needed to form the given sum. A sum can contain an arbitrary number of coins of each denomination. For example, if sum = 34 and coins = { 1, 15, 25 }, the method will return 6, since

34 = 15 + 15 + 1 + 1 + 1 + 1

and it is not possible to form this sum with a smaller number of coins.

If we cannot form the given sum using the given denominations of coins, our method will return int.MaxValue.

By the way, you will recall that in a recent homework exercise we wrote a recursive program that can generate all possible ways of forming a sum from a set of coins. So one way to find the smallest number of coins would be to generate all those possible ways, and see which one uses the smallest number. However that will be hopelessly inefficient, because there may be an exponential number of ways to form the sum. Dynamic programming will give us a more efficient solution.

naive recursive solution

First, here is a naive recursive solution to the problem:

  // Return the smallest number of coins needed to form (sum).
  static int numCoins(int sum, int[] coins) {
      if (sum == 0) return 0;
    
      int min = int.MaxValue;
      foreach (int c in coins)
          if (c <= sum)
              min = Min(min, numCoins(sum - c, coins));

      return min == int.MaxValue ? int.MaxValue : min + 1;
  }

This will run in exponential time.

bottom-up dynamic programming

Here is a solution using bottom-up dynamic programming. Its structure is similar to the previous rod-cutting solution.

  // Return the smallest number of coins needed to form (sum).
  static int numCoins(int sum, int[] coins) {
      int[] min = new int[sum + 1];
    
      for (int k = 1 ; k <= sum ; ++k) {
          // Compute min[k], the minimum number of coins needed to add up to k.
          int m = int.MaxValue;
          foreach (int c in coins)
              if (c <= k)
                  m = Min(m, min[k - c]);
          min[k] = m == int.MaxValue ? int.MaxValue : m + 1;
      }
    
      return min[sum];
  }

This version runs in O(N2), where N = sum.

bottom-up dynamic programming, extended

This version returns an array with the values of the coins that form the sum.

  static int[] numCoins2(int sum, int[] coins) {
      int[] min = new int[sum + 1];
      int[] first = new int[sum + 1];
    
      for (int k = 1 ; k <= sum ; ++k) {
          // Compute min[k], the minimum number of coins needed to add up to k.
          // Also remember first[k], the first coin to use in forming the sum k.
          int m = int.MaxValue;
          foreach (int c in coins)
              if (c <= k && min[k - c] < m) {  // best so far
                  m = min[k - c];
                  first[k] = c;
              }
          min[k] = m == int.MaxValue ? int.MaxValue : m + 1;
      }
    
      List<int> l = new List<int>();
      for (int s = sum ; s > 0 ; s -= first[s])
          l.Add(first[s]);
      return l.ToArray();

}

graphical interfaces

Graphical programs contain many common user interface elements: push buttons, check boxes, scrollbars, dialog boxes and so on. In this course we will learn to write programs in C# that contain these kinds of elements, which are typically called widgets in the Unix programming world and controls in the Windows world.

There are many user interface toolkits that let you write graphical programs using a variety of widgets/controls. Some of these toolkits are specific to one particular operating system, and others are cross-platform. Also, some of them are specific to a particular programming language, and others have bindings to many different languages. In this course we will use GTK. See the separate page Introduction to GTK in C# for more information about it.