**Lesson 1**

*1. How many comparisons are needed to do a Bubble Sort on a list of seven items? – 21

*2. Supposing we’re lucky and the pivot always divides the list into equal halves, how many comparisons are needed in Quicksort on a list of seven items? – 10. Six at the first stage, four at the second.

*3. If the pivots are unluckily chosen, so that each time the pivot turns out to be the smallest number in the list or sublist, and the pass moves all items to the right of the pivot and none to the left, how many comparisons are needed to do a Quicksort on a list of seven items? – 21… 6 at the first stage, 5 at the second, 4 at the third, 3 at the fourth, 1 at the fifth.

*4. It would be a bit easier to do Quicksort if we always took the *first* item in a list or sublist as pivot, rather than the middle one. So why make it more complicated and take the middle item?

– To reduce the chances of the unlucky situation in *3 arising. The unlucky situation in *3 arises if the list is *already* in the right order and we choose the first item as pivot. If the list is already *almost* in the right order, then the choice of the first element as pivot will still give bad results as in *3. But almost-in-the-right order is quite a likely option. (You had a sorted list, but you’ve added a few new items, or changed a few existing items, and want to sort them in. If it was sorted ascending, and now you want to sort it descending, then the first-item choice of pivot turns out to be equally unlucky).

Only by weird coincidence will the smallest number be in the median position of the unsorted list, second-smallest in what becomes the median after eliminating the first median, third-smallest in what becomes the median after eliminating the first two, etc.

The thing in the textbook about choosing the item to the *right* of the middle as pivot if there is no middle item in the unsorted list is hocus-pocus: it would make no difference if in that case you always chose the item to the *left*, or chose to the right or to the left alternately or randomly. The essence is to choose the pivot *somewhere* in the middle.

Another way of minimising the risk of bad luck on the lines of *3 is to choose three items at random from the list or sublist, and taking the middle item of those three as pivot.

**Lesson 2**

**Extra**: *5. How many comparisons are needed to do a Bubble Sort on a list of 1023 items? – ½×1023×1022, or about half a million.

**Extra**: *6. Supposing the pivot always divides the list into equal halves, how many comparisons are needed in Quicksort on a list of 1023 items? – 7166, or only 1.4% as many as Bubble Sort. 1022 on the first pass, 1020 on the second, 1016 on the third… down to 512 on the 9th and last.

**Extra**: *7. Roughly how many comparisons will be needed for 1,048,575 items (that’s 2^{20}-1), by Bubble Sort and by Quicksort? – About 500 billion for Bubble Sort, and about 19 million for Quicksort (only 0.04% as many). If N=2^{n}, Bubble Sort will take ½N(N-1) comparisons, and in the best case Quicksort will take (n-2)N+2. It can be proved that on average, i.e. with a choice of pivots which is reasonably random compared to any order the list has before sorting, Quicksort will take about 2 n ln(n) operations, i.e. about 1.4nN.

**Extra**: *8. You already know an algorithm for sorting lists of data by hand. It’s called stem-and-leaf plot. What does that algorithm have in common with Quicksort which makes it relatively efficient? Why can’t computers be programmed to do stem-and-leaf instead of Quicksort? – Both stem-and-leaf and Quicksort are “divide and conquer” algorithms. They work by progressively chopping the problem up into smaller problems. We can’t use stem-and-leaf on computers because when working by hand on small lists (as we do with stem-and-leaf) we can just *see* what the best choice of stems is. To get a computer to work out the best choice of stems for a huge list would be about as hard as doing the whole sort.

**Answers for booklet on induction**

**Tower of Hanoi**

Claim: For all n, the game takes 2^{n}–1 moves for n disks.

Proof:

By induction.

Step 1: If you have only one disk, just move it to another rod. That is one move. You can’t do it in less, since less than one move is zero moves. ▇

Step 2: for any k, if the claim is true for n=k, then it is true for n=k+1

To move k+1 disks, you must first move the upper k disks, because otherwise you can’t move the bottom disk. If the claim is true for n=k, it takes 2^{k}–1 moves to get those upper k disks onto a second rod.

You can’t move the bottom disk on top of the k upper disks, so move it to the third rod.

Then the job is to move the k upper disks from the second rod to the third. If the claim is true for n=k, that takes another 2^{k}–1 moves.

Total moves = 2^{k}–1+1+2^{k}–1

= 2×2^{k}+1 = 2^{k+1}-1 ▇

Therefore the claim is true for all n, by induction ▇

Extra: What formula for number of moves needed, u_{n}, if there are infinitely many pegs?

It will take only 2n-1 moves to move n disks. You can move each disk onto a separate peg, and then move the

(n–1) smaller disks on top of the biggest one.

Extra: What if there are 4 pegs?

This is an unsolved problem, but many fewer moves than for 3 pegs. See here and here

**2. Claim: for all, n lines divide the plane into a maximum of A=½(n ^{2}+n+2) areas.**

Proof:

By induction.

Step 1: Prove true for n=1.

One line divides the plane intotwo areas, and ½(1^{2}+1+2)=2 ▇

Step 2: Prove that if for any k the claim is true for n=k, then it is true for n=k+1

If the claim is true for n=k, we can draw k lines dividing the plane into ½(k^{2}+k+2) areas.

If the (k+1)th line crosses all k lines at points different from their points of intersection, then it will create (k+1) new areas. [Imagine the (k+1)th line being way below all the previous points of intersection].

We then have ½(k^{2}+k+2)+k+1 areas,

or ½(k^{2}+k+2 +2k+2)

or ½(k^{2}+2k+1+k+1+2)

or ½[(k^{2}+2k+1)+(k+1)+2]

or ½[(k+1)^{2}+(k+1)+2]

which is what the claim says for (k+1) lines ▇

Therefore the claim is true for all n, by induction ▇

**3. Dividing a circle into areas**. Your mathematical task here is to show that the apparently obvious pattern isn’t valid. Find how many different areas the circle is divided into by the lines connecting: 1 point (this is just 1 area, since there is no line); 2 points; 3 points; 4 points; 5 points. What does it look like the formula should be for the number of areas? Check it for 6 points.

Answer:

1 point – 1 area

2 points – 2 areas

3 points – 4 areas

4 points – 8 areas

5 points – 16 areas

But…

6 points – 31 areas

Find a simple mathematical argument which proves that the pattern which seems obvious from n=1,2,3,4,5 can’t be valid as n gets bigger.

Argument: if you have n points, you have ½n(n+1) lines. So there surely can’t be more than ½([½n(n+1)]^{2}+[½n(n+1)]+2) areas, because those lines create only that many areas in the whole plane, let alone within the circle.

For big n, that is about n^{4}/8 areas (because for big n, n^{4} is much bigger than any n^{3},

n^{2}, n, etc. terms)

But for big n, n^{4}/8 is much less than 2^{n–1}, which is the pattern which seems obvious from n=1,2,3,4,5.

Extra extra: Find the accurate formula. (Click here).

**Claim 1**: If you add any number n and the number next to it, then the answer is odd.

Proof by induction:

Step 1: prove true for n=1

The next number after 1 is 2. 1+2=3. 3 is odd ▇

Step2: prove that if for any k the claim is true for n=k, then it is true for n=k+1

If the claim is true for n=k, then k+k+1 is odd

But the next number after k+1 is k+2

and (k+1)+(k+2)= k+k+1+2, and so is odd ▇

Therefore, claim true for all n by induction

**Claim 2: **If you add all the numbers 1+2+3+….+n, the answer is ½n(n+1)

Proof by induction

Step 1: prove true for n=1

1=½1×2 ▇

Step 2: prove that if for any k the claim is true for n=k, then it is true for n=k+1

1+2+3+….+k+(k+1)=(1+2+3+….+k)+(k+1)

If the claim is true for n=k, then this

= ½k(k+1)+(k+1)

= ½(k+1)(k+2), which is the formula the claim would give for n=k+1 ▇

Therefore the claim is true for all n by induction.

**Claim 3**: F+V–E=2 on the surface of a sphere (or anything an infinitely stretchable and squashable sphere could be made into without ripping or cutting)

Proof by induction on E, the number of edges

Step 1: Prove claim true for n=1

If there is only one edge, then there are either two vertices and one face, or one vertex and two faces.

Either way F+V−E = 1+2–1=2 ▇

Step 2: Prove that if for any k the claim is true for n=k, then it is true for n=k+1

Take a “flattened” shape with (k+1) edges.

There are four ways to remove an edge.

One: it is a loose end which doesn’t divide one face from another.

In that case, if we remove the edge, then we reduce E by 1. We reduce V by 1 (the vertex at the “dangling” end of the edge). We don’t change F. So we don’t change F+V–E

Two: it is a loop beginning and ending at the same vertex.

In that case, if we remove the edge, then we reduce E by 1. We don’t change V. We reduce F by 1 (the inside of the loop used to be a face, but now is merged into another face). So we don’t change F+V−E

Three: the edge joins two vertices and divides one face from another.

In that case, if we remove the edge, then we reduce E by 1. We reduce F by 1 and don’t change V, so we don’t change F+V–E

Four: We remove a vertex which has only two edges meeting at it, so those two edges merge into a single edge, without changing anything else.

In that case, we reduce E by 1, we reduce V by 1, and we don’t change F. So we don’t change F+V−E

In every case F+V–E is unchanged. If it was 2 before, it’s still 2 ▇