This book chapter is a very nice presentation of Dynamic Programming. Let's do the following.

• Everyone read sections 6.1 and 6.2 (pp 169 - 173). These two sections present the basic idea behind dynamic programming and illustrate it with a nice example.
• Each person (or pair of people) pick one of the other sections to present: 6.4, 6.5, 6.6, or 6.7. (All the sections are quite short.) To pick a section reply to this message saying which section you want and who will be doing that section. If a section has been selected by someone or some group, please select another section until they are all taken.
• Each person select an exercise from the end of the chapter and write code that solves it. Let's have one exercise per person--although if you want to work in teams, do as many exercises as there are people on your team. Again, to avoid duplication reply to this message saying which exercise(s) you are doing and who will be doing it/them.

​This is not a difficult assignment.

Remember: this is a regular class; you are getting 4 units of credit for it; we will relax after the programming contest in a month. So let's put in the effort now.

The entire book is available here, either as a single pdf file or chapter-by-chapter. Perhaps we should go over some of the other chapters in the next few weeks. Let me know what you think.

Much of this material should have been covered in CS 312. Unfortunately, it's been many years (probably decades!) since I taught that course. The official syllabus for CS 312 mentions dynamic programming explicitly as one of the topics covered.

Please sign up for the section you are going to present and the problem you are going to code.

Here is a question about the knapsack problem (p 181). You want to solve:

K(w) = maximum value achievable with a knapsack of capacity w

Can we express this in terms of smaller subproblems? Well, if the optimal solution to K(w)
includes item i, then removing this item from the knapsack leaves an optimal solution to
K(w  - w_i). In other words, K(w) is simply K(w - w_i) + v_i, for some i. We don't know which i,
so we need to try all possibilities.

My question to you is why is this true? Why is it that "if the optimal solution to K(w) includes item i, then removing this item from the knapsack leaves an optimal solution to K(w  - w_i)."
 

Problem 6.18 is a simple variation of 6.17. It is shown without the archive, which can be added as above.

/** May use a denomination only once */
def canMakeChangeOneUse(money: Int, denominations: List[Int]): Boolean = {
    if (money == 0) true
    else if (denominations.isEmpty) false
    else if (denominations.head > money) canMakeChangeOneUse(money, denominations.tail)
    else canMakeChangeOneUse(money - denominations.head, denominations.tail) ||
            canMakeChangeOneUse(money, denominations.tail)
  }                                               //> canMakeChangeOneUse: (money: Int, denominations: List[Int])Boolean

  canMakeChangeOneUse(16, List(1, 5, 10, 20))     //> res4: Boolean = true
  canMakeChangeOneUse(31, List(1, 5, 10, 20))     //> res5: Boolean = true
  canMakeChangeOneUse(40, List(1, 5, 10, 20))     //> res6: Boolean = false

Problem 6.22 looks like the same problem as 6.18.

Here's code for problem 6.13.

 def game6_13(cards: List[Int]): Array[Array[Option[(Int, Char)]]] = {

   var moveTable = ofDim[Option[(Int, Char)]](cards.size, cards.size)
   for (i <- 0 until cards.size)
     moveTable(i) = Array.fill[Option[(Int, Char)]](cards.size)(None)

    def getBestMove(left: Int, right: Int): (Int, Char) = {
      if (moveTable(left)(right).isDefined) moveTable(left)(right).get
      else {
        val forPlayer1 = (left + right) % 2 == 1
        val bestMove = {
          if (left == right) (-cards(left), 'X') // No choice. Player_2 takes last card
          else {
            val scores: List[(Int, Char)] = List('L', 'R').map(
              _ match {
                case 'L' => ((if (forPlayer1) cards(left) else -cards(left)) + getBestMove(left + 1, right)._1, 'L')
                case 'R' => ((if (forPlayer1) cards(right) else -cards(right)) + getBestMove(left, right - 1)._1, 'R')
              }) //end map
            if (scores(0)._1 == scores(1)._1) (scores(0)._1, 'X')
            else if (forPlayer1) { if (scores(0)._1 > scores(1)._1) scores(0) else scores(1) }
              else if (scores(0)._1 < scores(1)._1) scores(0) else scores(1)
          } // end else
        } // end bestMove = 
        moveTable(left)(right) = Option(bestMove)
        println("Player_" + (if (forPlayer1) "1 " else "2 ") + left + " " + right + " " + moveTable(left)(right))
        bestMove
      } // end else
    } // end getBestMove

    for (left <- cards.size - 2 to 0 by -1) 
      for (right <- left +1 until cards.size) 
         getBestMove(left, right)

    moveTable
  } // end game6_13

