Introduction to Algorithm Design

The Vacuum Cleaner Problem

We know the outline of our living room and we want to place power plugs in our room such that we can clean all of it with a vacuum clenar that has a power cord of a given length. How many power plugs do we need for this? How do we place them optimally? These are typical questions that SOI tasks can cover.

Today there are also vacuum cleaners that do not need a power cord and drive through your flat like robots. Instead of power plugs these robots need charging stations that they have to reach before their battery is empty. Also this leads to interesting questions: How do we spread out these charging stations optimally? What is a good cleaning route for a robot? The search for an optimal cleaning tour is similar to the following well known problem:

The Travelling Salesperson Problem (TSP)

A salesperson wants to travel through all the cities in a country as quickly as possible. So we search for the shortest tour that visits all cities. This is one of the most famous problems in theoretical computer science and is called Traveling Salesman [1] Problem, short TSP.

One way of solving this problem is just to try out all possible orders of cities. For each permutation, this is how we call the orders in mathematics, of the cities, we compute the costs and we store the minimum. So we already found a first algorithm for TSP. But is it a good or a bad one?

For $n$ cities, that are all connected with each other, we check $n \cdot (n-1) \cdot (n-2) \cdots 4 \cdot 3 \cdot 2 \cdot 1$ orders this way. This number is called $n$-factorial and is written as “$n!$”.

How large can our problem be so that this algorithm can still solve it? $100$ cities? For this we would need to try $100!$ permutations. But that are more than $2^{100}$ many. Is this a lot? Imagine a piece of paper. Fold it $100$ times, then the resulting pile is as thick as $2^{100}$ layers of paper. This is just about as much as the size of the known universe! [2]

Interestingly no significantly better algorithms for TSP are known today. In 1970, one could solve the problem for 120 cities with a slightly better algorithm. With the same algorithm one can solve 140 cities today, just by using faster computers. So only waiting until the computers get faster will not bring us far.

Meanwhile, there are also better algorithms for certain types of graphs, so that we can also find tours for hundreds of thousands of cities. So an algorithmic breakthrough can really lead to an improved efficiency. How does one invent a faster algorithm?

Example: Find the Star

Imagine you are sitting in an SOI workshop and are waiting until Niklaus Wirth enters the room. Who is Niklaus Wirth? Niklaus Wirth is the only Swiss winner of the Turing award (the nobel prize of computer science) and the inventor of the programming language Pascal.

Is Niklaus Wirth already in the room? Who even recognises him? You should all know him. [3] So we want to find Niklaus Wirth or another star among us. What is a star? How de we find one?

Definition: Star

• everyone knows him/her
• he/she knows nobody

As the basic operation, we consider a question to Person A of the form “Do you know person B?”. The answer is either Yes or No. Other questions are not allowed. How do we ask such questsions in a room of $n$ persons most effectively?

• Can it be that there is no star? Yes, for instance if everyone knows everyone.
• Can it be that there is exactly one star? Yes, for instance if Niklaus Wirth is here, because he probably does not know us.
• Can it be that there are several stars? No! See footnote [^ZweiStars] to see why not. [4]

We want to minimize the number of questions.

A naive approach: Asking everyone about everybody else takes $n \cdot (n-1)$ questions. We fill the complete table with the exception of the diagonal (everyone knows himself):

How do we know find the star in this table? We are looking for a person whose column only contains Yes (everyone knows her/him) and whose row only contains No (she/he does not know anyone). So in the example above, Bettina is the star.

So if we ask all $n(n-1)=n^2-n$ possible questions then we can decide if there is a star and if so find her/him. When designing algorithms, we always want to be as efficient as possible, so minimize the number of questions that we ask. So is it possible to find a star or say with certainty that there is none without asking all possible questions? How many questions do we need at least? Let $Q(n)$ be the number of questions that we ask for $n$ persons. So far, we have $Q(n)=n^2-n$. For $n=1000$, we ask $999'000$ questions. We now show how we can reduce this to just $2996$ questions.

We use induction for this: Induction means nothing else than starting with few people at first and then considering the others one by one. The easiest cases are $n=1$ with $Q(1)=0$ (a single person is always a star) and $n=2$. With only two people in the room, we can always solve the task with two questions: We write $Q(2) = 2$. For more than two: We send someone out of the room to wait in the hallway, determine the potential star among the remaining people and then fetch back the person in the hallway. For this extra person we have to check whether she/he is a star or confirm that the star from before is still a star. This takes up to $2(n-1)$ questions. This, we can write as:

Unfortunately, we did not save anything and still end up asking almost $n^2$ questions. But we have applied a new concept: we use the same method on a subset of people over and over again. This is called recursion (from the latin “going back”).

Why do we not save any questions? As it could be that the person that we send to the hallway is the star, we need many questions when that person reenters. Can we guarantee that we do not send out the star? Here comes the trick: If we ask A for B: If A knows B, then A is not a star. If A does not know B, then B is no star. In both cases, we find one person that is not a star and can send her/him to the hallway. (Whether or not the remainig person is a star is not clear yet.) So after just one question, we can always send a non-star to the hallway. We can repeat this “send out the non-star” procedure until only one person remains. This last person we have to question more thoroughly as she could be a star but does not have to be one. To this end, we fetch one person after the other from the hallway and ask her if she knows the star candidate and vice versa. For each person reentering, we can verify the potential star with just two questions. That’s cool right?

To compute the precise number of questions $Q(n)$ for $n$ persons, we need a bit of calculation. If you have not seen this in your math class yet, no problem. You can just remember that $3n$ questions are enough: for each person other than the star, we spend three questions, one when sending her out and two when bringing her back in. Thus for $1000$ people, $3000$ questions suffice. If you are super interested, you can find the mathematical proof in the appendix.

We summarize: At first we needed $n\cdot(n-1)$ questions. But after we looked at it closely, we figured out a much much faster method. This new method is so fast that it only asks a small fraction of all possible questions.

Challenge task: Can you do even better?

Intuitive O-Notation

What does this mean concretely? For a program that performs $5n^3 + 2n^2 + 8n + 50$ steps for an input of size $n$, we look at this polynomial and but only care about the summand with the highest power, so the $5n^3$, as everything else is really really small in comparison for large $n$. In addition, we ignore constant factors so we simplify $5n^3$ to $n^3$. We can write this in shorthand using the $\mathcal{O}$-Notation:

We write

$3n^3 + 2n^2 + 8n + 50 \in \mathcal{O}(n^3)$

and read this as

The program with $3n^3 + 2n^2 + 8n + 50$ steps runs asymptotically at most as slow as a program with $n^3$ steps.

For polynomials, we only care about the highest power. Frequent other functions that you will enounter: Logarithms are faster (= result in faster programs = grow slower) then square roots, square roots are faster than polynomials and polynomials are faster than exponential functions.

Formal O-Notation

This “Oh-Notation” can also be made mathematically formal. If you don’t care about this, just jump over this section.

For this we define a set of functions, that also does not grow faster than a growth function $g: \mathbb{N} \rightarrow \mathbb{N}$. We write this with a big, calligraphic ‘O’, as

$\mathcal{O}(g) = \{f: \mathbb{N} \rightarrow \mathbb{N}, \exists c_1, c_2: \forall n: f(n) \leq c_1 + c_2 \cdot g(n) \}$.

We say

All functions $f$ in $\mathcal{O}(g)$ do not grow asymptotically faster than $g$.

We can use this to simplify terms like $3n-4 \in \mathcal{O}(n)$ by setting e.g. $c_1 = 0$ and $c_2 = 3$. Usually, we are happy to just say that

The search for a start takes $\mathcal{O}(n)$ questions.

or

We find the star in linear time.

The precise number of questions (the $Q(n) = 3n-4$ that we showed above) often does not even interest us.

The two constants in the definition allow us to scale and shift one function against the other one.

As one could not easily typeset the $\in$ symbol in the beginning, one often wrote $3n-4 = \mathcal{O}(n)$, but correct is the notation with $\in$, as $3n-4$ is one of many functions that are contained in the set $\mathcal{O}(n)$.

Applications of the O-Notation

Now we can do the same for “growing at least as fast” as class $\Omega(g)$. Or for “strictly less fast” with small-O, so $o(g)$.

If the function $f$ is both in $\mathcal{O}(g)$ and $\Omega(g)$, we say that $f$ and $g$ grow asymptotically equally fast and write $f \in \Theta(g)$. For example: $3n-4 \in \Theta(n)$.

One has to get used to this asymptotic notation for a bit. In algorithm design it is everywhere, so we will see it in every SOI topic again. But don’t get frightened by it. Most things that you will see, are those:

• $\mathcal{O}(n)$: linear running time (e.g. for the fast star finding algorithm)
• $\mathcal{O}(n^2)$: quadratic running time (e.g. for the star finding algorithm that asks all possible questions)
• $\mathcal{O}(\log n)$: logarithmic running time (e.g. for binary search)
• $\mathcal{O}(n \log n)$: slightly super-linear running time (e.g. for sorting algorithms)

First naive solution

Here is a pseudocode implementation of an algorithm that simply tries out everything. Let d[k] deonte the $k$-th number in the input, so the stock price change on day $k$.

