Integer Functions
These are just functions that convert between Real numbers (i.e. things with decimal points) to integral values. They actually have some important properties that we'll learn about, but this is mired in semantics about the number line, so be prepared for some painfully specific definitions.
Floors and Ceilings
The most basic integer functions are the floor and ceiling. These are defined as such
$\lfloor x \rfloor = \text{ the largest integer less than or equal to x}
\\ \lceil x\rceil= \text{ the smallest integer greater than or equal to x}$
So we're basically throwing away the decimal portion of our real number and are choosing an integer above or below it. In a sense, we're paying attention to the integer boundaries to our real number, so you should think of the floor/ceiling functions as inequalities, and view them in the context of the number line.
Here are some fundamental identities that you should drill into your brain. fyi, $ \Leftrightarrow $ means "if and only if".
The definitions we gave at first for ceiling and floor used filthy, imprecise words to introduce the idea, but purge such heresy from your mind and instead internalize the following definitions, written in terms of a real $x$ and integer $n$.
$$
\lfloor x \rfloor = n \ \Leftrightarrow \ n \leq x < {n + 1} \quad \text{(a)}
\\
\lfloor x \rfloor = n \ \Leftrightarrow \ {x-1} < n \leq x \quad \text{(b)}
\\ - \\
\lceil x\rceil = n \ \Leftrightarrow \ {n-1} < x \leq n \quad \text{(c)}
\\
\lceil x\rceil = n \ \Leftrightarrow \ x \leq n < {x + 1} \quad \text{(d)}
$$
On negative values, we hold the same properties, which means that, perhaps less intuitively, the floor
$\lfloor -x\rfloor = - \lceil x \rceil$
So, when you're doing a problem involving floor and ceiling, your goal should be to actually get rid of the function via some identity or substitution, because it's almost always easier to work with an inequality.
More identities for an integer $n$ and a real $x$
$$
\lfloor x \rfloor < n \ \Leftrightarrow \ x < n \quad \text{(e)}
\\
\lfloor x \rfloor \geq n \ \Leftrightarrow \ x \geq n \quad \text{(f)}
\\ - \\
\lceil x\rceil > n \ \Leftrightarrow \ x > n \quad \text{(g)}
\\
\lceil x\rceil \leq n \ \Leftrightarrow \ x \leq n \quad \text{(h)}
$$
It should be fairly easy to convince yourself that.
$\lfloor \lceil x\rceil \rfloor =\lceil x\rceil$
as well as
$\lceil x + n\rceil =\lceil x\rceil + n$
Ok now let's do a couple of problems to drill these into our brains.
Problem: Using floor and/or ceiling, get the decimal portion of x
$x - \lfloor x \rfloor = \{x\}$
The squiggly brace notation actually denotes the decimal component of a number.
If we know x isn't an integer, then we can also use
$1 + x - \lceil x \rceil = \{x\}$
but it will be one otherwise
--------
Now for the other problem, prove that
$$ \lfloor \sqrt{\lfloor x \rfloor} \rfloor = \lfloor \sqrt{x} \rfloor $$
Some people may look at this and go "oh, sure", but "sure" isn't a proof.
Like I stated earlier, let's try to get rid of the integer valued functions by using their identities.
We can often tackle these problems by introducing some relevant integer.
$\lfloor \sqrt{\lfloor x \rfloor} \rfloor = n, n \in Z$
recall $Z$ is the set of integers. We know, by definition that
$n \leq \sqrt{\lfloor x \rfloor} < n+1$
Ok, cool. Now let's get rid of the square root with property (a)
$ n^2 \leq \lfloor x \rfloor < (n+1)^2$
properties (f) and (g) let us recognize that the current inequality holds without the floor function, so we can rewrite it as
$ n^2 \leq x < (n+1)^2$
and maintain correctness.
Finally, we can re-apply square roots and use the exact same properties to rewrite this as
$ n \leq \lfloor \sqrt{x} \rfloor < {n+1}$
Thus we have proven our original statement.
This result actually generalizes such that with any continuous, monotonically increasing function $f(x)$,
$\lfloor f(x) \rfloor = \lfloor f( \lfloor x \rfloor) \rfloor$ and $\lceil f(x) \rceil = \lceil f( \lceil x \rceil) \rceil$
--------
But wait, how about a bonus problem involving both these concepts? Wow, you're as pumped up as I am. Alright, so here's the laydown :
we want to evaluate $\lfloor \lfloor m \alpha \rfloor n / \alpha \rfloor$
when m and n are positive integers and $\alpha$ is an irrational number greater than $n$
So, let's mess around with it. The easiest thing to do, IMO, is to represent messy values with simpler ones. Here let's rewrite this with $q = \lfloor m \alpha \rfloor$
$\lfloor q n / \alpha \rfloor$
Then via definition, we know that
$m \alpha - 1 \leq q < m \alpha$
which, if we plug in our equation, means that
$(m \alpha - 1)n / \alpha \leq qn / \alpha < m \alpha n / \alpha$
$\Rightarrow nm - n / \alpha \leq qn / \alpha < mn$
And the only integer value in this range is $nm-1$, which is what our floor function selects.
Another way to view this problem, is to separate the fractional component of our rational number
$\lfloor \lfloor m \alpha \rfloor n / \alpha \rfloor = \lfloor \frac{(m \alpha - \{m \alpha \})n }{\alpha} \rfloor = \lfloor \frac{n m \alpha}{\alpha} - \frac{\{m\alpha\}n}{\alpha} \rfloor$
We can then nicely dissect that final statement into chunks. $\frac{n m \alpha}{\alpha} = nm$, then the subtracting term can me decomposed into ${m \alpha}$, which is the fractional portion and therefore between $(0,1)$, and the term $\frac{n}{\alpha}$, which we know from the problem statement that $\alpha > n$ and therefore $0 < \frac{n}{\alpha} < 1$. Let's then say $Q = \frac{\{m\alpha\}n}{\alpha} \rfloor$. Because of our previous inequalities, $0<Q<1$, and therefore
$\lfloor \frac{n m \alpha}{\alpha} - \frac{\{m\alpha\}n}{\alpha} \rfloor = \lfloor n m - Q \rfloor = nm - 1$
Ok, I held off providing a graph until you had to use the definitions, but here's a quick visualization of what the ceiling and integer functions look like.
Each "#" on the x axis is a multiple of 1/2, and each y is a unit. The darker shade represents the value of the ceiling function on an x value, the lighter share is the floor, and the X is on values where both ceiling and floor evaluate as true.
In general, we want to know, given some alpha and beta on a number line, the number of integers between them.
If we think about this from the perspective of a physical number line, we can usually restrict our computations by wrapping them to the nearest integers. In other words, the decimal place itself is superfluous. If we were given integers $a$, $b$ and asked to compute the number just between them, we would count their difference minus 1, since in reality we have $b - a + 1$ markers. This very clearly creates $b - a$ regions between them. Whether we add or subtract one depends on whether we're including the endpoints.
Now, if we have to count this for real numbers, but exclude the endpoints, we have to take into account if our numbers are actually integers. Luckily we can do this with floor and ceiling as well.
Since we only want to count the integers between our markers, we can go to the integers we know won't be counted, and then exclude them from our calculation. The mixed-case of only excluding one boundary shares the same principal.
So, we can get the bounds of numbers using our number-line principles.
$$[\alpha, \beta], \alpha \leq \beta \text{ contains } \lfloor \beta \rfloor - \lceil \alpha \rceil + 1 \text{ integers}$$
$$[\alpha, \beta), \alpha \leq \beta \text{ contains } \lceil \beta \rceil - \lceil \alpha \rceil + 1 \text{ integers}$$
$$(\alpha, \beta], \alpha \leq \beta \text{ contains } \lfloor \beta \rfloor - \lfloor \alpha \rfloor + 1 \text{ integers}$$
$$[\alpha, \beta], \alpha \leq \beta \text{ contains } \lceil\beta \rceil - \lceil \alpha \rceil + 1 \text{ integers}$$
Ok now let's do a bunch of problems.
Show that the expression
$$ \lceil \frac{2x + 1}{2} \rceil - \lceil \frac{2x + 1}{4} \rceil + \lfloor \frac{2x + 1}{4}\rfloor$$
is always either $\lfloor x \rfloor$ or $\lceil x \rceil$
So, there's a fairly easy way to do this, but let's examine the problem thoroughly first. If we separate the fractional components, and distribute a bit then
$ \lceil \frac{2x + 1}{2} \rceil - \lceil \frac{2x + 1}{4} \rceil + \lfloor \frac{2x + 1}{4}\rfloor = \lceil x + 1/2 \rceil - \lceil x/2 + 1/4 \rceil + \lfloor x/2 + 1/4\rfloor =
\\ \lfloor x \rfloor + \lceil \{x\} + 1/2 \rceil - \lfloor x/2 \rfloor - \lceil \{x/2\} + 1/4 \rceil + \lfloor x/2 \rfloor + \lfloor \{ x/2 \} + 1/4 \rfloor \\ = \lfloor x \rfloor + \lceil \{x\} + 1/2 \rceil - \lceil \{x/2\} + 1/4 \rceil + \lfloor \{ x/2 \} + 1/4 \rfloor$
let's replace this with a shorthand
$\lfloor x \rfloor + a - b + c$
--------
Ok, next problem.
Prove that
$$\lceil \frac{n}{m} \rceil = \lfloor \frac{n + m - 1}{m} \rfloor$$
for all integers n and all positive integers m
Ok, so first trick here is to recognize that it is sufficient to consider this for $0 < n < m$, since if $n > m$, we can subtract integer $k = \lfloor n/m \rfloor$ from both sides and get a new $n, m$ to consider(with a small variation for negative cases).
Anyway, considering only $n/m$, we can consider the boundary between integers consisting of fractions of m.
and we see that because we have $m$ lengths, we have $m-1$ points, which means that for any nonzero value of n, we are crossing into the next integer boundary. Our equation then has two cases $n=0$ and $0 < n < m$, and it equality holds for both.
--------
HIGH SPEED LOW DRAG FOLLOWUP PROBLEM
Find a necessary and sufficient condition on the real number $b>1$ such that
$$\lfloor log_b x \rfloor = \lfloor log_b {\lfloor x \rfloor} \rfloor$$
for all real $x \geq 1$
alright, so let's just mess with floor functions like we do. First lets introduce a nice term
$\lfloor log_b x \rfloor = n$
let's use the definition of the floor with our favorite variable n
$n \leq log_b x < n+1$
and now we can isolate x!
$n^{bn} \leq x < (n+1)^b$
and we can apply a floor function here (and the rest of the algebra to get the statement we want) if and only if the conditions in identities (e) and (f) from the previous section are satisfied. That is
$n^{bn} \leq \lfloor x \rfloor < (n+1)^b \ \Leftrightarrow \ (n+1)^b > \lfloor x \rfloor x \geq n^b$
therefore, the necessary and sufficient conditions, in terms of our inputs is that
$\lfloor log_b {\lfloor x \rfloor} \rfloor \ \ \Leftrightarrow \ \lfloor log_b x \rfloor ^b \leq \lfloor x \rfloor < (\lfloor log_b x \rfloor +1)^b$
--------
Ok, the last one for this section.
Find the sum of all multiples of x in the closed interval $[\alpha..\beta]$, when $x>0$
So, this is pretty much the same as our integer boundary problems, except we're using multiples of $x$ as our boundary. We can view the segment $\beta - \alpha$ as intersecting some amount of these boundaries between $\lfloor (\alpha - \beta) / x \rfloor$ and $\lfloor (\alpha - \beta) / x - 1 \rfloor$ depending on position. To find the exact amount, we need to see if we intersect exactly, which we can do by finding how far away we are from our closest "first" x tick.
That is $k = \lfloor \alpha / x \rfloor * x$ is the tick at or before $\alpha$. We can then determine how many points we actually intersect with by counting from the first actual intersection of the ruler and a point by subtracting the portion to the left.
$\frac {\beta - \alpha - (\alpha - k)}{x} = M$ gives us the number of x's we intersect with. Now, to sum them up, we use an arithmetic sequence.
and we easily compute the sum with our previously calculated boundaries
$\sum_{k+1}^{M} ((k+1)*m)$
On this subtopic I also suggest doing problems 31 and 40.
\\ \lceil x\rceil= \text{ the smallest integer greater than or equal to x}$
So we're basically throwing away the decimal portion of our real number and are choosing an integer above or below it. In a sense, we're paying attention to the integer boundaries to our real number, so you should think of the floor/ceiling functions as inequalities, and view them in the context of the number line.
 |
