Please clone the starter code linked from Canvas (with `git clone --recursive` so that you also clone the submodules), install its dependencies with `npm install`, and use "File" → "Open Workspace…" to open your clone in VSCode.  Please do not run the app yet—it contains spoilers.

--------------------------------------------------------------------------------

# Graph Search vs. Dynamic Programming

*   Idea behind *graph search* design:
    *   Frame the problem as a problem on a graph
    *   Explore vertices and edges using a worklist algorithm
    *   Compute a subproblem result for each vertex
    *   Postprocess to extract a final result

*   Idea behind *dynamic programming* design:
    *   Frame the problem as a problem on a directed acyclic graph (DAG)
    *   Explore vertices in topological order
    *   Compute a subproblem result for each vertex
    *   Postprocess to extract a final result

--------------------------------------------------------------------------------

# Problem 1:

As long as you take no more than 10 kg, you may choose as many as you want of each of these items:

*   Item A weighs 3 kg and is worth $10.
*   Item B weighs 4 kg and is worth $14.

What choice of items gives you the maximum total value?

Example: The selection ⟅B, B⟆ weights 8 kg and has value $28.  But there is a more valuable choice of items.

# Problem 2:

You are placing linebreaks in the following paragraph (where words are represented by 'x's):

> x x x x xxxx xxxx

so that every line is at most seven characters long, including spaces.  The penalty for not filling a line is the number of unused spaces on that line squared.  What wrapping gives the minimum possible total penalty?

Example: The wrapping

> x x x x
> xxxx
> xxxx

has a total penalty of `(7 - 7)² + (7 - 4)² + (7 - 4)² = 0 + 9 + 9 = 18`.  But there is a wrapping with a lower total penalty.

--------------------------------------------------------------------------------

# Dynamic Programming for the Unbounded Knapsack Problem

Problem: Subject to an integer weight limit, what choice of items (allowing repeats) from a collection of items with positive integer weights gives the maximum total value?

## DAG

*   Edges (actions):
    *   … or
    *   …
*   Vertices (situations):
    *   …
*   Edge weights:
    *   …
*   Topological order:
    *   …
*   Goal:
    *   …

## Backpointer Class

*   Information for the final result:
    *   …
*   Information to go back:
    *   …
*   Information to compare quality:
    *   …

## Choosing a Backpointer

*   Exhaustive search:
    *   Generate ….
    *   Check that ….

## Example

*   Item Z ….
*   Item A weighs 3 kg and is worth $10.
*   Item B weighs 4 kg and is worth $14.

      Vertex         Backpointer      Notes for Humans
    -----------  -------------------  ----------------
    Weight (kg)   Item   Total Value  (Back to Weight)
    -----------  ------  -----------  ----------------
              0  [none]           $0  ⊥
              1  Item …            …  …
              2  Item …            …  …
              3  Item …            …  …
              4  Item …            …  …
              5  Item …            …  …
              6  Item …            …  …
              7  Item …            …  …
              8  Item …            …  …
              9  Item …            …  …
             10  Item …            …  …

    Reversed Path
    ----
    10 ← (Item …) ← …

--------------------------------------------------------------------------------

# Dynamic Programming for the Line-Wrapping Problem

Problem: Wrap a paragraph to a line length, minimizing the sum of the squares of the lengths of unused space on each line.

## DAG

*   Edges (actions):
    *   …
*   Vertices (situations):
    *   …
*   Edge weights:
    *   …
*   Topological order:
    *   …
*   Goal:
    *   …

## Backpointer Class

*   Information for the final result:
    *   …
*   Information to go back:
    *   …
*   Information to compare quality:
    *   …

## Choosing a Backpointer

*   Exhaustive search:
    *   Generate ….
    *   Check that ….

## Example

>  x x x x xxxx xxxx
> 0 1 2 3 4    5    6

    Vertex          Backpointer
    ------  -----------------------------
     Index  Previous Index  Total Penalty
    ------  --------------  -------------
         0               ⊥              0
         1               …              …
         2               …              …
         3               …              …
         4               …              …
         5               …              …
         6               …              …

    Reversed Path
    ----
    6 ← …