Here's a call to it from a worksheet. Intermediate results are printed during the computation. For example,

Player_2 0 2 Some((-92,R))

means that it's Player_2's turn with the indices at 0 and 2. (For a given pair of indices it's always either Player_1's turn or Player_2's turn.) His best move is to take the R (right) card (which is 100). The final score will be -92 (from Player_1's perspective).

  def playGame6_13(cards: List[Int]): Array[Array[Option[(Int, Char)]]] = {
    var moveTable = game6_13(cards)
    for (i <- 0 until cards.size) {
      for (j <- 0 until cards.size)
        printf("%12s", moveTable(i)(j).getOrElse(""))
      println(" ")
    } //
    moveTable
  }                                               //> playGame6_13: (cards: List[Int])Array[Array[Option[(Int, Char)]]]
  playGame6_13(List(1, 9, 100, 10))              
                                                  //> Player_2 3 3 Some((-10,X))
                                                  //| Player_2 2 2 Some((-100,X))
                                                  //| Player_1 2 3 Some((90,L))
                                                  //| Player_2 1 1 Some((-9,X))
                                                  //| Player_1 1 2 Some((91,R))
                                                  //| Player_2 1 3 Some((81,X))
                                                  //| Player_2 0 0 Some((-1,X))
                                                  //| Player_1 0 1 Some((8,R))
                                                  //| Player_2 0 2 Some((-92,R))
                                                  //| Player_1 0 3 Some((82,L))
                                                  //|   (-1,X)       (8,R)     (-92,R)      (82,L) 
                                                  //|                   (-9,X)      (91,R)     (81,X) 
                                                  //|                               (-100,X)      (90,L) 
                                                  //|                                                 (-10,X) 
                                                  //| res0: Array[Array[Option[(Int, Char)]]] = Array(Array(Some((-1,X)), Some((8,
                                                  //| R)), Some((-92,R)), Some((82,L))), Array(None, Some((-9,X)), Some((91,R)), S
                                                  //| ome((81,X))), Array(None, None, Some((-100,X)), Some((90,L))), Array(None, N
                                                  //| one, None, Some((-10,X))))

  playGame6_13(List(1, 5, 6, 2))                  
                                                  //> Player_2 3 3 Some((-2,X))
                                                  //| Player_2 2 2 Some((-6,X))
                                                  //| Player_1 2 3 Some((4,L))
                                                  //| Player_2 1 1 Some((-5,X))
                                                  //| Player_1 1 2 Some((1,R))
                                                  //| Player_2 1 3 Some((-1,X))
                                                  //| Player_2 0 0 Some((-1,X))
                                                  //| Player_1 0 1 Some((4,R))
                                                  //| Player_2 0 2 Some((-2,R))
                                                  //| Player_1 0 3 Some((0,X))
                                                  //|   (-1,X)       (4,R)      (-2,R)       (0,X) 
                                                  //|                   (-5,X)       (1,R)      (-1,X) 
                                                  //|                                  (-6,X)        (4,L) 
                                                  //|                                                  (-2,X) 
                                                  //| res1: Array[Array[Option[(Int, Char)]]] = Array(Array(Some((-1,X)), Some((4,
                                                  //| R)), Some((-2,R)), Some((0,X))), Array(None, Some((-5,X)), Some((1,R)), Some
                                                  //| ((-1,X))), Array(None, None, Some((-6,X)), Some((4,L))), Array(None, None, N
                                                  //| one, Some((-2,X))))

I will present 6.7 and problem 6.2

I will cover 6.6 and problem 6.16

Here is some code for Bugs Integrated (placing chips on a plate).

I liked Larry's problem of finding the longest palindromic subsequence so much that I thought I'd write it in Scala.  Here's the whole thing in a worksheet.

  def longestPalindrome(string: String): Set[String] = {
       var archive = Map[(Int, Int), Set[String]]()

         def longestPalindrome(i: Int, j: Int): Set[String] = {
               val result =
                    archive.getOrElse((i, j), {
                         if (i > j) Set("")
                         else if (i == j) Set(string(i) +: "")
                         else if (string(i) == string(j)) longestPalindrome(i + 1, j - 1).map(s => (string(i) +: s) :+ string(j))
                         else {
                                val leftSet = longestPalindrome(i, j - 1)
                                val rightSet = longestPalindrome(i + 1, j)
                                if (leftSet.head.length > rightSet.head.length) leftSet
                                else if (leftSet.head.length < rightSet.head.length) rightSet
                                // Is there a better way to deal with this case?
                                else leftSet ++ rightSet
                         }
                  archive += (i, j) -> result
                  result
                }
         }
         // There must be a better way to sort a set.
         scala.collection.immutable.TreeSet[String]() ++ longestPalindrome(0, string.length() - 1)
  }                                               //> longestPalindrome: (string: String)Set[String]
  
  
  longestPalindrome("ACGTGTCAAAATCG").mkString(", ")
                                                  //> res0: String = CTAAAATC, GCAAAACG, GTAAAATG

Here is the palindrome problem from the bottom up.  It first finds all pairs of matching letters -- as well as each individual letter. Then it inserts these into each other until no more insertions are possible. 

/**
 *  @param string is the original string
 */
case class PairwisePaliSolver(string: String) {

  /**
   *  This is the class Pali of palindromes. It is a tree of Palindromes
   *  with the same left and right characters. children aset of internal Palindromes.
   *  @param left and right are the indices of the leftmost and righmost character.
   *  @param children are embedded palindromes. Only the largest children are kept.
   *  Therefore they all have the same length.
   *
   */
  case class Pali(left: Int, right: Int, children: Set[Pali]) {

    def this(left: Int, right: Int) = this(left, right, Set[Pali]())

    // The length of the children. Since only the largest are kept, 
    // the children all have the same length
    val childLength = if (children.isEmpty) 0 else children.head.length

    // The number of characters in this palidrome.
    val length: Int = (if (isASingleChar) 1 else 2) + childLength

    // The span of the string covered.
    def width = right - left + 1

    /**
     * Add potentialChild to the set of children if it compatible with this Palindrome.
     * It it is larger than the others, discard the others and keep only it.
     * It if is the same size add it to the set of children.
     * If it is smaller than the children don't add it.
     */
    def addChild(potentialChild: Pali): (Boolean, Pali) = {
      if (potentialChild.left <= left ||
          potentialChild.right >= right ||
          potentialChild.length < childLength) (false, this)
      else {
        val newChildren =
                 if (potentialChild.length > childLength) Set(potentialChild)
                 else children + potentialChild
        (true, Pali(left, right, newChildren))
      }
    }

    /**
     *  Is this Palindrome a single character?
     */
    private def isASingleChar = left == right

    /**
     * Generate a pretty-print nested and intended version of all the Palis
     * that this one represents.
     */
    override def toString: String = toString("\n")

    /**
     * Generate a pretty-print nested and intended version of all the Palis
     * that this one represents.
     * @param indent is "\n <some spaces> "
     */
    def toString(indent: String): String = {
      if (children.isEmpty)
        indent +
          (if (length == 1) string(left).toString
          else string(left) + (if (width == 2) "" else "-") + string(right))
      else {
        val childStrings = children.map(_.toString(indent + "  ")).mkString(", ")
        indent + string(left) + childStrings + indent + string(right)
      }
    }

    /**
     * Generate a Sequence of Strings of the palindromes this Pali represents.
     */
    def toString2: Seq[String] = {
      if (children.isEmpty)
        Seq({
          if (length == 1) string(left).toString
          else string(left) + (if (width == 2) "" else "-") + string(right)
        })
      else {
        val childStrings = children.map(_.toString2).toList.flatten
        childStrings.map((s: String) => string(left) + s + string(right))
      }
    }
  } // End of class Pali

  /**
   * Add childPali as a new child (using addChild) to each of the Pali's in palis.
   * For each potential parent, return (Boolean, Pali) where Boolean is true or false
   * depending on whether the child was added to the parent. Pali is either the
   * parent with the new child or the original Pali -- without the new child.
   */
  private def addChildToParents(childPali: Pali, palis: Seq[Pali]): (Boolean, Seq[Pali]) = {
    if (palis.isEmpty) (false, Seq())
    else {
      val insertions = palis.map(_.addChild(childPali))
      val (acceptedList, paliList) = insertions.unzip
      val wasInsertedSomewhere = acceptedList.exists(x => x)
      (wasInsertedSomewhere, paliList)
    }
  }

  /**
   * Return a Seq of Pali objects. Each stores pointers to
   * left and right characters that are the same. The children set is empty.
   * Later these will be embedded inside each other to build complete palindromes.
   * To test findPairs, remove the private and call
   *
   * > PairwisePaliSolver(<some string>)).findPairs
   */
  private def findPairs: Seq[Pali] = {
    for {
      left: Int <- 0 to string.length - 1;
      right: Int <- left to string.length - 1;
      if (string(left) == string(right))
    } yield new Pali(left, right)
  }

  /**
   * This is the method that does all the work. It takes the pairs generated
   * by findPairs and inserts one into another until no more insertions are
   * possible. At that point, all the palindromes will have been discovered.
   * The Palis in the returned Seq cannot be inserted into each other.
   *
   */
  private def pairsToPalis(palis: Seq[Pali]): Seq[Pali] = {
    if (palis.isEmpty) Seq()
    else {
      /* Sort the palis by width. Since each child must have a smaller width 
       * than its parent, no Pali can be inserted into another Pali that
       * is closer to the front of the list. This simplifies the insertion algorithm. 
       */
      val sortedPalis = palis.sortWith((a: Pali, b: Pali) => a.width < b.width)
      /*
       * Add the first Pali to each of the rest of the Palis if possible. If it 
       * can be added to any Pali, don't keep it in the list. If not keep it.
       * result will the same list of Palis as sortedPalis.tail except that some
       * of them may have sortedPalis.head inserted as a child.
       */
      val (wasInserted, result) = addChildToParents(sortedPalis.head, sortedPalis.tail)
      /* 
       * Call this method recursively on the rest of sortedPalis. newSeq will have
       * all the palis in sortedPalis.tail inserted into every other pali in 
       * sortedPalis.tailto the extent possible. The final question is whether to
       * keep sortedPalis.head. If it has been inserted somewhere, don't keep it.
       * If not, keep it as the head of the new Seq.
       */
      val newSeq = pairsToPalis(result)
      // Return the result
      if (wasInserted) newSeq else sortedPalis.head +: newSeq
    }
  }

  /**
   *  The main control.
   */
  def solve: Seq[Pali] = {
    val pairs: Seq[Pali] = findPairs // Find the initial pairs
    val palis = pairsToPalis(pairs) // Build the maximal Palis
    val maxLength = palis.map(_.length).max // maxLength is the length of the longest Pali
    palis.filter(_.length == maxLength) // Keep only Palis of that length
  }

}