Warning! You are probably being recorded (and transcribed).
Approximate overview
Can you show the different styles?
GNU Style
int
factorial (int n)
{
if (n <= 0)
{
return 1
}
else
{
return n * factorial (n - 1);
}
} // factorial
Google Java Style
int factorial(int n) {
if (n <= 0) {
return 1;
} else {
return n * factorial(n-1);
}
}
Many of you use
int factorial(int n) {
if (n <= 0)
{
} else
{
}
}
What are the policies for using LaTeX?
You can look up the different LaTeX things, but you CANNOT use AI to generate your LaTeX or to translate from one format to LaTeX.
You can use Pandoc to translate to LaTeX.
Given a set of stamp values \(V = { v_1, v_2, ... v_n }\) and a total cost, \(C\), find the fewest stamps that exactly sum to \(C\).
A greedy solution can work.
Example: 1, 5, 10, 25, and any \(C\).
But it won’t always work.
Example: 1, 3, 8, 14 and \(C = 16\)
Find every way to make \(C\), choose the one with the smallest number of stamps.
Also a recursive solution.
We’ll design a function, stamps(V,C), that tells you the minimum
number of stamps. (We can modify it to tell you what those stamps are.)
stamps(V,0) = 0
stamps(V,C) = min(1 + stamps(V, C-v1), 1 + stamps(V, C-v2), ...)
Refactor
stamps(V,0) = 0
stamps(V,C) = 1 + min(stamps(V, C-v1), stamps(V, C-v2), ...)
Hack to limit it to stamps that are less than or equal to the cost
stamps(V,negative) = infinity
stamps(V,0) = 0
stamps(V,C) = 1 + min(stamps(V, C-v1), stamps(V, C-v2), ...)
Observation: If there is no solution (e.g., because we have no one-cent stamp), we will likely get ininity as an answer.
For our example
\(V = { 14, 8, 3, 1 }\)
stamps(V, 16)
1 + min(stamps(V, 2), stamps(V, 8), stamps(V, 13), stamps(V, 15))
stamps(V, 2) = 1 + min(stamps(V, -12), stamps(V, -6), stamps(V, -3), stamps(V, 1)
stamps(V, -12) = infinity
stamps(V, -6) = infinity
stamps(V, -3) = infinity
stamps(V, 1) = 1 + min(...., stamps(V, 0)) = 1
stamps(V, 2) = 1 + 1 = 2
stamps(V, 8) = 1 + min(stamps(V, -6), stamps(V, 0), stamps(V, 5), stamps(V, 7))
stamps(V, 8) = 1 + min(infinity, 0, stamps(V, 5), stamps(V, 7))
stamps(V, 5) = 1 + min(stamps(V, -9), stamps(V, -3), stamps(V, 2), stamps(V, 4))
stamps(V, 5) = 1 + min(infinity, infinity, stamps(V, 2), stamps(V, 4))
stamps(V, 2) = 1 + min(stamps(V, -12), stamps(V, -6), stamps(V, -1), stamps(V, 1))
stamps(V, 2) = 1 + min(infinity, infinity, infinity, stamps(V, 1))
stamps(V, 1) = 1 + min(stamps(V, -13), stamps(V, -7), stamps(V, -2), stamps(V, 0))
stamps(V, 1) = 1 + min(infinity, infinity, infinity, 0) = 1
stamps(V, 2) = 1 + min(infinity, infinity, infinity, 1) = 2
stamps(V, 4) = 1 + min(stamps(V, -10), stamps(V, -4), stamps(V, 1), stamps(V, 3))
stamps(V, 4) = 1 + min(infinity, infinity, stamps(V, 1), stamps(V, 3))
stamps(V, 1) = 1 + min(stamps(V, -13), stamps(V, -7), stamps(V, -2), stamps(V, 0))
stamps(V, 1) = 1 + min(infinity, infinity, infinity, 0) = 1
How much work does this do?
| At each stage, we do $$ | V | $$ recursive calls |
| So this is approximately $$ | V | ^C$$ |
Can we do better?
Yes! Take advantage of our observation that we are recomputing the same value again and again and again.
Idea: Make a table of the values we’ve computed.
0 1 2 3 4 5 6
+---+---+---+---+---+---+---+
| 0|inf|inf|inf|inf|inf|inf|
+---+---+---+---+---+---+---+
Rewrite our algorithm to use the table
stamps(V, C)
if (C < 0)
return inf
else (C == 0)
return 0
if table[C] < infy
return table[C]
else
table[C] = 1 + min(stamps(v1, C-v1), stamps(v2, C-v2), ...)
return table[C]
You never fill in a space more than once. There are \(C\) spaces to fill in. So, even with all the recursive calls, this is \(O(C \times |V|)\).
Can we fill out the table iteratively, rather than recursively?
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 0|inf|inf|inf|inf|inf|inf|inf|inf|inf|inf|inf|inf|inf|inf|inf|inf|
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
fillTable(V, C)
for c in 1:C
table[c] = 1 + min(lookup(table,c-v1), lookup(table,c-v2), ...)
lookup(table, x)
if (x < 0)
return infinity
else
return table[x]
stamps(V, C)
table = fillTable(V, C)
return table[C]
Improving the algorithm
fillTable(V, C)
for v in V
table[v] = 1
for c in 1:C
if (table[c] == infy)
table[c] = 1 + min(lookup(table,c-v1), lookup(table,c-v2), ...)
An approach to certain kinds of optimization problems, originally designed by Richad Bellman at Bell Labs in 1950’s.
Given an optimization problem, do three basic things
In our stamps problem, the following expression was our recursive way of computing (or thinking about the issue)
stamps(V, C) = 1 + min(stamps(V, C-v1), stamps(V, C-v2), ...)
In our stamps problem, we made it more efficient by using a one-dimensional table.
Note: We may move on to two-dimensional and three-dimensional tables.
How can we modify the stamps solution above to extract the list of stamps?
fillTable(V, C)
for v in V
table[v] = 1
for c in 1:C
if (table[c] == infy)
table[c] = 1 + min(lookup(table,c-v1), lookup(table,c-v2), ...)
define lookup(table, x)
if (x < 0)
return infinity
else
return table[x]
stamps(V, C)
table = fillTable(V, C)
return table[C]
You have a bunch of items, each of which has a value and a weight, both of which are positive integers.
We can represent these as \((v_i, w_i)\) pairs.
You also have a designated total weight, \(W\), that you can carry.
Which items should you grab to maximize the total value of grabbed items?
What is your recursive formulation? I.e, given a set of pairs, P, and a total weight, W, what does your computation depend upon?
Sam will ask you those questions at the start of next class. Be ready.
Two key issues for DP: