Recitation 13
Recitation notes for the week of November 27, 2017.
A Reminder for Homework 9 Q1
Note on Timeouts on Homework 9 Q1
For this problem the total timeout for Autolab is 480s, which is higher the the usual timeout of 180s in the earlier homeworks. So if your code takes a long time to run it'll take longer for you to get feedback on Autolab. Please start early to avoid getting deadlocked out before the feedback deadline.
Also for this problem, C++ and Java are way faster. The 480s timeout was chosen to accommodate the fact that Python is much slower than these two languages.
Our recommendation
- Either code in
C++orjavaOR - If you want to program in
pythonthen test on first five test cases and test for all 10 only if you pass the first five.
Recap of last week's recitation
Note
Link to last week’s recitation to answer any questions one may have.
Dynamic Programming
(Credit: Original Notes by Zulkar Nine.)
Here is one way to think about Dynamic Programming algorithm:
- Divide problem into subproblems.
- Solve each subproblem.
- Combine to get original solution.
Divide and Conquer v/s Dynamic Programming
The above outline looks a lot like divide and conquer! The table below lists the differences:
| Divide and Conquer | Dynamic Programming |
| Independent subproblems | Overlapping subproblems |
| Solve top down | Solve bottom up (or top down using memoization) |
| Usually recursive | Backtracking |
Example: Divide and Conquer vs. Dynamic Programming Solutions
Fibonacci Sequence
This is the sequence $0,1,1,2,3,5,8,13,\dots$.
More formally, the sequence is defined as for any $n\ge 2$: \[\text{fib}[n] = \text{fib}[n-1] + \text{fib}[n-2],\] with the base case \[\text{fib}[0] = 0 \text{ and } \text{fib}[1] = 1.\]
Below is the obvious recursive (or divide and conquer algorithm):
Divide and Conquer Algorithm
fib(n):
#Input: n
#Output: fib[n]
if n==0:
return 0
else if n==1:
return 1
else:
return fib(n-1) + fib(n-2)
Exercise (for home)
Show that the above algorithm ends up using $2^{\Omega(n)}$ additions.
Of course the above is wasteful since we re-solve the same fib(i) multiple times. In this case the dynamic programming algorithm is the obvious one you would think of given the original recursion for fib[n]. I.e.
Dynamic Programming Algorithm
#Input: n
#Output: fib[n]
fib[0]=0
fib[1]=1
for i = 2 to n:
fib[i] = fib[i-1] + fib[i-2]
return fib[n]
Note
The above algorithm has $O(n)$ additions and takes $O(n)$ space.
One should only need $O(1)$ amount of space if one only keeps track of the last two elements.
A Digression
The stuff below is not relevant to dynamic programming but is a neat trick that you should know that is helpful in solving certain recursions.
Even faster computation
It turns out that one can compute fib[n] with $O(\log{n})$ multiplications and additions.
The trick in arguing the above is to use matrix-vector multiplication (recall Homework 3). In particular, first represent the recurrence for fib[n] as a matrix vector product, like so
\[\begin{pmatrix} \text{fib}[n]\\ \text{fib}[n-1]\end{pmatrix} = \begin{pmatrix} 1 & 1\\ 0 &1\end{pmatrix} \cdot \begin{pmatrix} \text{fib}[n-1]\\ \text{fib}[n-2]\end{pmatrix}.\]
Exercise 1
Convince yourself that the above identity holds.
Now, let us define the $2\times 2$ matrix: \[ M = \begin{pmatrix} 1 & 1\\ 0 &1\end{pmatrix}.\] In other words, one can re-state the identity above as \[\begin{pmatrix} \text{fib}[n]\\ \text{fib}[n-1]\end{pmatrix} = M \cdot \begin{pmatrix} \text{fib}[n-1]\\ \text{fib}[n-2]\end{pmatrix}.\] This implies the following identity
Identity
\[\begin{pmatrix} \text{fib}[n]\\ \text{fib}[n-1]\end{pmatrix} = M^{n-1}\cdot\begin{pmatrix} \text{fib}[1]\\ \text{fib}[0]\end{pmatrix}.\]Exercise 2
Convince yourself that the above identity holds.
Next we note that $M^{n-1}$ can be computed very efficiently:
Exercise 3
Argue that $M^{n-1}$ can be computed with $O(\log{n})$ additions and multiplications.
Hint
Generalize the algorithm for Question 2 on Homework 8.
We are now ready to show that fib[n] can be computed very efficiently:
Exercise 4
Show that $\text{fib}[n]$ can be computed with $O(\log{n})$ additions and multiplications.
Billboard Problem
The Problem
There are $n$ sites for a billboard, each at a location $x_i$ and each site generates $r_i$ revenue. (You can assume that $x_1\le x_2\le \cdots \le x_n$.)
The goal is to pick a subset of sites that maximizes the total revenue with the constraint that if sites $x_i$ and $x_j$ (for any $i\neq j$) are chosen, then: $|x_i - x_j| > 5$.
Here is an example input: 
Bottom-Up (Dynamic Programming Style)
Consider the sub-problem, where we only have the first site: 
Note that in this case the optimal solution is to pick the only site, which means he have $\text{OPT}(1) = 5$.
Now consider the sub-problem where we have the first two sites
In the above case, we have two options:
- If we don’t pick site $2$, then the optimal solution is the same as above and we get $\text{OPT}(1)=5$.
- If on the other hand, we pick site $2$, we have to eliminate all sites within a 5 mile radius of site $2$ (which in this case is site $1$) and we get a revue of $r_2=6$.
Now consider the sub-problem where we have the first three sites
We again two two options:
- Do not pick site $3$, in which case we get revenue $\text{OPT}(2)$.
- Pick site $3$, in which case we will have to eliminate site $2$ and get a total revenue of $\text{OPT}(1) + r_3$.
Generic Formula
Note to TA
Try to get students to come up with this for you.
Definition
For any $j\in [n]$, define $e_j$ to be the closest site that is outside of $5$ mile radius from site $j$. That is, $e_j$ is the largest $i < j$ such that $x_i < x_j-5$.
In parallel with the weighted interval scheduling problem, the above recurrence leads to the following algorithm:
Dynamic Programming Algorithm
#Input: x[] and r[]
#Output: OPT(n)
M = [ ] #Stores value of OPT
M[0] = 0
M[1] = r1
compute e[j] for j = 1..n #This can be done in O(n) time
for j = 2...n:
M[j] = max( M[j-1], M[e[j]] + r[j])
return M[n] #This will be the largest revenue
$O(n)$ Runtime Analysis
Exercise (for home)
Given $x_1\le x_2\le \cdots x_n$, compute $e_j$ for $j\in [n]$ in $O(n)$ time.
Hint
If all the $x_j$'s are integers then this is simple. If not (i.e. if the $x_j$ can be real numbers), then consider the following. Create a new list of values $y_j=x_j-5$ for $j\in [n]$. Then merge the $x$ and $y$ arrays (note they both are sorted) and then use this merged sorted array to compute the $e_j$ values.
Given the above it is easy to see that the algorithm can be implemented in $O(n)$ time.