for i = 1 to n do
    for j = i to n do
        S := 0
        for k = i to j do
            S := S + d[k]
        store the maximum S seen so far

We look at every possible interval $[i,j]$ and compute the corresponding sum $S$. How long does this algorithm run?

Upper bound on the running time: Let us count the number of additions generously: each loop is executed at most $n$ times. As the loops are nested, we take the product, so $n\cdot n\cdot n = n^3$ in $\mathcal{O}(n^3)$.

But is this algorithm really that slow or did we just bound way too roughly? Let us also bound the running time conservatively, so counting rather too few additions. For this, let us assume that the start of the interval $i$ is only in the first third of the array and that the end of the interval $j$ is only in the last third of the array. For each such pair $i,j$, it holds that $k$ has to go over at least $\frac{n}{3}$ values. In total, even under these assumptions, we still perform at least $\frac{n^3}{27}$ steps which is in $\Omega(n^3)$.

As we got the same cubic upper and lower bound, we can thus say that the running time of our algorithm is in $\Theta(n^3)$. This is not especially quick and only suffices to work through a couple hundred days of the stock exchange.

So we got a program that is correct (in the sense that it computes the optimal solution), but we would like to get a faster one. We have to ask ourselves the question: What do we do that is too much? Do we computee something that we would not need to or do we compute the same thing over and over again? If we watch our algorithm “at work” we can see that it repeats itself. We sum up the numbers from $i$ to $j$ and in the next round from $i$ to $j+1$. So in doing that we sum up almost the same set of numbers again, just one more number at the end. Couldn’t we compute the sum of numbers from $i$ to $j$ faster somehow?

Solution with Prefix Sums

It suffices to compute all the prefix sums: A prefix is an initial part of a sequence. The prefix of length $i$ of our input are simply the first $i$ numbers.

For each position $i$, we compute the sum $S_i$ as the sum of numbers up to position $i$. All these values $S_i$, we can compute in linear time, so in $\mathcal{O}(n)$, increasingly in $i$: To compute $S_i$, we just have to add $d[i]$ to $S_{i-1}$. After that, the sum of numbers from $i$ to $j$ is simply $S_{j} - S_{i-1}$.

We can now get rid off the innermost loop:

// Compute the prefix sums in O(n)
S[0] := 0
for i := 1 to n do
    S[i] := S[i-1]+d[i]
// Take the sum of each interval in O(n^2)
for i := 1 to n do
    for j := i to n do
        S := S[j]-S[i-1]
        merke maximales S

How much faster is this? The precomputation of the prefix sums is in $n$ steps. After that, we can compute the sum of each of the $\mathcal{O}(n^2)$ intervals in constant time. Hence we get $\mathcal{O}(n^2 + n) = \mathcal{O}(n^2)$ steps overall.

Divide-and-Conquer

Are we happy now? $\mathcal{O}(n^2)$ can still be too slow for many real inputs. But contrary to before, this solution does not have an obvious speed bottleneck that we could attack.

To get faster, we want to look at another trick of algorithm design: divide and conquer. It is a powerful technique, that already the ancient Romans knew (latin: divide et impera) – although not in an algorithmic context but rather related to strong foreign policy.

As with the star, we try an inductive approach. But here we will not just take out one element (like with the star). Instead, we will split in the middle:

We split our sequence into two parts. Where can the solution, i.e. the interval with the biggest sum, be? We distinguish three cases: Either completely in the left half, completely in the right half or it contains part of the left and the right half. Exactly these three cases we want to consider and to compute the maximum interval for each case. Then we just have to pick the best of those three intervals.

Such a strategy, that splits the problem into smaller portions, solves each of them separately and then recombines them, is called “divide and conquer”. Did this split help us?

The first two cases are easy to cover: We compute the solution recursively (with the same approach) on both halves separately. But how can we compute the solution for the third case?

We search in the left half for the best piece that ends at the right border, and we combine it with the best piece from the right half that ends at the left border. Hence we have to consider the prefix sums of the right half and the suffix sums of the left half (A suffix is just piece from the the tail, so a prefix “from the other side). We already saw, that we can compute them in linear time. We the best prefix from the right to the best suffix from the left. So we can cover the third case in linear time.

Divide-and-Conquer algorithm:

• If there is at most one number:
  • If exactly one positive number: take this number
  • sonst: 0
• If there are several numbers
  • divide in the middle
  • determine the optimum solution separately in both parts
  • determine the best border pieces on the left and right
  • take the best of the three potential solutions

Analysis: Now we want to analyze the running time of our algorithm to see if we improved anything at all. This is a bit of a lengthy calculation - if you want, you are happy to skip it and directly jump to the linear solution. [5]

