Week 1 – Introduction Algorithms, Induction, Star Search

Sources

Script Algorithmen und Datenstrukturen – Einleitung (HS 2026, Kap. 1–3) and Prof. Püschel’s lecture recordings (Part 1 and the start of Part 3). The script has no numbered definitions or lemmas yet, so these notes follow its section numbers (1.1, 1.2, 2, 3). Places where the lecture and script disagree, or the transcript is garbled, are marked with ⚠ Discrepancy.

---

1. Executive Overview & Core Objectives

This first week introduces the algorithmic way of thinking (algorithmische Denkweise) through two toy problems: the Pasture-Break problem (a short-sighted cow searching for a gap in a fence) and Star Search (finding a person known by everyone who knows no one). The method is the same in both. First write down a simple, correct algorithm, then count its cost in the worst case (schlechtester Fall), then ask “Geht es besser?” and improve it. Along the way the lecture introduces mathematical induction (vollständige Induktion) as a proof tool, and shows that the same idea, reducing size $n$ to size $n-1$, is also a design tool for algorithms (an inductive algorithm). Recurrences that arise from such algorithms are solved by telescoping (Teleskopieren), which gives a guess, and then by induction, which proves it.

Learning objectives. After this week you should be able to:

• State what an algorithm is (complete description, elementary operations, solves a problem for all instances).
• Explain why we analyse the worst case and not the best case.
• Analyse both Pasture-Break strategies (step size $+1$ gives $k(k+2)$, doubling gives $<9k$), including the choice of $i$ with $2^{i-1}<k\le 2^i$.
• Write a full induction proof (base case, induction hypothesis, induction step), including proofs whose base case is not $1$, and inequality proofs such as Bernoulli’s inequality.
• Set up a recurrence for a recursive algorithm, guess its closed form by telescoping, and prove it by induction.
• Give the naive ($n(n-1)$), recursive ($n(n-1)$ worst case) and improved ($3n-4$) star-search algorithms, with correctness arguments and question counts.
• Name the factors that make real runtimes machine-dependent, and explain why we need abstract models (RAM model, asymptotic analysis).

---

2. Core Concepts & Formal Definitions

2.1 Algorithms (Script §1.1)

Definition (Algorithm / Algorithmus) – lecture version

An algorithm (Algorithmus) is a complete description (vollständige Beschreibung) of a sequence of elementary operations (Abfolge von elementaren Operationen) that solves a problem (Problem).

Definition (Algorithm) – script version

Informally, an algorithm is a systematic decomposition (systematische Zerlegung) of an apparently difficult problem into simple steps. “Systematic” means the decomposition generalises: it is not tailored to one instance of the problem. So we require a description of the step sequence that is

• unambiguous (eindeutig),
• complete (vollständig), and
• generally valid (allgemeingültig), meaning it works for every instance.

Key components:

• Complete (vollständig): nothing is left out. The description is detailed enough that it is clear exactly what happens.
• Elementary operations (elementare Operationen): the allowed atomic steps. Which steps count as elementary depends on the problem and the model. Examples: one step of the cow; one question “does $P_i$ know $P_j$?”; for a computer, the basic machine instructions.
• Problem specification: problems are usually stated as “Given (gegeben) …, find (gesucht) …”.

Everyday examples from the lecture: cooking and baking recipes, IKEA assembly instructions (numbered, pictorial elementary steps), and written addition or multiplication from school. The script uses written multiplication as its main example: it reduces multi-digit multiplication to single-digit multiplications and additions, and the same description works for every pair of numbers.

Algorithms in computer science. We care about algorithms that operate on data and are executed by computers. Computers:

• can run arbitrary algorithms on data,
• very fast: about $10^{10}$ operations per second (lecture; already true for a smartphone), “billions of steps per second” (script),
• and provide many elementary operations in which we express algorithms.

The script’s motivation: being able to process huge amounts of data is what makes things like large language models possible. Faster hardware alone is a fallacy (Trugschluss). A good algorithm can process a data set in minutes on a laptop, while a bad one would not finish on the world’s fastest supercomputer before the sun burns out. With a better algorithm we can process the same data faster, or more data in the same time. Computer science is often defined as the science of algorithms.

Goals of the course (A&D):

1. Design and analysis of algorithms (Entwurf und Analyse von Algorithmen): learn the recurring ideas behind algorithm design, and learn to analyse cost.
2. Data structures (Datenstrukturen): discussed later.
3. The algorithmic way of thinking (algorithmische Denkweise): analogous to the mathematical way of thinking. It uses mathematical methods for analysis but is not the same thing as mathematics.
4. Knowing important algorithms (e.g. sorting). These are already implemented, but the point is to understand how they were designed, their advantages and disadvantages, and how to analyse them.

Typical questions in the algorithmic way of thinking (script):

• Which different algorithms exist for the same problem?
• How can we compare them? Can we assign a quality measure and quantify how much better one is?
• Can we determine the best possible algorithm with respect to this measure?

2.2 Worst-Case Analysis

Definition (Worst case / Best case)

For a fixed problem size (e.g. distance $k$, number of persons $n$), the worst case (schlechtester Fall) of an algorithm is the maximum cost over all admissible inputs or situations of that size. The best case (bester Fall) is the minimum.

Why worst case?

The worst case gives a guarantee: whatever the input, the cost never exceeds this bound. The best case is meaningless as a quality measure because it is rare. Average-case analysis exists but is (almost) never used in this course. Püschel: “Uns interessiert immer der Worst Case.”

2.3 Pasture-Break Problem (Script §1.2)

Problem (Pasture Break / "Ausbruch aus der Weide")

Given: an infinite, straight fence; a short-sighted (kurzsichtig) cow standing next to it; exactly one gap (Lücke) in the fence at distance $k\in \mathbb{N}$ steps, either to the left or to the right of the cow. The cow does not know the direction and, in general, does not know $k$.
Elementary operation: one step parallel to the fence. At each position the cow can only see whether the gap is exactly there.
Goal: find the gap with as few steps as possible in the worst case, for every $k$.

Assumptions (from student questions):

• The fence is infinite, so $k$ can be arbitrarily large, but $k$ is a fixed finite number.
• The cow stops as soon as it reaches position $k$ on the correct side.
• The algorithm must work for all $k$. Assumptions such as "$k<1000$" or “the gap is on the left” would allow better special-case algorithms, but they are not allowed.

2.4 Mathematical Induction (Script Kap. 2)

Definition (Principle of mathematical induction / vollständige Induktion)

Let $A(k)$ be a statement depending on $k\in \mathbb{N}$. To prove $A(k)$ for all $k\in \mathbb{N}=\{1,2,3,\dots \}$ it suffices to show:

1. Base case (Induktionsanfang, IA): $A(1)$ holds.
2. Induction step (Induktionsschritt, IS), $k\to k+1$: for all $k\in \mathbb{N}$: if $A(k)$ holds, then $A(k+1)$ holds.

Equivalently: show $A(k+1)$ with the help of $A(k)$. The assumption ”$A(k)$ holds” used inside the step is the induction hypothesis (Induktionshypothese, IH).

Generalisation: if the base case is at $n_0$ (show $A(n_0)$, and the step for all $n\ge n_0$), then $A(n)$ holds for all $n\ge n_0$.

Intuition: domino chain

IA gives $A(1)$. IS with $k=1$ gives $A(2)$; with $k=2$ it gives $A(3)$, and so on. An infinite family of statements is proved by a finite argument (two finite proofs). The IS must cover all $k\in \mathbb{N}$, otherwise the chain breaks.

Why proofs at all (script)? Testing an algorithm on many inputs says nothing about the other inputs, and small changes in the input can have drastic effects. We want statements for all inputs, and only proofs give those.

Definition (Recurrence / Rekurrenz)

A recurrence (Rekurrenz) is an equation that defines $F(n)$ through values of $F$ at smaller arguments, together with one or more base cases (Basisfälle). Example: $F(2)=2$, $F(n)=F(n-1)+2$ for $n>2$.
Recurrences arise naturally when an algorithm reduces a problem of size $n$ to size $n-1$: cost($n$) = cost($n-1$) + cost of the reduction. A recurrence determines $F$ uniquely but does not show directly how big $F(n)$ is. For that we want a closed form (geschlossene Formel) such as $F(n)=2(n-1)$.

Method (Telescoping / Teleskopieren, as used in this lecture)

Substitute the recurrence into itself repeatedly ($F(n)\to F(n-1)\to F(n-2)\to \dots$) until a pattern appears, then extrapolate down to the base case. The resulting "$\dots$" argument is not a proof. It produces a conjecture, which is then proved by induction.

⚠ Terminology note: in this lecture “Teleskopieren” means repeated substitution / unrolling. Other texts use “telescoping sum” for $\sum (a_{i+1}-a_i)=a_{n+1}-a_1$. The two are related (unrolling produces exactly such a sum), but don’t let the name confuse you.