| This guy is freaking trapped by integers |
Identities, Identities Everywhere
Here are some fundamental identities that you should drill into your brain. fyi, $ \Leftrightarrow $ means "if and only if".
The definitions we gave at first for ceiling and floor used filthy, imprecise words to introduce the idea, but purge such heresy from your mind and instead internalize the following definitions, written in terms of a real $x$ and integer $n$.
$$
\lfloor x \rfloor = n \ \Leftrightarrow \ n \leq x < {n + 1} \quad \text{(a)}
\\
\lfloor x \rfloor = n \ \Leftrightarrow \ {x-1} < n \leq x \quad \text{(b)}
\\ - \\
\lceil x\rceil = n \ \Leftrightarrow \ {n-1} < x \leq n \quad \text{(c)}
\\
\lceil x\rceil = n \ \Leftrightarrow \ x \leq n < {x + 1} \quad \text{(d)}
$$
On negative values, we hold the same properties, which means that, perhaps less intuitively, the floor
$\lfloor -x\rfloor = - \lceil x \rceil$
So, when you're doing a problem involving floor and ceiling, your goal should be to actually get rid of the function via some identity or substitution, because it's almost always easier to work with an inequality.
More identities for an integer $n$ and a real $x$
$$
\lfloor x \rfloor < n \ \Leftrightarrow \ x < n \quad \text{(e)}
\\
\lfloor x \rfloor \geq n \ \Leftrightarrow \ x \geq n \quad \text{(f)}
\\ - \\
\lceil x\rceil > n \ \Leftrightarrow \ x > n \quad \text{(g)}
\\
\lceil x\rceil \leq n \ \Leftrightarrow \ x \leq n \quad \text{(h)}
$$
It should be fairly easy to convince yourself that.
$\lfloor \lceil x\rceil \rfloor =\lceil x\rceil$
as well as
$\lceil x + n\rceil =\lceil x\rceil + n$
Ok now let's do a couple of problems to drill these into our brains.
Problem: Using floor and/or ceiling, get the decimal portion of x
$x - \lfloor x \rfloor = \{x\}$
The squiggly brace notation actually denotes the decimal component of a number.
If we know x isn't an integer, then we can also use
$1 + x - \lceil x \rceil = \{x\}$
but it will be one otherwise
--------
Now for the other problem, prove that
$$ \lfloor \sqrt{\lfloor x \rfloor} \rfloor = \lfloor \sqrt{x} \rfloor $$
Some people may look at this and go "oh, sure", but "sure" isn't a proof.
Like I stated earlier, let's try to get rid of the integer valued functions by using their identities.
We can often tackle these problems by introducing some relevant integer.
$\lfloor \sqrt{\lfloor x \rfloor} \rfloor = n, n \in Z$
recall $Z$ is the set of integers. We know, by definition that
$n \leq \sqrt{\lfloor x \rfloor} < n+1$
Ok, cool. Now let's get rid of the square root with property (a)
$ n^2 \leq \lfloor x \rfloor < (n+1)^2$
properties (f) and (g) let us recognize that the current inequality holds without the floor function, so we can rewrite it as
$ n^2 \leq x < (n+1)^2$
and maintain correctness.
Finally, we can re-apply square roots and use the exact same properties to rewrite this as
$ n \leq \lfloor \sqrt{x} \rfloor < {n+1}$
Thus we have proven our original statement.
This result actually generalizes such that with any continuous, monotonically increasing function $f(x)$,
$\lfloor f(x) \rfloor = \lfloor f( \lfloor x \rfloor) \rfloor$ and $\lceil f(x) \rceil = \lceil f( \lceil x \rceil) \rceil$
--------
But wait, how about a bonus problem involving both these concepts? Wow, you're as pumped up as I am. Alright, so here's the laydown :
we want to evaluate $\lfloor \lfloor m \alpha \rfloor n / \alpha \rfloor$
when m and n are positive integers and $\alpha$ is an irrational number greater than $n$
So, let's mess around with it. The easiest thing to do, IMO, is to represent messy values with simpler ones. Here let's rewrite this with $q = \lfloor m \alpha \rfloor$
$\lfloor q n / \alpha \rfloor$
Then via definition, we know that
$m \alpha - 1 \leq q < m \alpha$
which, if we plug in our equation, means that
$(m \alpha - 1)n / \alpha \leq qn / \alpha < m \alpha n / \alpha$
$\Rightarrow nm - n / \alpha \leq qn / \alpha < mn$
And the only integer value in this range is $nm-1$, which is what our floor function selects.
Another way to view this problem, is to separate the fractional component of our rational number
$\lfloor \lfloor m \alpha \rfloor n / \alpha \rfloor = \lfloor \frac{(m \alpha - \{m \alpha \})n }{\alpha} \rfloor = \lfloor \frac{n m \alpha}{\alpha} - \frac{\{m\alpha\}n}{\alpha} \rfloor$
We can then nicely dissect that final statement into chunks. $\frac{n m \alpha}{\alpha} = nm$, then the subtracting term can me decomposed into ${m \alpha}$, which is the fractional portion and therefore between $(0,1)$, and the term $\frac{n}{\alpha}$, which we know from the problem statement that $\alpha > n$ and therefore $0 < \frac{n}{\alpha} < 1$. Let's then say $Q = \frac{\{m\alpha\}n}{\alpha} \rfloor$. Because of our previous inequalities, $0<Q<1$, and therefore
$\lfloor \frac{n m \alpha}{\alpha} - \frac{\{m\alpha\}n}{\alpha} \rfloor = \lfloor n m - Q \rfloor = nm - 1$
Ok, I held off providing a graph until you had to use the definitions, but here's a quick visualization of what the ceiling and integer functions look like.
Each "#" on the x axis is a multiple of 1/2, and each y is a unit. The darker shade represents the value of the ceiling function on an x value, the lighter share is the floor, and the X is on values where both ceiling and floor evaluate as true.
Floor/Ceiling Applications
A very common problem in programming is to count the number of integers in an interval. It would be more appropriate to call it an operation.In general, we want to know, given some alpha and beta on a number line, the number of integers between them.
If we think about this from the perspective of a physical number line, we can usually restrict our computations by wrapping them to the nearest integers. In other words, the decimal place itself is superfluous. If we were given integers $a$, $b$ and asked to compute the number just between them, we would count their difference minus 1, since in reality we have $b - a + 1$ markers. This very clearly creates $b - a$ regions between them. Whether we add or subtract one depends on whether we're including the endpoints.
Now, if we have to count this for real numbers, but exclude the endpoints, we have to take into account if our numbers are actually integers. Luckily we can do this with floor and ceiling as well.
Since we only want to count the integers between our markers, we can go to the integers we know won't be counted, and then exclude them from our calculation. The mixed-case of only excluding one boundary shares the same principal.
So, we can get the bounds of numbers using our number-line principles.
$$[\alpha, \beta], \alpha \leq \beta \text{ contains } \lfloor \beta \rfloor - \lceil \alpha \rceil + 1 \text{ integers}$$
$$[\alpha, \beta), \alpha \leq \beta \text{ contains } \lceil \beta \rceil - \lceil \alpha \rceil + 1 \text{ integers}$$
$$(\alpha, \beta], \alpha \leq \beta \text{ contains } \lfloor \beta \rfloor - \lfloor \alpha \rfloor + 1 \text{ integers}$$
$$[\alpha, \beta], \alpha \leq \beta \text{ contains } \lceil\beta \rceil - \lceil \alpha \rceil + 1 \text{ integers}$$
Ok now let's do a bunch of problems.
Show that the expression
$$ \lceil \frac{2x + 1}{2} \rceil - \lceil \frac{2x + 1}{4} \rceil + \lfloor \frac{2x + 1}{4}\rfloor$$
is always either $\lfloor x \rfloor$ or $\lceil x \rceil$
So, there's a fairly easy way to do this, but let's examine the problem thoroughly first. If we separate the fractional components, and distribute a bit then
$ \lceil \frac{2x + 1}{2} \rceil - \lceil \frac{2x + 1}{4} \rceil + \lfloor \frac{2x + 1}{4}\rfloor = \lceil x + 1/2 \rceil - \lceil x/2 + 1/4 \rceil + \lfloor x/2 + 1/4\rfloor =
\\ \lfloor x \rfloor + \lceil \{x\} + 1/2 \rceil - \lfloor x/2 \rfloor - \lceil \{x/2\} + 1/4 \rceil + \lfloor x/2 \rfloor + \lfloor \{ x/2 \} + 1/4 \rfloor \\ = \lfloor x \rfloor + \lceil \{x\} + 1/2 \rceil - \lceil \{x/2\} + 1/4 \rceil + \lfloor \{ x/2 \} + 1/4 \rfloor$
let's replace this with a shorthand
$\lfloor x \rfloor + a - b + c$
where $a = \lceil \{x\} + 1/2 \rceil $, $b = \lceil \{x/2\} + 1/4 \rceil$, and $c =\lfloor \{ x/2 \} + 1/4 \rfloor $
Now we can deduce what their values will be for different x, which span over even and odd cases of integers.
Nice, so we now see it's a rounding function that on exact splits chooses between rounding up and down based on whether a number is even or odd. Since it rounds up on odd values, you could say that "choosing evens" is given preference.
Anyway, this was certainly illustrative, but the best way to do this is to make a substitution $o = \frac{x+1/2}{2}$ at the beginning of the problem, and work with the value o in the simpler $ \lceil 2\cdot o \rceil - \lceil o \rceil + \lfloor o \rfloor$. I'm sure the reader can continue from here.
--------
Ok, next problem.
Prove that
$$\lceil \frac{n}{m} \rceil = \lfloor \frac{n + m - 1}{m} \rfloor$$
for all integers n and all positive integers m
Ok, so first trick here is to recognize that it is sufficient to consider this for $0 < n < m$, since if $n > m$, we can subtract integer $k = \lfloor n/m \rfloor$ from both sides and get a new $n, m$ to consider(with a small variation for negative cases).
Anyway, considering only $n/m$, we can consider the boundary between integers consisting of fractions of m.
and we see that because we have $m$ lengths, we have $m-1$ points, which means that for any nonzero value of n, we are crossing into the next integer boundary. Our equation then has two cases $n=0$ and $0 < n < m$, and it equality holds for both.
--------
HIGH SPEED LOW DRAG FOLLOWUP PROBLEM
Find a necessary and sufficient condition on the real number $b>1$ such that
$$\lfloor log_b x \rfloor = \lfloor log_b {\lfloor x \rfloor} \rfloor$$
for all real $x \geq 1$
alright, so let's just mess with floor functions like we do. First lets introduce a nice term
$\lfloor log_b x \rfloor = n$
let's use the definition of the floor with our favorite variable n
$n \leq log_b x < n+1$
and now we can isolate x!
$n^{bn} \leq x < (n+1)^b$
and we can apply a floor function here (and the rest of the algebra to get the statement we want) if and only if the conditions in identities (e) and (f) from the previous section are satisfied. That is
$n^{bn} \leq \lfloor x \rfloor < (n+1)^b \ \Leftrightarrow \ (n+1)^b > \lfloor x \rfloor x \geq n^b$
therefore, the necessary and sufficient conditions, in terms of our inputs is that
$\lfloor log_b {\lfloor x \rfloor} \rfloor \ \ \Leftrightarrow \ \lfloor log_b x \rfloor ^b \leq \lfloor x \rfloor < (\lfloor log_b x \rfloor +1)^b$
--------
Ok, the last one for this section.
Find the sum of all multiples of x in the closed interval $[\alpha..\beta]$, when $x>0$
So, this is pretty much the same as our integer boundary problems, except we're using multiples of $x$ as our boundary. We can view the segment $\beta - \alpha$ as intersecting some amount of these boundaries between $\lfloor (\alpha - \beta) / x \rfloor$ and $\lfloor (\alpha - \beta) / x - 1 \rfloor$ depending on position. To find the exact amount, we need to see if we intersect exactly, which we can do by finding how far away we are from our closest "first" x tick.
That is $k = \lfloor \alpha / x \rfloor * x$ is the tick at or before $\alpha$. We can then determine how many points we actually intersect with by counting from the first actual intersection of the ruler and a point by subtracting the portion to the left.
$\frac {\beta - \alpha - (\alpha - k)}{x} = M$ gives us the number of x's we intersect with. Now, to sum them up, we use an arithmetic sequence.
and we easily compute the sum with our previously calculated boundaries
$\sum_{k+1}^{M} ((k+1)*m)$
On this subtopic I also suggest doing problems 31 and 40.
Floor/Ceiling Recurrences
Let's look at a recurrence involving the floor function.
$$ K_0 = 1 \\ K_{n+1} = 1 + min(2K_{\lfloor n/2 \rfloor}, 3K_{\lfloor n3 \rfloor}) $$
There are two ugly terms in this recurrence. The first is the min function, and the second one are the floor functions acting as indices. It makes it very annoying. Let's write out this recurrence for the first few terms.
$4, 7, 7, 7, 9, 9, 10, 13, ...$
Let's try proving that $ K_n \geq n + 1$ via induction. Let's assume that the inequality holds thorugh n, We know that
$ K_{n+1 } \geq 1 + min(2 (\lfloor n/2 \rfloor + 1),\ 3 (\lfloor n/3 \rfloor + 1) ) \\= 1 + min ( 2\lfloor n/2 \rfloor + 2,\ 3 \lfloor n/3 \rfloor + 3) $
Since$ k \lfloor n/k \rfloor = k \lfloor \frac{mk + r}{k} \rfloor = km = n - r$
where r is the remainder
$n-r$ is minimized when the remainder is maximized, which is when $r = k-1$, so we can plug this back in to our min function as a "worst-case" scenario for a lower bound, i.e.
$k_{n+1} \geq 1 + min(N-2 + 1 + 2, N-3+1+3 \\ \geq 1 + min(n +1, n+1) \\ \geq n + 2$
which satisfies our problem.
This is basically how we handle recurrences with floors: by providing bounds, and it's more precise!
Quicksort is usually written as $f(n) = 2f(n/2) + n - 1$ but technically, when we split the array, we're creating the recurrence $f(n) = f(\lceil n/2 \rceil) + f(\lfloor n/2 \rfloor)$ + n - 1 . This may make a difference in your analysis, but realistically speaking, just using normal division is good enough. As skiena put it "Dropping the floors ... asymptotically it doesn't really change the answer. In all my years as an algorithm analyst that's something that's been good enough for me". But it does matter in small or specific cases. The devil is in the detail!
'mod' : The Binary Operator
The "modulus" operator is very much the same as the mod operation in programming. You get the remainder of a division operation. This operation is so fundamental that getting the modulus is part of the x86 div command.
The best way to define the mod operation is as:
$$n = m \lfloor n/m \rfloor + n \bmod m$$
which is to say
$$x \bmod m = x - y \lfloor x/y \rfloor$$
Anyway, it does exactly what you expect it to do. Now, what are some interesting properties of mod?
Base case:
$x \bmod 0 = x$
Distributive
$c (x \bmod y) = (cx) \bmod (cy)$
Negative Cases:
$ x mod y = - ( {-x} mod {-y} ) $
We won't be going over mod further for now, but number theory is the next chapter..
Floor/Ceiling Sums
So, some sums become fairly trivial when you apply a floor function to them, e.g.
$\sum_{k=0}^n \lfloor \frac{1}{k} \rfloor = sum_{k=0}^n 0 = 0$
However, we often have to treat then with more thought. Let's take, for example,
$\sum_{0 \leq k < n} \lfloor \sqrt{k} \rfloor = \sum_{k, m \geq 0} m [k < n] [m = \lfloor \sqrt{k} \rfloor] \\ = \sum_{k, m \geq 0} m [k < n] [m \leq \sqrt{k} < m + 1] \\ = \sum_{k, m \geq 0} m [k < n] [m^2 \leq k < (m + 1)^2] \\ = \sum_{k, m \geq 0} m [m^2 \leq k < (m + 1)^2 \leq n] + \sum_{k, m \geq 0} m [m^2 \leq k < n < (m+1)^2$
with sums, the boundary conditions can screw you up, so make sure to manipulate them properly. Here we have to assume that n is a perfect square, which reduces the second sum to zero. We can then write the first explicitly in these terms.
$\sum_{k, m \geq 0} m [m^2 \leq k < (m + 1)^2 \leq a^2] = \sum_{k, m \geq 0} m [m^2 \leq k < (m + 1)^2 \leq a^2] = \sum_{m \geq 0} m ( (m+1)^2 - m^2)[m+1 \leq a] \\ = \sum_{m \geq 0} m (2m+1) [ m < a] \\ = \sum_{m \geq 0} (2m^{\underline{2}} + 3m^{\underline{1}}) [m < a] \\ = \sum_{m}^a (2m^{\underline{2}} + 3m^{\underline{1}}) [m < a] \delta m \\ = \frac{2}{3}a(a-1)(a-2) + \frac{3}{2} a (a-1)$
Another good illustration is a casino problem introduced in the book (earlier than this section, weirdly enough).
Here's the premise: a certain casino has a roulette wheel with one thousand slots, numbered 1 to 1000. If the number n you get on a spin has the property that $n \bmod \lfloor \sqrt[3]{n} \rfloor = 0$, then you get back your cash and 5 dollars, otherwise you squander a dollar on the playing fee. We want to calculate if this game is profitable.
What can you do? You can sum over all ball values to compute "average" winnings. That is,
((numer of winners) * profit - (number of losers) * cost)/(total balls)
which we can write as
$(5W - L) / 1000$
since winners and losers must equal the whole batch $W + L = 1000$, we can write this as:
$(5 W - (1000 - W)) / 1000 = (6W - 1000) / 1000$
Cool, so let's use a summation to count the number of winners
$W = \sum_{1 \leq N \leq 1000} (n \bmod \lfloor \sqrt[3] n\rfloor = 0)$
again, we use the definition of floor to expand this as
$= \sum_{k,n}(k \leq n < (k+1)^3) (n \bmod k = 0) \\
= 1 + \sum_{k,m}(k^3 \leq km < (k+1)^3)(1 \leq k < 10) \\
= 1 + \sum_{k,m}(m\in [k^2, (k+1)^3/k])(1 \leq k < 10) \\
= 1 + \sum_{k,m}(\lceil k^2 + 3k + 3 + \frac{1}{k} \rceil - \lceil k^2 \rceil) \\
= 1 + \sum_{k,m}(3k+4) = 172$
So, (6*172-1000) mean that out of every 1000 games we play, we can expect to win 32 dollars!
----
In conclusion, sums seem pretty straightforward, but are an integral(haha, I'm so tired) part of computer science, and we should be second nature to work with.
Bonus Exercises
I recommend the following exercises from the text, in addition to the ones we've done here: 5, 7, 8, 9, 14, 20, 26-29, 31, 33, 40
No comments :
Post a Comment