We write $T(n)$ for the time with $n$ elements. For the case where we compute (potentially multiple) partial solutions, we can write the running time as

Let $a'$ be a constant that bounds the effort to determine the solution across the middle, $a = a'+1$ and for the base case with $n=1$ let $T(1)=b$ for some constant $b$.

How does one solve such a recursion? We do what we did before. We insert a couple of times and see if we get a feeling for the solution.

This stops if $n=2^i$ or equivalently if $i = \log_2 n$, because then $T(1)$ and the recursion stops. So we suspect something like $T(n) = n\cdot b + a\cdot n\cdot \log n$, which would mean $T(n) \in \mathcal{O}(n \log n)$.

But is this really true? To formally prove it, we do not want to use $\mathcal{O}$-notation because hiding constants in a recurrence can be dangerous.

Proof by induction: To prove: There are $c_1$ and $c_2$, such that $T(n) \leq c_1 n \log n + c_2$

Induction base: To get $T(1) \leq c_2$, pick $c_2 \geq b$.

Induction hypothesis (IH): For $T\left(\frac{n}{2}\right)$ we already know that $T\left(\frac{n}{2}\right) \leq c_1 \frac{n}{2} \log \left(\frac{n}{2}\right) + c_2$.

Inductions step:

Can we make the last inequality hold? We have some room left to play, as we did not fix $c_1$ yet. Which condition does $c_1$ need to fulfill?

Pick $c_1 = a+c_2$ for example. What this shows is that our Divide-and-Conquer algorithm runs in time $\mathcal{O}(n\log n)$.

Linear Solution

Can we do even better? Let us try from the beginning and try again with an induction from left to right.

As a condition that should always stay true, we want to assume that after step $i$, we know the optimum solution for the first $i$ elements. If we now add element $(i+1)$ we want to quickly figure out if this new element belongs to the best interval or not. For this, we do not only compute the maximum up to $i$ but also how much we can get if we end at the right border of the current prefix, so at element $i$. Using this “border maximum”, we can now quickly compare whether we can get a new maximum with the new element or not.

For this we need that if we got up to position $i$, we computed already these things:

• the maximum in the range $1, \dots, i$,
• the maximum, that ends at position $i$.

bordermaxmax := 0
max := 0
for i = 1 to n do
    bordermax := bordermax + d[i]
    if bordermax < 0 then bordermax := 0
    if max < bordermax then max := bordermax

This approach is super simple to implement and has even just linear running time! So $\mathcal{O}(n)$, perfect!

Lower bound

Now we get ambitious and want to do even better. Can we do $\mathcal{O}(\sqrt n)$ or even $\mathcal{O}(\log(n))$? Or is no further improvement possible?

The following consideration shows that we can not be better than linear: Assume we have an algorithm that does not look at all the elements. Then this algorithm can not be correct:

• If the algorithm computes a range that contains the not-looked-at element, then let it be $-\infty$. We would better not take anything.
• If the solution does not contain the not-looked-at element, then let it be $\infty$, so that it really should be in the solution.

Hence every correct algorithm has to look at every element at least once. The running time is thus in $\Omega(n)$. This is not a property of a specific algorithm, but for all algorithms that solve the maximum subarray problem. We call this the runtime complexity of the problem

However, the size of the input is not always a lower bound for the runtime. Remember the star problem. The input was quadratic (all pairs), but we only had to ask linearly many questions.

Here some extra questions (with their answers):

• How do we find the interval (and not just its sum)? Answer: During the algorithm, we keep track of the bounds for max and bordermax and update them upon each change.
• What is the memory usage? Answer: We distinguish two types of memory: Memory used by the program (including the input) and how much memory we use additionally during the computation. This way, the first and last algorithm only require constant additional memory for the values S, bordermax and max. But as soon as we for instance compute all the prefix sums, like in the second algorithm, we need linear, so $\mathcal{O}(n)$, additional memory. Bonus question: How much additional memory does the divide-and-conquer algorithm need? [6]

So this is it. You reached the end of our crash course in algorithm design and analysis. If you have any questions, please let me know (daniel@soi.ch). Otherwise have fun with the other sections of our tutorials.

Induction for the Star task

We can write the function $Q(n)$ as follows:

The two cases distinguish whether we still send someone out or not. Now we telescope, meaning that we plug in the formula a couple of times and see what we get:

To formally prove that $Q(n) = 3n - 4$, we prove it by induction:

• Hypothesis: $Q(n-1)$ = $3(n-1)-4$
• Base of the induction: $Q(2)$ = $2$ ✓
• Step of the indution: $Q(n) = 3 + Q(n-1) = 3 + 3(n-1) -4 = 3n-4$ ✓