Knowledge types (Püschel's mental model)

• Look-up knowledge: you know where to look it up (Google, an LLM).
• Middle-of-the-night knowledge: someone wakes you at 3 a.m. and you know it instantly. These two sums must be in this category:
  ${\sum }_{j=1}^{k}j=\frac{k(k+1)}{2},{\sum }_{j=0}^{k-1}{2}^j=2^k-1.$

2.5 Star Search (Script Kap. 3)

Definition (Star)

In a group of $n$ persons $P_1,\dots ,P_n$, a person $P_s$ is a star (Star) if

1. $P_s$ knows no other person: for all $t\ne s$, $P_s$ does not know $P_t$, and
2. every other person knows $P_s$: for all $t\ne s$, $P_t$ knows $P_s$.

(Knowing oneself is irrelevant.) Mental model: Tom Cruise (lecture) or Roger Federer (script) walks into the lecture hall.

Problem (Star search / Starsuche)

Given: persons $P_1,\dots ,P_n$. Find: the star if one exists, otherwise report “no star”.
Elementary operation: a yes/no question “Does $P_i$ know $P_j$?”, written $P_i\to P_j$.
Goal: as few questions as possible in the worst case.

Lemma (number of stars)

A group has either 0 or 1 stars. Both cases occur.

• 0 stars is possible (in fact the normal case for large groups, e.g. this lecture hall).
• 1 star is possible (bring Tom Cruise in).
• 2 or more stars is impossible.

Proof of "at most one star"

Suppose $P_s$ and $P_t$ with $s\ne t$ are both stars. Since $P_s$ is a star, every other person knows $P_s$, in particular $P_t$ knows $P_s$. But then $P_t$ knows someone, which contradicts $P_t$ being a star. $■$
(Lecture illustration: bring in Brad Pitt and Tom Cruise. They know each other from Interview with a Vampire (1994), so neither is a star any more.)

2.6 Comparing Algorithms (preview, finished next lecture)

Criteria for judging algorithms:

• Correctness (Korrektheit): strictly, this requires a formal proof. So far we have only argued informally.
• Runtime (Laufzeit): always the worst case, as a guarantee.

The difficulty is that real runtime depends on

• the input (its size, and whether it is “nice” or not),
• the computer (speeds differ and have grown enormously over the decades),
• the implementation: programming language (Python vs. C vs. Rust), compiler, and how cleverly it is written.

A statement like “runs in $278n^2+7n$ seconds on this machine” is useless: too detailed, and different for every machine and implementation. We need models that abstract from these details and are therefore universally valid:

1. Unit-time random-access model (RAM model): a processor plus memory, with simplified assumptions about what each operation (e.g. loading data) costs.
2. Asymptotic runtime analysis (asymptotische Laufzeitanalyse): only linear ($\sim n$), quadratic ($\sim n^2$), and so on. Constant factors ($3n$ vs. $17n$) change from machine to machine. The growth type does not. On any computer and in any language, a linear algorithm beats a quadratic one for large enough $n$.

---

3. Step-by-Step Derivations & Mathematical Proofs

3.1 Pasture Break, distance $k$ known

Algorithm: walk $k$ steps in one direction (say left). If the gap is not there, walk back ($k$) and then $k$ to the right.

Case	Steps
gap on the left	$k$
gap on the right	$k+k+k=3k$

Worst case $=3k$. Nothing can be improved here: without knowing the direction, the cow must risk the wrong side first.

3.2 Pasture Break, $k$ unknown: Algorithm 1 (increase by 1)

Idea: zig-zag. You must alternate sides, because betting on one side forever may never find the gap. Increase the distance each time: $1$ left and back, $2$ right and back, $3$ left and back, …

It terminates: at the latest in round $k+1$, the cow walks distance $\ge k$ on the correct side.

Worst-case scenario. The last round on the correct side just misses: it reaches distance $k-1$ on the gap side, turns back ($k-1$). Then it walks $k$ on the wrong side and back ($2k$). Then it walks $k$ on the correct side and finds the gap.

Whether $k-1$ lands on the gap side depends on the parity of $k$ (since sides alternate). If round $k-1$ goes to the wrong side, round $k$ already goes to the correct side and the two “useless” $k$‘s disappear. That is the better case.

Counting:

$$\text{steps}=2\cdot 1+2\cdot 2+\cdots +2(k-1)+2k+k=2\sum _{j=1}^{k}j+k=2\cdot \frac{k(k+1)}{2}+k=k(k+1)+k=k(k+2).$$

Why stop at $k$ and not $k+1$: the cow sees the gap at distance $k$ and stops.

For comparison, the good parity case: $2{\sum }_{j=1}^{k-1}j+k=k(k-1)+k=k^2$, which differs by exactly $2k$ from the worst case.

Verdict: dominant term $k^2$. For $k=1000$, about $10^6$ steps. Very expensive.

Why is it wasteful? In round $k-1$ the cow walks $k-1$ steps, but the first $k-3$ positions on that side were already inspected two rounds earlier. Each round adds only 1–2 new positions, while the cost per round keeps growing. Effort is out of proportion to the information gained.

3.3 Pasture Break: Algorithm 2 (doubling)

Idea: double the distance each round, so each round explores about as many new positions as were already known: $1$ left and back, $2$ right and back, $4$ left and back, $8$ right and back, …

Choice of $i$. Pick the unique $i\in {\mathbb{N}}_0$ with
$2^{i-1}<k\le 2^i,$
i.e. $2^i$ is the first power of two $\ge k$ ($i=\lceil {\log }_{2}k\rceil$). This $i$ is unique for every $k$, because the intervals $(2^{i-1},2^i]$ partition the positive integers.

Worst-case scenario. The cow just misses: the round of length $2^{i-1}$ goes to the correct side and falls short, since $2^{i-1}<k$. Back $2^{i-1}$. Then the round of length $2^i$, which would have succeeded, goes to the wrong side: $2^i$ there and $2^i$ back. Then the round of length $2^{i+1}$ goes to the correct side and stops after $k$ steps.

(Lecture Q&A: “Is the near-miss of length $2^{i-2}$?” It misses too, but $2^{i-1}$ is the maximal near-miss. That is the unlucky case, because if $2^{i-1}$ were on the wrong side, the next round of length $2^i\ge k$ would hit.)

Counting:

$$\text{steps}=2(2^0+2^1+\cdots +2^{i-1}+2^i)+k=2(2^{i+1}-1)+k,$$

using the sum of the first $i+1$ powers of two, $S_{i+1}=2^{i+1}-1$ (proved in §3.4).

⚠ Discrepancy (transcript): the spoken sum reads “2·1 + 2·1 + 2·2 + …”. This is a transcription or speech slip. The correct sum is $2(2^0+2^1+\cdots +2^i)+k$, as in the script.

Bounding in terms of $k$ (abschätzen). We want an upper bound that is a function of $k$ alone.

• From $k>2^{i-1}$: $4k>4\cdot 2^{i-1}=2^{i+1}$. This is the key trick: write $2^{i+1}$ as $4\cdot 2^{i-1}$ to connect it to $k$.
• Dropping the $-1$ only makes the expression larger (fine for an upper bound).

$$2(2^{i+1}-1)+k<2\cdot 2^{i+1}+k<2\cdot 4k+k=9k.$$

Worst case $<9k$, i.e. linear in $k$. For $k=1000$: at most about $9000$ steps instead of about $10^6$. For $k=100$ (script): Algorithm 1 needs more than $10000$ steps, Algorithm 2 fewer than $900$.

Theorem (optimality of 9k, stated without proof)

The bound $9k$ is best possible: for every algorithm and every $\epsilon >0$ there is a $k$ for which the algorithm needs at least $(9-\epsilon )k$ steps in the worst case.
In particular, tripling, using factor 1.5, and so on do not improve the worst case. Faster growth makes it worse (see Self-Assessment Q1).

⚠ Lecture vs. script: the lecture only says “it can be proven that other factors don’t improve the worst case; we won’t do it”. The script gives the precise $(9-\epsilon )k$ lower bound, also without proof.

On "Geht es besser?"

Showing that something can be done better is easy: exhibit a better algorithm. Proving that nothing can be better (a lower bound, untere Schranke) is in general very hard. For many problems it is unknown whether the best known algorithm is optimal.

3.4 Induction Example 1: sum of powers of two

Claim

Let $S_k=1+2+4+\cdots +2^{k-1}={\sum }_{j=0}^{k-1}{2}^j$. Then for all $k\in \mathbb{N}$:
$S_k=2^k-1.$

How to find the conjecture (script): $S_1=1$, $S_2=3$, $S_3=7$, $S_4=15$. Each is one less than the next power of two.

Proof by induction on $k$.

IA ($k=1$): $S_1=1$ (a single summand) and $2^1-1=1$. ✓

IS ($k\to k+1$): assume $S_k=2^k-1$ (IH). Then

$$\begin{array}{rlrl}{S}_{k+1}& =\underset{=S_k}{\underbrace{1+2+\cdots +2^{k-1}}}+2^k& & \text{(definition: split off the last term)}\\ & \stackrel{\text{IH}}{=}{2}^k-1+2^k& & \text{(induction hypothesis)}\\ & =2\cdot 2^k-1=2^{k+1}-1.& & \text{(arithmetic)}\end{array}$$

This is exactly the claim for $k+1$. $■$

Why split off the last term? Because that exposes $S_k$, the object the IH talks about. This is the standard first move in induction proofs about sums.

⚠ Discrepancy: in the recording Püschel first wrote the $S_{k+1}$ sum incorrectly, then said after the break “da hatte ich vorhin einen Fehler drin” and fixed it. The version above (and in the script) is correct.

3.5 Induction Example 2: Bernoulli’s inequality (Bernoullische Ungleichung)

Theorem (Bernoulli's inequality)

For all $x\ge -1$ and all $n\in \mathbb{N}$:
$(1+x{)}^n\ge 1+nx.$

(Named after the Swiss mathematician Jakob Bernoulli, 17th century.) Formally, induct on $n$ with $A(n)$: ”$(1+x{)}^n\ge 1+nx$ for all $x\ge -1$”.

IA ($n=1$): $(1+x{)}^1=1+x=1+1\cdot x$, so "$\ge$" holds (with equality). ✓

IS ($n\to n+1$): strategy. Start from the left-hand side for $n+1$ and use only "$=$" and "$\ge$" steps until $1+(n+1)x$ appears, using the IH somewhere along the way.

$$\begin{array}{rlrl}(1+x{)}^{n+1}& =(1+x{)}^n(1+x)& & \text{split off one factor, exposing the IH term}\\ & \ge (1+nx)(1+x)& & \text{IH, and }(1+x)\ge 0\\ & =1+x+nx+n{x}^2& & \text{multiply out}\\ & \ge 1+x+nx=1+(n+1)x& & \text{since }n{x}^2\ge 0.\end{array}$$

$■$

The two delicate points:

1. Multiplying an inequality by a number is only allowed if that number is non-negative, otherwise the inequality flips. We multiply $(1+x{)}^n\ge 1+nx$ by $(1+x)$. This is exactly where $x\ge -1⟺1+x\ge 0$ is used.
2. Dropping $n{x}^2$ is allowed because it is $\ge 0$ (as $n\ge 1$ and $x^2\ge 0$) and we only want "$\ge$".

Exam Trap: use every hypothesis

At the end of a proof, check that you have used every assumption. If a hypothesis (here $x\ge -1$) was never used, you have probably overlooked something.

⚠ Transcript garble: the expansion was transcribed as “1 plus x plus x plus nx Quadrat”. The correct expansion is $(1+nx)(1+x)=1+x+nx+n{x}^2$.

3.6 Induction Example 3: a simple recurrence (base case $\ne 1$)

Claim

Let $F(2)=2$ and $F(n)=F(n-1)+2$ for $n>2$. Then $F(n)=2(n-1)$ for all $n\ge 2$.

The function is defined only from $2$ on: $F(2)$ is given directly, and the recurrence gives all larger values. So the claim starts at $2$, and the base case is $n_0=2$. There is no statement for $n=1$.

IA ($n=2$): $F(2)=2=2(2-1)$. ✓

IS ($n\to n+1$, $n\ge 2$): assume $F(n)=2(n-1)$. Since $n+1>2$, the recurrence applies:

$$F(n+1)=F(n)+2\stackrel{\text{IH}}{=}2(n-1)+2=2n=2((n+1)-1).$$

Writing the result in the form $2((n+1)-1)$ makes it visible that it matches the claim for $n+1$. $■$

⚠ Script typo: the last line in the script reads "$2n=2(n+1)-1)$". The parentheses are misplaced. Correct: $2n=2((n+1)-1)$.

3.7 Telescoping to find the closed form

Suppose we did not already know the answer $2(n-1)$. Unroll the recurrence (valid for all $n>2$):

$$\begin{array}{rlrl}F(n)& =F(n-1)+2& & \\ & =F(n-2)+2+2=F(n-2)+2\cdot 2& & \text{(recurrence for }n-1\text{)}\\ & =F(n-3)+3\cdot 2& & \\ & ⋮& & \\ & =F(n-j)+j\cdot 2.& & \end{array}$$

Pattern: subtracting $j$ in the argument adds $j$ twos. To reach the base case $F(2)$ we take $j=n-2$:
$F(n)=F(2)+2(n-2)=2+2n-4=2(n-1).$
The "$⋮$" is not a proof, so the induction of §3.6 then nails it down.

3.8 Star Search: naive algorithm

Algorithm: ask every $P_i$ about every $P_j$ ($i\ne j$). Then all “knows” relations are known, and we can check the star definition directly.

Count: an $n\times n$ table without the diagonal (no one is asked about themselves):
$n^2-n=n(n-1)\text{ questions.}$
This is quadratic. For about 300 people in the hall, roughly $300\cdot 299\approx 90000$ questions (the lecture says “about 100,000”).

3.9 Star Search: recursive / inductive algorithm (first attempt)

Design idea (inductive algorithm, induktiver Algorithmus): solve the problem for $n$ persons, given the solution for $n-1$ persons. This is induction used not as a proof but as an algorithm construction method: build the size-$n$ solution from the size-$(n-1)$ solution, just like an induction step.

Base case $n=2$: ask both possible questions ($P_1\to P_2$ and $P_2\to P_1$), so 2 questions. There is a star iff exactly one of the two knows the other.

For $n\ge 3$:

• Step 0: send one person out of the room, w.l.o.g. $P_n$.

• Step 1 (recursion): find the star among $P_1,\dots ,P_{n-1}$.

• Step 2: if step 1 returned a star $P_s$, test whether $P_s$ is a star among all $n$ by asking

  • $P_s\to P_n$ (must be no), and
  • $P_n\to P_s$ (must be yes).

  If both are as required, $P_s$ is the star (there is at most one). Done.

• Step 3: reached if step 1 found no star or step 2 failed. Then the only possible candidate is $P_n$. Test it with, for all $i\ne n$ (i.e. $i=1,\dots ,n-1$):

  • $P_n\to P_i$ (must be no), and
  • $P_i\to P_n$ (must be yes).

  If all succeed, $P_n$ is the star; otherwise there is no star.

Lemma (why only $P_n$ remains a candidate)

If $P_j$ with $j\le n-1$ is a star among $P_1,\dots ,P_n$, then $P_j$ is also a star among $P_1,\dots ,P_{n-1}$.
Proof: both star conditions only become weaker when persons are removed. “Everyone knows $P_j$” and ”$P_j$ knows nobody” still hold for the subset. $■$
Contrapositive (Püschel: “Wenn ich kein Star bin unter wenig Personen, dann bin ich auch kein Star unter vielen”): if the recursive call finds no star, or its star $P_s$ fails in step 2, then no $P_j$ with $j<n$ can be the star of the full group. Only $P_n$ is left.

Analysis. Let $F(n)$ be the number of questions.

Best case (step 2 always succeeds, step 3 never runs):
$F(2)=2,F(n)=F(n-1)+2⟹F(n)=2(n-1).$
This is exactly the recurrence from §3.6, already solved. Example for the best case (script): a chain where $P_1$ is the star of every prefix group, e.g. everyone knows $P_1$ and $P_1$ knows nobody.

Worst case (step 3 is needed in every recursive call): this happens if the person sent out is always the star of the current group. Step 3 costs $2(n-1)$ questions.

Subtle detail (lecture): if we reach step 3 after step 2 failed, the two questions between $P_s$ and $P_n$ were already asked, so step 3 needs only $2(n-2)$ new questions. Then step 2 + step 3 costs $2+2(n-2)=2(n-1)$. If step 1 found no star, step 3 alone costs $2(n-1)$. Either way the step adds $2(n-1)$.

$F(2)=2,F(n)=F(n-1)+2(n-1)(n>2).$

Telescoping:

$$\begin{array}{rlrl}F(n)& =F(n-1)+2(n-1)& & \\ & =F(n-2)+2(n-2)+2(n-1)& & \\ & =F(n-3)+2(n-3)+2(n-2)+2(n-1)& & \\ & ⋮& & \\ & =F(2)+2\cdot 2+2\cdot 3+\cdots +2(n-1)& & (n-2\text{ summands})\\ & =2\cdot 1+2\cdot 2+\cdots +2(n-1)& & (F(2)=2=2\cdot 1)\\ & =2\sum _{j=1}^{n-1}j=2\cdot \frac{(n-1)n}{2}=n(n-1).& & \end{array}$$

⚠ Transcript garble: the spoken version of this telescoped line (“2 mal n minus 1, … bis 2 mal 2 plus 2 mal 2 plus 2 mal 3 …”) is muddled. The correct sum is shown above and matches the script’s table, $2+2\cdot 2+\cdots +2(n-1)=n(n-1)$.

Verdict: $n(n-1)$, no better than the naive algorithm. The recursive idea by itself does not help. You only find out by analysing it.

3.10 Star Search: improved algorithm ($3n-4$)

Diagnosis: the expensive part is step 3, which happens because the person sent out might be the star.

Idea: make sure never to send out a star in step 0. Then step 3 is never needed: if the recursive call finds no star, there is none (the removed person is not a star either), and if step 2 fails, there is none.

How, with one question? Pick two persons $P_i,P_j$ and ask $P_i\to P_j$:

• Answer yes: $P_i$ knows someone, so $P_i$ is not a star.
• Answer no: $P_j$ is not known by $P_i$, so $P_j$ is not a star.

Either way, one question identifies a guaranteed non-star. That person is sent out.

Key asymmetry

Proving that someone is not a star is cheap (one question). Proving that someone is a star is expensive (all $2(n-1)$ questions).

Script formulation of the new step 0:

0. If $P_{n-1}$ knows $P_n$, swap $P_{n-1}$ and $P_n$.

Correctness: if the original $P_n$ is a star, then $P_{n-1}$ knows it and they are swapped. The new $P_n$ (the old $P_{n-1}$) knows someone, so it is not a star. If they are swapped, the person now called $P_n$ is the old $P_{n-1}$, who knows the old $P_n$ and is therefore not a star. If not swapped, $P_{n-1}$ does not know $P_n$, so $P_n$ is not a star. In every case the new $P_n$ is not a star and can be sent out.

StarSearch(P_1, ..., P_n):                  // returns the star or NONE
    if n == 2:
        ask P_1 -> P_2 and P_2 -> P_1
        if  P_1 knows P_2 and not (P_2 knows P_1): return P_2
        if  P_2 knows P_1 and not (P_1 knows P_2): return P_1
        return NONE
    // Step 0: guarantee P_n is not a star (1 question)
    if P_{n-1} knows P_n:
        swap(P_{n-1}, P_n)
    // Step 1: recursion on the first n-1 persons
    s := StarSearch(P_1, ..., P_{n-1})
    if s == NONE: return NONE              // P_n is not a star either
    // Step 2: verify s against P_n (2 questions)
    if not (s knows P_n) and (P_n knows s):
        return s
    return NONE                            // no Step 3 needed

Analysis (worst case): per recursion level at most $1$ (step 0) $+2$ (step 2) $=3$ questions.
$F(2)=2,F(n)=F(n-1)+3(n>2).$
Worst case = step 2 is always executed, i.e. step 1 always returns a star. If it returns “no star”, we stop early.

Telescoping:

$$F(n)=F(n-1)+3=F(n-2)+2\cdot 3=F(n-3)+3\cdot 3=\cdots =F(2)+3(n-2)=2+3n-6=3n-4.$$

Induction proof of $F(n)=3n-4$ for $n\ge 2$: IA: $F(2)=2=3\cdot 2-4$ ✓. IS: $F(n+1)=F(n)+3\stackrel{\text{IH}}{=}3n-4+3=3(n+1)-4$ ✓. $■$

Result

The improved inductive star search needs at most $3n-4$ questions in the worst case. “At most”, because some questions may repeat: step 0 may ask the same pair as a later step 2. This is linear: for about 300 people, under 900 questions (lecture: “about 1000”) instead of about 90,000.

Meta-lesson

The only design idea that went in was the inductive one: build the solution for $n$ from the solution for $n-1$. The algorithm follows almost mechanically from it. Analysis shows whether it is good. Here a second iteration (“which person should we remove?”) was needed to make it efficient.

---

4. Worked Examples & Applications

Example: naive star search, $n=3$

Question table (rows: who is asked; columns: about whom; ”–” = not asked):

$P_i\to P_j$	$P_1$	$P_2$	$P_3$
$P_1$	–	yes	yes
$P_2$	no	–	no
$P_3$	no	yes	–

$6=3^2-3$ questions. Who is the star? Column $P_2$ is all “yes” (everyone knows $P_2$), and row $P_2$ is all “no” ($P_2$ knows nobody). So $P_2$ is the star.
(Lecture: a student first suggested $P_1$, reading the table the wrong way round. A star must be known (its column is all “yes”) and must not know anyone (its row is all “no”). $P_1$ knows others, so it is not a star.)

Example: improved star search, $n=4$

Relations: $P_1\to P_2$, $P_1\to P_3$, $P_3\to P_2$, $P_4\to P_2$; nobody else knows anyone.

• $n=4$, step 0: does $P_3$ know $P_4$? No, so $P_4$ is not a star and is sent out. (1 question)
• $n=3$ on $\{P_1,P_2,P_3\}$, step 0: does $P_2$ know $P_3$? No, so $P_3$ is sent out. (1)
• $n=2$ on $\{P_1,P_2\}$: $P_1\to P_2$ yes, $P_2\to P_1$ no, so the star is $P_2$. (2)
• Back at $n=3$, step 2: $P_2\to P_3$? no ✓. $P_3\to P_2$? yes ✓. So $P_2$ is the star of $\{P_1,P_2,P_3\}$. (2)
• Back at $n=4$, step 2: $P_2\to P_4$? no ✓. $P_4\to P_2$? yes ✓. $P_2$ is the star. (2)

Total: $1+1+2+2+2=8=3\cdot 4-4$. ✓

Exam Trap: "early termination" does not fix the worst case

A student proposed: “as soon as $P_1$ knows someone, stop asking $P_1$.” Püschel first accepted this, then corrected himself at the start of Part 3:

1. Knowing $P_1$ is not a star does not make $P_1$ irrelevant. Any other $P_j$ can only be a star if $P_1$ knows $P_j$, so we still need $P_1$ to answer questions about others.
2. More generally, special-case shortcuts (“in this situation I can save something”) do not improve the worst case. Improvements must hold in every case.

Exam Trap: elementary operations must stay elementary

“Ask each person how many others they know” is not one elementary operation. It hides $n-1$ elementary questions. Always count in the agreed elementary operation.

Exam Trap: off-by-one in the worst-case picture

In Pasture Break the worst case is the maximal near-miss: $k-1$ (Algorithm 1) or $2^{i-1}$ (Algorithm 2) on the correct side, followed by a full useless sweep on the wrong side. Choosing $2^{i-2}$, or forgetting the return trips, gives wrong counts.

Exam Trap: base case when the statement starts at $n_0\ne 1$

If a claim is only defined for $n\ge 2$, the base case is $n=2$, not $n=1$. In the step, make sure the recurrence is actually applicable: $F(n+1)=F(n)+2$ needs $n+1>2$, which holds for all $n\ge 2$.

Exam Trap: inequalities in induction

Multiplying both sides of an inequality by a negative number flips it. In Bernoulli the hypothesis $x\ge -1$ exists precisely to guarantee $1+x\ge 0$. Without it the statement can fail: $x=-4$, $n=3$ gives $(-3{)}^3=-27\ngeqq 1-12=-11$.

Student questions from the lecture (answered):

• Is the fence finite? No, it is infinite, so $k$ can be arbitrarily large, but it is a fixed number.
• Why stop at $k$ and not continue to $k+1$? The cow sees the gap at distance $k$ and leaves.
• Can’t we exploit assumptions like "$k<1000$"? No. Solutions must work for all $k$.
• Does tripling help in Pasture Break? Not in the worst case (it gets worse, see Q1).
• Is the recursive star algorithm more efficient? “We don’t know yet; we only know after analysing it.” (It turned out not to be, until step 0 was improved.)
• Lower-bound thought: every person must be involved in at least one question, so one can hope for something linear but not better. (This is only a heuristic. No formal lower bound was proved.)

---

5. Intuition & Conceptual Bridges

Intuition: doubling = balance effort and information

Algorithm 1 pays an ever-growing cost per round for a constant amount of new information (1–2 new positions). Doubling makes the new region in each round about as big as everything explored before. The total work is then a geometric series, dominated by its last term, so the cost is proportional to the final distance and therefore $O(k)$. Geometric growth (doubling) will come back often: dynamic arrays, exponential search, and similar.

Intuition: induction as proof and as design

• As proof: $A(1)$ plus ($A(k)\Rightarrow A(k+1)$) gives $A(k)$ for all $k$.
• As design: “solve size 1 or 2 directly” plus “turn a size-$(n-1)$ solution into a size-$n$ solution” gives an algorithm for every $n$.
• As analysis: this design automatically produces a recurrence (cost($n$) = cost($n-1$) + cost of the step). Telescoping guesses its solution; induction proves it.
  The same structure appears three times, which is why Püschel stresses the “deep connection” between induction and certain algorithms, both in analysis and in construction.

Intuition: why the step cost decides everything

For $F(n)=F(n-1)+c(n)$ we get $F(n)=F(\text{base})+\sum c(\cdot )$.

• constant step cost $c$ → linear total ($2(n-1)$, $3n-4$),
• linear step cost $\sim n$ → quadratic total ($n(n-1)$).
  So in an inductive algorithm the whole game is to make the step from $n-1$ to $n$ cheap. That is exactly what the improved step 0 does: it turns a $2(n-1)$ step into a $3$ step.

Connections:

• Backward: Gauss’s sum $\sum j=k(k+1)/2$ was on exercise sheet 0. The geometric sum $2^k-1$ is the binary number $11\dots 1_2$.
• Forward: next lecture covers the RAM model and asymptotic analysis (O-notation), i.e. formalising “linear beats quadratic for large $n$, constants don’t matter”. Exercise sheets 0 and 1 prepare the mathematics. Later in the course come recursion and divide-and-conquer (recurrences of the form $T(n)=aT(n/b)+\dots$), sorting algorithms, correctness proofs (e.g. invariants), and data structures.

---

6. Summary & Self-Assessment Questions

Cheat Table

Topic	Key fact
Algorithm	complete, unambiguous, generally valid description of a sequence of elementary operations solving a problem
Analysis focus	worst case (a guarantee), never best case
Pasture break, $k$ known	worst case $3k$ (optimal)
Pasture break, step $+1$	worst case $2{\sum }_{j=1}^{k}j+k=k(k+2)$
Pasture break, doubling	$2^{i-1}<k\le 2^i$; worst case $2(2^{i+1}-1)+k<9k$
Optimality	$9k$ is best possible: $(9-\epsilon )k$ lower bound (no proof given)
Gauss sum	${\sum }_{j=1}^{k}j=k(k+1)/2$
Geometric sum	${\sum }_{j=0}^{k-1}{2}^j=2^k-1$
Induction	IA: $A(n_0)$; IS: $A(n)\Rightarrow A(n+1)$ for all $n\ge n_0$; IH = assumption $A(n)$
Bernoulli	$(1+x{)}^n\ge 1+nx$ for $x\ge -1$, $n\in \mathbb{N}$
Telescoping	unroll the recurrence, spot the pattern, then prove by induction
$F(n)=F(n-1)+c$, $F(2)=2$	$F(n)=2+c(n-2)$
Star	knows nobody, known by everybody; at most one star
Naive star search	$n(n-1)$ questions
Recursive (send out $P_n$)	best $2(n-1)$, worst $n(n-1)$
Improved (send out a non-star)	worst $3n-4$
Non-star in 1 question	$P_i\to P_j$: yes means $P_i$ is not a star; no means $P_j$ is not a star
Runtime depends on	input, machine, implementation (language, compiler)
Abstraction	RAM model plus asymptotic analysis (linear vs. quadratic, ignore constants)

Self-Assessment Questions

Question 1. Instead of doubling, the cow multiplies its distance by $3$ each round ($1,3,9,27,\dots$, alternating sides). Derive the worst-case number of steps as a function of $k$ and compare with $9k$. Then generalise to an arbitrary factor $b>1$.

Solution to Question 1

Choice of $i$. Let $3^{i-1}<k\le 3^i$.

Worst case. As with doubling: the sweep of length $3^{i-1}$ goes to the correct side and just misses; the sweep $3^i$ (which would hit) goes to the wrong side; the sweep $3^{i+1}$ goes to the correct side and stops after $k$ steps. Steps:
$2(3^0+3^1+\cdots +3^i)+k=2\cdot \frac{3^{i+1}-1}{3-1}+k=3^{i+1}-1+k.$
Bound. $3^{i+1}=9\cdot 3^{i-1}<9k$, so the total is $<10k$. The bound is essentially tight: choosing $k=3^{i-1}+1$ gives $9\cdot 3^{i-1}-1+3^{i-1}+1=10\cdot 3^{i-1}\approx 10k$. Tripling is worse than doubling ($\approx 10k$ vs. $\approx 9k$).

General factor $b$. Worst case $2\cdot \frac{b^{i+1}-1}{b-1}+k$ with $k\to b^{i-1}$ from above, giving about $\left(\frac{2b^2}{b-1}+1\right)k$. Minimise $g(b)=\frac{b^2}{b-1}$:
$g^{\prime }(b)=\frac{2b(b-1)-b^2}{(b-1{)}^2}=\frac{b(b-2)}{(b-1{)}^2}=0⟺b=2,$
with $g(2)=4$, giving $2\cdot 4+1=9$. So among all geometric strategies, doubling is optimal, which matches the claim that $9k$ is best possible. (Example: $b=1.5$ gives $2\cdot \frac{2.25}{0.5}+1=10$, also worse.)

Question 2. Prove by induction that ${\sum }_{j=1}^{n}j=\frac{n(n+1)}{2}$ for all $n\in \mathbb{N}$.

Solution to Question 2

IA ($n=1$): ${\sum }_{j=1}^{1}j=1=\frac{1\cdot 2}{2}$. ✓

IS ($n\to n+1$): assume ${\sum }_{j=1}^{n}j=\frac{n(n+1)}{2}$ (IH). Split off the last summand:
${\sum }_{j=1}^{n+1}j={\sum }_{j=1}^{n}j+(n+1)\stackrel{\text{IH}}{=}\frac{n(n+1)}{2}+(n+1)=(n+1)\left(\frac{n}{2}+1\right)=\frac{(n+1)(n+2)}{2}.$
This is the claim for $n+1$. $■$

Question 3. Let $G(1)=1$ and $G(n)=G(n-1)+2n-1$ for $n>1$. Guess a closed form by telescoping and prove it by induction.

Solution to Question 3

Telescoping:

$$\begin{array}{rl}G(n)& =G(n-1)+(2n-1)\\ & =G(n-2)+(2n-3)+(2n-1)\\ & ⋮\\ & =G(1)+3+5+\cdots +(2n-1)=1+3+\cdots +(2n-1).\end{array}$$

The sum of the first $n$ odd numbers: ${\sum }_{j=1}^n(2j-1)=2\cdot \frac{n(n+1)}{2}-n=n^2$. Conjecture: $G(n)=n^2$.

Induction: IA: $G(1)=1=1^2$ ✓. IS: assume $G(n)=n^2$. Then
$G(n+1)=G(n)+2(n+1)-1\stackrel{\text{IH}}{=}{n}^2+2n+1=(n+1{)}^2.■$

Question 4. (a) Why is the first recursive star-search algorithm (always sending out $P_n$) quadratic in the worst case? Describe a worst-case instance. (b) Explain precisely why, after the improved step 0, step 3 is never needed.

Solution to Question 4

(a) Step 3 costs $2(n-1)$ questions and is required whenever the removed person $P_n$ could be the star. Worst-case instance: in every recursive call the removed person is the star of the current group. For example, let $P_n$ be the star of the whole group, $P_{n-1}$ the star of $\{P_1,\dots ,P_{n-1}\}$, and so on (each $P_m$ knows nobody among $P_1,\dots ,P_{m-1}$ and is known by all of them). Then at every level step 1 or step 2 fails to produce the star and step 3 must run:
$F(n)=F(n-1)+2(n-1),F(2)=2\Rightarrow F(n)=n(n-1).$
(b) After step 0 the removed person $P_n$ is guaranteed not to be a star. If the recursive call finds no star, then by the lemma (a star of the big group is a star of the subgroup) no $P_j$ with $j<n$ can be the star, and $P_n$ isn’t either, so there is no star. If the call finds $P_s$ and step 2 rejects it, the same argument applies. Either way the only candidate step 3 would test, $P_n$, is already excluded. So step 3 is skipped and each level costs at most $1+2=3$ questions, giving $3n-4$.

Question 5. In the proof of Bernoulli’s inequality, identify exactly where the hypothesis $x\ge -1$ is used, and show by a concrete example that the inequality can fail without some lower bound on $x$.

Solution to Question 5

In the step
$(1+x{)}^n(1+x)\ge (1+nx)(1+x)$
we multiply the IH inequality $(1+x{)}^n\ge 1+nx$ by $(1+x)$. This preserves the direction of "$\ge$" only if $1+x\ge 0$, i.e. $x\ge -1$. If $1+x<0$ the inequality would flip. (The later step dropping $n{x}^2\ge 0$ holds for all real $x$.)

Counterexample: $x=-4$, $n=3$: $(1-4{)}^3=-27$, while $1+3\cdot (-4)=-11$, and $-27\ngeqq -11$. So the statement is false for some $x<-1$, and the hypothesis is genuinely needed in the proof. (The inequality actually holds for $x\ge -2$, but proving that needs a different argument. The induction above uses $x\ge -1$.)