Recurrent Problems
The topic of this first chapter is a -slight pause- recurring theme in mathematics and all of computer science. -audience laughter-To the uninitiated, recurrent problems are equations that are written in terms of themselves.
Here's a random example as a function, but these are often notated with a subscript as well
$$ S(n) = 2S(n/2), S(1) = 2 $$
$$ S_n = 2S_{n/2} $$
And by plugging in values of n shows us that this is just $2^n$ for n greater than 0
$n$ $S_n$
1 | 2
2 | 4
3 | 8
4 | 16
It's very similar to differential equations, but in this case we're given discrete steps, which makes it easy for us problem-slayers to comprehend it for a few definite cases, while we search for a pattern.
$$ R_n = 2R_{n-2} + 2R_{n-1}, R_0 = 1, R_1 = 2$$
The chapter itself only covers three problems but generalizes them. The focus being not on any specific recurrences, but rather to hone the cleverness required to look at a specific problem and frame it to find a nice recurrent pattern.
Hanoi
The legacy intro recurrence is the tower of hanoi. Visually, it's not a very interesting problem, but people teach it out of tradition.
The premise is: we have three disk-holders $A$, $B$, $C$. On $A$, we have a tower of $n$ disks. The disks increase in size from top to bottom, so that the largest disk is on the bottom. We want to move these disks to point C, but we can only move one at a time, and larger disks cannot be placed on smaller disks. Here's a robot doing it.
We want to find out the number of moves it takes to move the tower from $A$ to $B$, given the size $n$. We'll call this number $T_n$. The first lesson about recurrences is that you need to play with them to wrap your mind around them.
Here's some CG demonstration
Hanoi with n = 1
We just move our disk to point C.
with n = 2
-#-#-# n = 3
The rest of the figures are left as an exercise to the reader.
---------
After playing around with it, we can see for the first few n we get
$n$ $T_n$
1 | 1
2 | 3
3 | 7
4 | 15
Since this chapter is about recurrences, our technique for solving the hanoi must work for any n. In other words, the number of iterations for n must be written in terms of the number of iterations for a smaller n.
Here's one approach: simplify our n case to be the same as our n=2 case.
So our solution here depends on solving hanoi for the n-1 plates twice, just so we can move the bottom plate. In other words, we have two sub-hanoi movements for the n-1 plates, and only one additional movement from the new plate. We can express this relation as:
$$T_n = 2T_{n-1} + 1$$
So we play with this and see the pattern with an expanded version
$T_0 = 1$
$T_1 = 2T_0 + 1 = 2 + 1$
$T_2 = 2T_{1} + 1 = 2(2T_0 + 1) + 1 = 4 + 2 + 1$
$T_3 = 2T_{2} + 1 = 2(2(2T_0 + 1) + 1) + 1 = 8 + 4 + 2 + 1$
$T_4 = 2T_{3} + 1 = 2(2(2(2T_0 + 1) + 1) + 1) + 1 = 16 + 8 + 4 + 2 + 1$
$T_N = 2T_{n-1} + 1 = 2(2( ... 2(2T_0 + 1) + 1 ... ) + 1) + 1 = 2^ n + 2^{n-1} + ... + 2^3 + 2^2 + 2^1 + 2^0$
By unfolding this we see we get the summation of powers of 2 from 0 to n. This gets us an interesting closed form that arises nicely because of a property of binary numbers. See if you can find this nice closed form!
The premise is: we have three disk-holders $A$, $B$, $C$. On $A$, we have a tower of $n$ disks. The disks increase in size from top to bottom, so that the largest disk is on the bottom. We want to move these disks to point C, but we can only move one at a time, and larger disks cannot be placed on smaller disks. Here's a robot doing it.
We want to find out the number of moves it takes to move the tower from $A$ to $B$, given the size $n$. We'll call this number $T_n$. The first lesson about recurrences is that you need to play with them to wrap your mind around them.
Here's some CG demonstration
Hanoi with n = 1
We just move our disk to point C.
with n = 2
-#-#-# n = 3
The rest of the figures are left as an exercise to the reader.
---------
After playing around with it, we can see for the first few n we get
$n$ $T_n$
1 | 1
2 | 3
3 | 7
4 | 15
Since this chapter is about recurrences, our technique for solving the hanoi must work for any n. In other words, the number of iterations for n must be written in terms of the number of iterations for a smaller n.
Here's one approach: simplify our n case to be the same as our n=2 case.
So our solution here depends on solving hanoi for the n-1 plates twice, just so we can move the bottom plate. In other words, we have two sub-hanoi movements for the n-1 plates, and only one additional movement from the new plate. We can express this relation as:
$$T_n = 2T_{n-1} + 1$$
So we play with this and see the pattern with an expanded version
$T_0 = 1$
$T_1 = 2T_0 + 1 = 2 + 1$
$T_2 = 2T_{1} + 1 = 2(2T_0 + 1) + 1 = 4 + 2 + 1$
$T_3 = 2T_{2} + 1 = 2(2(2T_0 + 1) + 1) + 1 = 8 + 4 + 2 + 1$
$T_4 = 2T_{3} + 1 = 2(2(2(2T_0 + 1) + 1) + 1) + 1 = 16 + 8 + 4 + 2 + 1$
$T_N = 2T_{n-1} + 1 = 2(2( ... 2(2T_0 + 1) + 1 ... ) + 1) + 1 = 2^ n + 2^{n-1} + ... + 2^3 + 2^2 + 2^1 + 2^0$
By unfolding this we see we get the summation of powers of 2 from 0 to n. This gets us an interesting closed form that arises nicely because of a property of binary numbers. See if you can find this nice closed form!
Double Hanoi
A simple variation of the Hanoi problem is to double the disks to $2n$, with adjacent pairs of 2 having the same size. We'll call this recurrence $D_n$ Disks of the same size are allowed to sit on each other. Before reading further can you guess the number of steps to move the tower from A to C in terms of the original Hanoi recurrence $T_n$ ?
We might think we can just move each double-tile as if it were a tile, and use the same hanoi procedure for solving this but with twice the steps.
Just by doubling each step, $D_n = 2T_n$, our final ordering will look something like this.
Doubling Hanoi steps is perfectly valid, and is actually the fastest solution. This problem illustrates a very important concept in recurrences: relating a more complicated problem to a simpler one. In other words, we can often express complicated recurrences in terms of simpler ones.
Final note for this problem, for n=3, we see that each odd numbered double-tile is "upside down". Problem for reader: does this hold true in general?
Order Preserved Hanoi
Let's call the number of steps to reach this ordered end-state $Y_n$. Unfortunately, this means we can't just use a double-hanoi strategy for moving plates. Though that gives us a lower-bound for our recurrence.
We can brute force this for a few n. Maybe say, after 3 it gets hard.
$n$ $Y_n$
1 | 3
2 | 11
3 | ??
Again, to solve this, we have to play around with it until we find a general pattern. One general way to solve this is.
(1) Move all disks except for the bottom 2 to position C
(2) Move both bottom disks to position B. They will be upside down
(3) Move all disks from C to A
(4) Move bottom disks from B to C. They will be right-side up
(5) Move disks from A to C in order. Based on the double-hanoi, these will have some set upside-down. Let's simply assume all are upside down, so placing these in order on top of C will require 3 moves per (2n-2) remaining discs.
From this simple description we get the recurrence
$$ Y_n \leq D_n + 2 + D_n + 2 + 3(2n-2) = 2D_n + 6n - 4 = 4T_n + 6n - 4$$
Since we skipped some details, we can think of this as the upper bound. You can find a more detailed solution by analyzing the pattern of which sets get flipped.
Lines in the Plane
The second problem the text actually introduces in the chapter is "How many regions can we define with n lines". Let's call this $L_n$ This is a pretty important problem for 2D plane splitting, and more fun than the hanoi problem.
The first step, as always, is to play around with it. Let's see what we can get with the first few n.
The first step, as always, is to play around with it. Let's see what we can get with the first few n.
So we may not see a particularly obvious pattern.
$n$ $L_n$
0 | 0
1 | 2
2 | 4
3 | 7
The greater question here, is what creates the regions? What even is a region? It's a tricky question that you should try to think about yourself, but as a simplification it here in the context of lines. That is, a region is a byproduct of the existence and intersections of lines. With this in mind, we should frame the problem not in terms of "arranging lines to make volumes" but "how do line intersections create regions". From our simple pattern, we see that for n=2, the addition of a line creates two regions because it intersects with a line, therefore splitting two regions that the intersectee was separating. In the case of n=3, our new line intersects with two lines. In the path of our one line, we can maximally intersect with two other regions(n-1) and create n new regions. Some intuition: Two lines as divisors in one dimension(the dimension of the new line) can maximally separate three regions. We therefore maximally split each of these regions.
Anyway, from this we can create the closed form:
$$L_n = L_{n-1} + n$$
$$L_0 = 0$$
We can find the closed form by expanding this
$L_0 =1$
$L_1 = 1 + 1$
$L_2 = 1 + 1 + 2$
$L_3 = 1 + 1 + 2 + 3$
$L_n = 1 + 1 + 2 + 3 + ... + n-1 + n = 1 + (n + 1) + (n -1 + 2) + ... = 1 + \frac{n(n+1)}{2}$
Question for the reader: is any particular placement of lines necessary to create the max number of regions from n lines? What are the restrictions, if any?
Lines in Plane: Closed Region Edition
Building on our previous problem, we want to know the max number of closed regions(i.e. completely surrounded by lines you can make with n lines. Let's call this $C_n$.
To maximally avoid work, let's relate this to the previous problem somehow.
After we've defined a closed region with n=3, we can recreate the previous problem's sequence $L_n$ starting from 0. In other words, one way to derive the solution is to say $C_n = L_{n-3}, n\geq3$
Another more concise interpretation you can do from principles, is to recognize that for each n lines we intersect, we get n+1 regions, but that two of those are on the boundaries. In other words, if we have n lines on the plane defining $L_n$ regions, we know that $2n$ of them will be open regions, so we can use the solution $C_n = L_n - 2n, n\geq3$ as well.
On a final note, the trickiest variation of this problem uses zig-zag lines instead of regular ones. I encourage the reader to try it out using the basic principles we observed here.
Josephus Problem
The legend of this problem is that Josephus was a general in the Jewish-Roman war. Being sieged by the Romans and with no chance of winning, the general and his soldiers decided to commit suicide rather than being captured. They decided to kill every second man to ensure nobody would try getting out of it. Of course, Josephus wasn't into any of that suicide nonsense, so the story goes he quickly found out which position to stand in to ensure that he would be the last person alive.
Aside from getting out of your weekend suicide cults, this problem has a lot of general implications in recurrences, so it's worth paying attention to.
Formally, given n people in a circle numbered $1..n$, we want to find the final survivor $J_n$. To illustrate how it works, let's look try this with 8 people.
Aside from getting out of your weekend suicide cults, this problem has a lot of general implications in recurrences, so it's worth paying attention to.
Formally, given n people in a circle numbered $1..n$, we want to find the final survivor $J_n$. To illustrate how it works, let's look try this with 8 people.
So we can see $J_8$ = 1
So this problem has a few ways to tackle, but we should always try to get a handle on it by trying it for a bunch of small cases first. This specific problem might take more to see a pattern.
$n$ $J_n$
1 | 1
2 | 1
3 | 3
4 | 1
5 | 3
6 | 5
7 | 7
8 | 1
9 | 3
10 | 5
11 | 7
12 | 9
13 | 11
14 | 13
15 | 15
16 | 1
17 | 3
We might observe a few things while doing the work. First that the result is never even(all evens get wiped out in the first loop). Second, that the survivor is 1 for every power of two, and in-between those powers, we add 2 for each step of our iteration. In other words $J_{2^m+l} = 2l+1 , 0\leq l < 2^m$.
This observation can give us some intuition to the mechanisms of the problem. Since it works in powers of two, and since this is a recurrence problem, the recurrent form probably has to do something with multiples of two, or halving.
In-fact, if we observe our first round above again, we'll notice that we end up with the same situation as n=4, but with each person'd id being multiplied by 2, then subtracted by 1. In other words, $J_8 = 2*J_4 - 1$. We can test this and find in general that $J_{2n} = 2J_n - 1$.
However, what about odd cases?
If we kill an extra person in the first round(i.e. the first guy), then we end up with a recurrent situation where our next "lap" is $n/2$ rounded down, with each dude's index multiplied by 2 and plus 1. In other words $J_{2n+1}= 2J_n + 1$.
For the closed form, we can actually use the intuition with respect to powers of two, using the table. But what if you wanted to use the recurrence to find the closed form? Well, you could find it using any of the methods in the next section.
For a fun interactive visualization, compile josephus.c found here, and run your own peer-pressure death ring!
So this problem has a few ways to tackle, but we should always try to get a handle on it by trying it for a bunch of small cases first. This specific problem might take more to see a pattern.
$n$ $J_n$
1 | 1
2 | 1
3 | 3
4 | 1
5 | 3
6 | 5
7 | 7
8 | 1
9 | 3
10 | 5
11 | 7
12 | 9
13 | 11
14 | 13
15 | 15
16 | 1
17 | 3
We might observe a few things while doing the work. First that the result is never even(all evens get wiped out in the first loop). Second, that the survivor is 1 for every power of two, and in-between those powers, we add 2 for each step of our iteration. In other words $J_{2^m+l} = 2l+1 , 0\leq l < 2^m$.
This observation can give us some intuition to the mechanisms of the problem. Since it works in powers of two, and since this is a recurrence problem, the recurrent form probably has to do something with multiples of two, or halving.
In-fact, if we observe our first round above again, we'll notice that we end up with the same situation as n=4, but with each person'd id being multiplied by 2, then subtracted by 1. In other words, $J_8 = 2*J_4 - 1$. We can test this and find in general that $J_{2n} = 2J_n - 1$.
However, what about odd cases?
If we kill an extra person in the first round(i.e. the first guy), then we end up with a recurrent situation where our next "lap" is $n/2$ rounded down, with each dude's index multiplied by 2 and plus 1. In other words $J_{2n+1}= 2J_n + 1$.
For the closed form, we can actually use the intuition with respect to powers of two, using the table. But what if you wanted to use the recurrence to find the closed form? Well, you could find it using any of the methods in the next section.
For a fun interactive visualization, compile josephus.c found here, and run your own peer-pressure death ring!
Main Methods Discovered
Method 0, the most important method, is just writing stuff and seeing what happens. This is also known as the brute-force strategy, but with your mind. However these are the formal methods introduced in this chapter.
Guess-and-Induct
Say you have a recurrent form for $J_n$, and a hypothetical closed form f(n). All you need to do is show that $J_{n+1} = f(n+1)$, and one case for a real value $k$, so we can deduce that our equality is true for any $k+m$ where $m\geq0$.
Repertoire Method
basis of the trick
$$T_n = 1 + T_{n-1} \\ T_0 = 0$$ and $$S_n =S_{n-1} + n \\ S_0 = 0$$
and we know the closed forms of each. $$T_n = n,\\ S_n = \frac{n^2+n}{2}$$
Say we now have a new recurrence, $G_n = G_{n-1} + 1 + n$. We can recognize that these components are the same as the recurrences we just solved, and represent our new problem in terms of them $G_n = T_n + S_n$, which implies that $G_n = n + \frac{n^2+n}{2}$, the sum of their closed forms. Moreover, any linear combination of those solutions forms a new recurrence whose closed form is the linear combination of those closed forms.
Since we know our recurrences are associative, we can solve a seemingly complex recurrences by working "backwards" and solving simpler recurrences and adding them up. Let's do a real example.
Say we want to find the closed form of a recurrence:
$$R_n = R_{n-1} + 3 + 7n + 3n^2, R_0 = 5$$
Using the repertoire method, we generalize this and instead consider
$$R_0 = \alpha\\R_n = R_{n-1} + \beta + \gamma n + \theta n^2$$
We know that the solution of this will be of the general form
$$R_n = A(n)\alpha + B(n)\beta + C(n)\gamma + D(n)\theta$$
What we then want to do is to test closed-forms of similar recurrences, and gather enough of them to combine for our solution. Working backwards, we look for special cases of our recurrence $R_n$ that we can solve.
Case 1:
Assume closed form
$R(n) = 1, n>0;$
What set of constants make
$R_n = A(n)\alpha + B(n)\beta + C(n)\gamma + D(n)\theta$
true?
$\alpha=1, \beta=\gamma=\theta=0$
Cool, this set of constants gives us a separate recurrence $R_n=R_n-1, R_0 = 1$ where our original closed form is true, that we'll use later.
Case 2:
Same procedure, but we look for a recurrence
$R_n = n^2, R_0 = 0;$
$R_n = n^2 = R_{n-1} + \beta + \gamma n + \theta n^2 = (n-1)^2 + \beta + \gamma n + \theta n^2$
so we do a bit of algebra
$n^2 = n^2 - 2n + 1 + \beta + \gamma n + \theta n^2$
$2n - 1 = \beta + \gamma n + \theta n^2$
and thus we know our closed form is true for constants $\beta = -1$, $\gamma = 2$, $theta = 0$
This gives us the recurrence
$R_n = R_{n-1} +2n - 1, R_0=0; R_n = n^2, n \geq 0$
Case 3:
Let's do the same procedure with $R(n) = n$
$R_n = n, R_0 = 0$
$R_0 = 0$
$R_n=n = (n-1) + \beta + \gamma n + \theta n^2$
$1 = + \beta + \gamma n + \theta n^2$
which is true for constants $\beta=1; \alpha=\gamma=\theta=0$
Case 4:
assume
$R_n = n^3, R_0 = 0$
then again
$R_0 = \alpha = 0$
$R_n=n^3=(n-1)^3 + \beta + \gamma n + \theta n^2 = n^3 - 3n^2 +3n -1 + \beta + \gamma n + \theta n^2$
cancel out the n^3 and
$3n^2 - 3n + 1 = \theta n^2+ \gamma n + \beta $
which we see is true for $\theta = 3, \beta = 1, \gamma = -3$
With our 4 recurrences, we have 4 sets of constants
$\{\alpha = 1, \beta = 0, \gamma = 0, \theta = 0\} = (1)$
$\{\alpha = 0, \beta = 1, \gamma = 0, \theta = 0\} = (2)$
$\{\alpha = 0, \beta =-1, \gamma = 2, \theta = 0\} = (3)$
$\{\alpha = 0, \beta = 1, \gamma = -3, \theta = 3\} = (4)$
With these 4 linearly independent solutions, the values of $\alpha, \beta, \gamma, \theta$ can be solved with a linear combination of these sub-recurrences.
Back, to the original equation, the constants we want are $\{\alpha = 5, \beta = 3, \gamma = 7, \theta = 3\}$
Which we can get with
$$(4) + 5 \cdot (3) + 7 \cdot (2) + 5 \cdot (1)$$
Which also means that the closed form must me
$$n^3 + 5 \cdot n^2 + 7 \cdot n + 5 = R_n, n \geq 0$$
--------
We could also target the individual functions $A(n)$, $B(n)$, $C(n)$, $D(n)$ first, by finding the closed form for a simple component like $R_n = R_{n-1} + n$ which yields a more complicated equation, but a simpler linear combination of solutions. Similarly, if we had known the closed forms for $R_n=$_{n-1} + 1$, $R_n=$_{n-1} + n$, $R_n=$_{n-1} + n^2$ in advance, then we could have just combined them for our solution. In practice, a combined, creative approach always works best.
So, our method is sort of a form of that "relate complex problems to their simpler counterparts" thing I mentioned before, but more formal. It also tells us that many recurrences are linear combinations of simpler/purer recurrences, so getting to know those should let you recognize a seemingly complicated expression that's just a bunch of simpler ones dressed up.
General Recurrences as Base-Changes
The final, but perhaps most general, observation the book makes is with respect to recurrences is to liken them to a base-change.
Let's consider the josephus problem again.
$J_1 = 1$
$J_{2n} =2J_n - 1 $
$J_{2n+1} = 2J_n + 1 $
let's rewrite it in this form
$J_1 = 1$
$J_{2n+j} = 2J_n + \beta_j \quad $ for $ j={0,1}, n\geq 1$ and $\beta_0 = -1, \beta_1 = 1$
if we expand this, we'll continuously divide our input by 2, so let's simplify this by representing our input in base-2 in a series of bits.
$n = (b_mb_{m-1}b_{m-2} \dotso b_1b_0)_2,\quad b_m = 1$
we can expand our josephus recurrence more cleverly now
$J((b_mb_{m-1}b_{m-2} \dotso b_1b_0)_2,\quad b_m = 1)\ =\ 2J((b_mb_{m-1}b_{m-2}...b_1)_2) + \beta_{b_0}$
$= 4J((b_mb_{m-1}b_{m-2} \dotso b_2)_2) + 2\beta_{b_1} + \beta_{b_0}$
$\vdots$
$= 2^mJ((b_m)) + 2^{m-1}\beta_{b_{m-1}} + \dotso 2\beta_{b_1} + \beta_{b_0}$
$= 2^m \cdot 1+ 2^{m-1}\beta_{b_{m-1}} + \dotso 2\beta_{b_1} + \beta_{b_0}$
In a sense, our $\beta_{\{0,1\}}$ values are like "if" conditions, for what value should be in that decimal point. Let's apply this principle to our Josephus problem, with n=100, which in base 2 is 1100100
$$\quad(1\quad1\quad0\quad0\quad1\quad0\quad0)_2 = 100 = n\\
--------
\\\quad(1\quad1\quad{-1}\quad{-1}\quad1\quad{-1}\quad{-1})_2 = J(n) \\
\quad{+64}\quad{+32}\quad{-16}\quad{-8}\quad{+4}\quad{-2}\quad{-1} = J(n) = 73$$
It works quite nicely!
Let's generalize this even further. What if we didn't just do base-2 recurrences but base-n. Well, instead of a 2 in our form, let's make it even more general.
$T_j = \alpha_j, \quad j=\{{1 \dotso d-1}\}$
$T_{d n + j} = c T_n + \beta \quad j=\{{0 \dotso d-1}\}$
wow, looks crazy doesn't it? However, note that only thing determining our input and computing-"base" is the input coefficient d, whereas c should be seen as the output base. In other words, we're building up an actual number that we compute in our output base. So similar to our previous example, we convert our input to digits, but with base d.
$T((b_mb_{m-1}b_{m-2} \dotso b_1b_0)_d,\quad d > b_m > 0) = T((b_mb_{m-1}b_{m-2} \dotso b_1) + \beta_{b_0}$
$= T((b_mb_{m-1}b_{m-2} \dotso b_1) + \beta_0$
$= c^2T((b_mb_{m-1}b_{m-2} \dotso b_2) + c\beta_{b_1} + \beta_{b_0}$
$\vdots$
$= c^{m}T((b_m) + c^{m-1} + \dotso + c\beta_{b_1} + \beta_{b_0}$
$= c^{m}\alpha_{b_m} + c^{m-1}\beta_{b_{m-1}} + \dotso + c\beta_{b_1} + \beta_{b_0}$
$=(\alpha_{b_m}\beta_{b_m}\dotso\beta_{b_2}\beta_{b_1}\beta_{b_0})_c$
Basically, each $\beta_j$ is a case in this number system. If $d=3$, then our $\beta_j$ has three cases based on whether the digit is 0, 1, or 2.
Let's wrap this up with a concrete example. Say we have a base-3 recurrence
$f(1)\quad\quad\ \ =\ 15$
$f(2)\quad\quad\ \ =\ 7 $
$f(3n)\quad\ \ \ \ =\ 5 f(n) -2$
$f(3n + 1)\ = \ 5 f(n) + 7$
$f(3n + 2)\ =\ 5 f(n) + 32$
and we want to compute this for $n=47=(1202)_3$
Then based on our previous deductions, just convert bases and select cases.
$f((1202)_3) = (15\ 32\ {-2}\ 32\ )_5$
$ = 15 \cdot 5^3 + 32 \cdot 5^2 + (-2) \cdot 5^1 + 32 \cdot 5^0 $
$ = 15 \cdot 125 + 32 \cdot 25 - 2 \cdot 5 + 32 \cdot 1 $
$ = 2697$
Phwew, there you have it. If anything seems unclear or incomplete, please let me know via a comment or email.
The core habit of problem solving isn't just about being satisfied with finishing a problem, but trying to dissect and generalize the solution to that problem in what is a paradoxically obsessed and rational process.
No comments :
Post a Comment