I want to offer a course about algorithms. Somewhat rigorous, but at the same time accessible.
But we need to start with some basics first. We will start by getting a taste of the kind of work we are going to be doing. We are going to be doing proofs about the behavior of algorithms.
In this post I will show you a mathematical proof about numbers.
As with every other post in my blog, I am learning this. So I am writing a course for myself. But I always try to make it accessible to others :D
Reasoning with numbers
Lets start with an interesting observation:
Observation: the sum of any three digits is at most two digits long.
In base 10 we can check this easily by noting that \(9+9+9 = 27\). Yet we would like to make a more general claim.
Lemma 1: For any integer base \(b \geq 2\), the sum of any three digits is at most two digits long.
A lemma is a claim that we need to prove using mathematical reasoning alone. No "empirical evidence" allowed!
Before offering the proof, lets take a moment to reason through what we are even asking!
The way to proceed can be to find out what is the biggest number we can represent with a single base \(b\) digit. Think for example, base 10, where \(9 = 10^1 - 1\). In base 2, we have that \(1 = 2^1-1\). In base 16 (hexadecimal), \(15 = \text{F} = 16^1 - 1\). And so on. Can you see it?
Indeed we should prove this second claim. But it is straightforward enough that we can convince ourselves that it is valid.
- Hint: can you provide an argument to claim that if this is true for \(b=n\) then it must also true for \(b=n+1\). Can you then show that it must be true for \(b = 2\)? What would that argument imply?
Then consider the number \(b^1-1\) which must be the biggest one-digit base \(b\) number. Thus we need to ask, how many digits does \(3(b^1-1)\) has? Now we have enough to attempt a proof.
Proof: First note that as \(b^1-1 > 0\), then \(3(b^1-1)\) must be bigger than \(b^1-1\). If that is the case, then it must also be at least two-digits long, because \(b^1-1\) is the biggest one-digit base \(b\) number!
Second, consider the biggest two-digit base \(b\) number. It must be \((b^2-b^1)+(b^1-1)=b^2-1\).
To help see it, consider the concrete example for base 10.
$$99 = (10^2 - 10) + (10 - 1) =(100-1)=90 + 9 $$
But we can show that:
$$ 3(b-1) \leq b^2-1 $$
If you are not convinced, try checking the inequality for \(b = 2, 3, 4, ...\)
Before continuing, can you offer a resoning why this should be true?
- Hint 1: \(b-1\geq1\)
- Hint 2: what is \(\frac{b^2-1}{b-1}\) ?
We can reason as follows:
$$ \frac{b^2-1}{b-1} = \frac{(b+1)(b-1)}{b-1} = b + 1 $$
But if \(b\geq2\), then \(3 \leq b+1\) and we can reverse the previous reasoning to end up with:
$$ \begin{align} 3 &\leq b+1 \\ 3(b-1) &\leq (b+1)(b-1) \\ 3(b-1) &\leq b^2-1 \\ \end{align} $$
Therefore, by our first statement above \(3(b^1-1)\) must be at least two-digits long. As it is larger than the largest one-digit base \(b\) number. But by the second statement, it cannot be three or more digits long. As it is smaller or equal than the biggest possible two-digit base \(b\) number.
But \(3(b^1-a)\) is the biggest possible number we can have by adding three one-digit number. And it must be two-digits long at most. So there is no other such number that could be more than two digits long.
We must conclude that any sum of three one-digit numbers base \(b \geq 2\) must be at most two digits long. This completes our proof.
Can you see why I said \(b \geq 2\)?
- Hint: Check the second exercise problem above :D
Wow. That was dense.
We can be a little bit more terse when writing proofs, without loosing rigor. As long as we are confident the reader (i.e you from the future) will be able to fill in the blanks.
Terse proof: Let \(A = 3(b-1)\) where \(b-1\) is the biggest one-digit base \(b\) number. And \(B = b^2-1\), with \(B\) being the largest two-digit base \(b\) number. Then, \(A \leq B\). But as \(B\) is two-digits long, \(A\) can only have at most two digits. This completes the proof.
The point is that, you can (and perhaps should) write a reasoning as detailed as you need, to understand it completely. Some proofs are simple enough that we can skip them. Some will need a more elaborate reasoning.
I will take this approach on this posts :D
Try it yourself!: Show that the sum of any two base \(b \geq 2\) one digit numbers has at most two digits. Is that true? Why?
Hint: the reasoning is almost exactly the same. Think, for example that 9 + 9 = 18? Can you generalize this?
Try writing a proof in the comments :D
About this posts
This series is about algorithms and, to a lesser extent, data structures. If you want to follow along, however, please note that I am not aiming this at complete beginners.
I will foolishly assume you are at least familiar with:
- Basic data structures like arrays, lists, trees and hash tables.
- Big O notation. You know what "linear time" means.
- You are at least willing to follow through some mathematical proofs.
That being said. I always try to keep my writing as accessible as possible :D
This are basically my notes from taking the "Intro to graduate algorithms" class from Georgia tech. Which is freely available online (I am not enrolled).
As you can probably imagine from the name, it is a graduate-level course. I will be following closely the book used. "Algorithms" by Dasgupta, Papadimitriou & Vazirani (2006).
* Please note that "we can convince ourselves", "as you should verify" and other such comments are code for "you should write the proof yourself in a piece of paper. I'm too lazy to do it myself!""
Epilogue
Hopefully that was interesting and my writing was simple enough. If you want to follow along, I encourage you to go through the reasoning with pen and paper :D
I am uploading these on a GitHub repo that you can check here: Algorithms-series.
I would appreciate any feedback (specially if I am wrong!!!). I am not an expert. I am learning, just like you!
If you wanna talk with me you should follow me on twitter: @jrlgs