Mathematics for Computer Science

The whole numbers are 0, 1, 2, 3, 4 and onwards forever. No fractions, no decimals, nothing negative. When a claim in this course says "for every whole number n", it usually means the counting numbers 1, 2, 3 and up, and where 0 matters the claim will say so.

The letter n is a stand-in. Writing "n times n" means "pick any whole number you like, and multiply it by itself". It is exactly the x in x + 3 = 5, except that instead of one secret value to find, n is meant to be every value in turn.

One whole number divides another if it goes in exactly, leaving nothing over. 3 divides 12, because 12 is 3 fours. 5 does not divide 12, because 12 is two 5s with 2 left over. That leftover is called the remainder.

A prime number is a whole number above 1 that nothing divides except 1 and itself. 2, 3, 5, 7, 11 and 13 are prime. 9 is not, because 3 divides it. Primes are the numbers that cannot be broken into smaller factors, and they turn up in this course because claims about them are easy to state and surprisingly hard to settle.

A program is a list of instructions a computer carries out in order. An algorithm is the method behind such a list: a recipe with steps definite enough that following it needs no judgement, and that always stops with an answer."Test n, then test n plus 1, forever" is a list of instructions, but it is not an algorithm, because it never stops.

So a computer can churn through cases faster than you can, which is a real help when hunting for a counterexample. It cannot turn checking into proving, because the supply of cases never runs out. A program that has tested a billion cases has tested none of the rest, and the rest is where every surviving surprise lives.

Because the step is not a list of promises, it is one promise with a blank in it. You argue about a domino called number k without ever saying what k is, using only facts true of every position: the spacing is the same everywhere, the dominoes are the same size. If the argument uses nothing specific to k, it works for k equals 5 and for k equals five million, and you never wrote either number.

This is why induction feels like cheating the first time. You do a finite amount of work, two arguments, and walk away with infinitely many conclusions. The finite work covers the infinite collection because it was careful never to mention a particular member of it.

The three dots mean "keep going the same way". So 1 + 2 + ... + 6 means 1 + 2 + 3 + 4 + 5 + 6, which is 21. And 1 + 2 + ... + n means start at 1 and add every whole number in order until you have added n. If n is 4 the sum is 10. If n is 1 the sum is just 1, since you start and stop in the same place.

Nobody writes out a hundred terms. The dots are shorthand for a pattern the reader can continue, and the pattern has to be obvious from the terms shown, which is why sums like this are always written with at least the first two.

Then you have proved nothing, and you can prove nonsense. Take the claim "n equals n plus 1". The step is fine: if n equals n plus 1 then adding 1 to both sides gives n plus 1 equals n plus 2, which is the claim for the next value. Every domino would knock over the next one perfectly.

But 1 does not equal 2, so the first domino never falls, and the whole line stays standing. A step without a base case is a line of dominoes nobody pushed. The next lab lets you glue the first one down and watch exactly that happen.

No, and it is worth knowing why. Take the claim you actually care about and wrap it: instead of "the claim holds at n", prove "the claim holds at every value from the start up to n". That wrapped claim can be pushed along by ordinary induction one step at a time, because knowing it up to k is exactly the pile of facts a strong step wants.

So strong induction is ordinary induction wearing a coat. People use it because it saves the bookkeeping, not because it can reach anything the plain version cannot. This is safe to skip: nothing later depends on it.

Take any collection of whole numbers that is not empty. It has a smallest member. That sounds too obvious to name, so mathematics names it anyway: the well-ordering of the whole numbers.

It is worth naming because it stops being true almost immediately if you leave the whole numbers. The fractions between 0 and 1 have no smallest member: whatever tiny fraction you pick, half of it is smaller and still in the collection. The negative whole numbers have no smallest member either. So well-ordering is a real property of a particular collection, not a piece of common sense, and every argument in this step leans on it.

Claim: every whole number above 1 is either prime, or a product of primes multiplied together. Suppose it were false. Then some number breaks it, so by well-ordering there is a smallest breaker. Call it m.

m is not prime, or it would satisfy the claim by itself. So m is a times b with both a and b bigger than 1 and smaller than m. Both are smaller than m, and m was the smallest breaker, so a and b both satisfy the claim: each is a product of primes. Multiply those two products together and you have m as a product of primes, which contradicts m being a breaker. So there is no smallest breaker, so there is no breaker.

In this subject, yes, always."You may have tea or coffee" in ordinary speech usually means one or the other and not both. In logic,"A or B" is true in three of the four situations, and false only when both parts are false.

When someone means strictly one or the other, they say exclusive or and spell it out. The plain "or" is inclusive, and the reason is convenience: inclusive or obeys tidier rules and the exclusive version is easy to build out of the three combiners when you actually want it.

Take the promise "if it rains, I will bring an umbrella". It is broken in exactly one situation: it rained and you did not bring one. If it did not rain, the promise is not broken whatever you did, because it never asked for anything.

So "if A then B" counts as true whenever A is false, which strikes everybody as odd the first time. "If the moon is cheese then I am a fish" is a true statement. It has to be, because a promise with a condition that never fires cannot have been broken. This is the same point the induction step made in Step 2, in different words.

Search boxes and filters."Show me everything that is not (cheap and fast)" is the same set as "everything that is either expensive or slow". People get this wrong constantly, usually by turning the first into "not cheap and not fast", which is a much smaller set: it drops everything that is cheap but slow.

The same swap runs through hardware, where the two combiners are physical circuits, and through searching, where a filter is turned inside out to make it faster. Safe to skip, but once seen you will notice it every week.

Read the description and look for the joining word."A sandwich and a drink" is two choices that both happen, so multiply."A sandwich or a soup" is one item drawn from two separate groups, so add. The word in the sentence is doing the arithmetic.

The trap is that adding is only correct if nothing sits in both groups. If three items appear on both the sandwich list and the soup list, adding the two lists counts those three twice, and the answer is the sum minus 3. Multiplying has its own condition: the number of drinks must not depend on which sandwich you picked.

Two light switches, each up or down, give four arrangements: up-up, up-down, down-up, down-down. Add a third switch and each of those four splits in two, giving 8. A fourth gives 16, a fifth 32. Each new switch doubles the count, because every arrangement of the old switches survives twice, once with the new switch up and once with it down.

Multiplying n twos together is written 2 to the power of n, and in the labs here it is typed as power(2, n). So power(2, 3) is 2 times 2 times 2, which is 8, and power(2, 10) is 1024. The same shorthand works for any base: power(10, 3) is 1000. The one that surprises people is power(2, 0), which is 1, because zero switches still have exactly one arrangement, the empty one.

Because a computer's smallest choice is a bit, which has two settings. Everything is built by putting bits side by side, so the number of possibilities is always some number of twos multiplied together. Eight bits in a row is the usual bundle, and it has power(2, 8) settings, which is 256. That bundle of eight bits is called a byte. It is the unit files and memory are measured in.

Doubling gets out of hand fast, and that cuts both ways. Thirty bits already give more than a billion arrangements, which is why a password of decent length cannot be guessed by trying them all. Thirty items to arrange give a number with 33 digits, which is why some perfectly clear questions cannot be answered by a computer checking every case, no matter how fast it is.

10 factorial is about 3.6 million. 13 factorial is over 6 billion. 20 factorial has 19 digits, and counting them at a billion per second would take about 77 years. 60 factorial is larger than the number of atoms anybody thinks exists.

This is why "just try every order and pick the best" is not a plan. A delivery van with 20 stops has 20 factorial routes. No faster computer rescues that, because doubling the speed of the machine buys you less than one extra stop. Problems shaped like this are the reason algorithms get invented.

Count handshakes at a party of 5. Pick the first person: 5 ways. Pick the second: 4 ways left. That is 20, but it is wrong, because picking Ana then Ben and picking Ben then Ana are the same handshake counted twice. So the answer is 20 divided by 2, which is 10.

The pattern is general. Whenever order does not matter, count as though it did and then divide by the number of orders you have overcounted by. For pairs that number is 2, because two things can be arranged in 2 factorial ways. For triples it is 6, because three things can be arranged in 3 factorial ways.

Write "n choose k" for the number of ways to pick k things out of n. Now single out one particular item, say the red one. Every selection either includes the red one or does not, and there is no third case, so add the two counts.

Selections that include the red one still need k minus 1 more items from the other n minus 1, and selections that leave it out need all k from the other n minus 1. Those two counts are exactly the two entries sitting above in the triangle. So the triangle is not a coincidence or a pattern somebody spotted: it is that one sentence, drawn.

"Some hole holds at least 8" does not say which hole, and does not say 8. It says there is a hole with 8 or more, and it refuses to say anything else. That vagueness is the source of its strength: the claim survives every arrangement, including the ones designed to break it.

The opposite mistake is common. Pigeonhole never says the items are spread evenly, and it never says two particular items collide. It says a collision exists somewhere. When you need to know where, you need a different argument.

Suppose someone claims a program that makes every file smaller, and a matching program that puts each one back exactly. Count the files of exactly 10 bits: there are power(2, 10) of them, which is 1024. Every one of them has to come out shorter, so every one lands among the files of 9 bits or fewer, and there are only 1023 of those, counting the empty one.

1024 items, 1023 holes. Two different files must squash to the same thing, and then the program that puts them back cannot know which one it started from. So the claim is impossible, for every program, forever and the argument fits in a paragraph. Safe to skip, but it is the clearest example of a proof that rules out an entire industry of promises.

A probability is how often something happens out of all the equally likely possibilities. A fair die has 6 faces, and 2 of them are above 4, so the probability of rolling above 4 is 2 out of 6, which is the fraction 1/3, the decimal 0.333, and 33.3 percent. Those are three spellings of one number.

Probability 0 means it never happens and probability 1 means it always happens, and everything real sits between. The word "chance" is used here for the same thing. Nothing in this step needs more than that, and Step 8 builds the rest. Continue with Probability for Engineering for distributions, Monte Carlo simulation, reliability and quality assurance.

Because 10,000 trials is a sample and not the whole story. Rolling two dice 10,000 times will give you around 1,667 sevens, but the exact count changes every run, and being off by 40 or 50 is completely ordinary. Nothing has gone wrong when that happens.

What does shrink is the error as a fraction. At 100 trials the measured share of sevens might be 12 percent or 21 percent. At 10,000 it will sit within a fraction of a percent of 16.67. The gap shrinks roughly in step with the square root of the number of trials, so getting the error ten times smaller costs a hundred times as many trials.

Two things are independent when knowing one tells you nothing about the other. Two dice are independent: the first showing a 6 changes nothing about the second. That is what lets you multiply probabilities to get the chance of both.

Drawing two cards from one pack without putting the first back is not independent, because the first card changes what is left. Multiplying as though it were is one of the most common mistakes in the subject, and the whole of Step 9 is what happens when people ignore it.

No. The coin has no memory, no ledger and no sense of fairness. The next flip is a half, exactly as the first one was, and the nine tails before it are irrelevant to a piece of metal.

What confuses people is that the long-run share really does settle near one half. It settles by being swamped, not by being corrected. Nine extra tails is a large lead over ten flips and an invisible one over a million, so the average drifts back towards a half without anything ever pushing it there. Lab 16 shows this happening as a line on a chart.

A false positive is an alarm on somebody healthy. A false negative is silence about somebody ill. They are separate numbers and improving one usually worsens the other, because a test made keener catches more of the ill and also startles at more of the healthy.

Which mistake matters more depends entirely on what happens next. For a cheap screening test followed by a careful second test, false alarms are tolerable and misses are not. For a test that triggers surgery, the trade runs the other way. There is no accuracy number that captures this, which is why one is never quoted alone.

It means: throw away everybody for whom B is false, and ask about A among those who are left. The chance that a person is ill is one question. The chance that a person is ill given that they tested positive is a different question, asked of a much smaller group.

Swapping the two is the mistake this whole step is about."99 percent of ill people test positive" and"99 percent of positive people are ill" are different sentences with different answers, and they are confused so often that the confusion has a name: the base rate fallacy.

Because after the first positive you are no longer standing in the general population. You are standing in the group of people who tested positive, and in that group the illness is far more common than it was outside. The base rate for the second test is the answer from the first.

That is the whole of Bayes' rule in one sentence: evidence does not give you an answer, it updates the count you already had. Lab 18 does the second test on the same grid and you can watch the proportion jump.

The same way the average household can have 1.7 children. An average is a summary of a pile of numbers, and there is no rule that a summary must be one of the things it summarises. 3.5 is the balance point of the six faces, the place where the die's payouts would balance on a see-saw.

This matters when the average is used to make a decision."The expected wait is 4 minutes" is compatible with everybody waiting either 30 seconds or 20 minutes and nobody ever waiting 4. The average alone cannot tell you which world you are in, and that is what the second half of this step is for.

Squaring a number means multiplying it by itself: 5 squared is 25. The square root undoes that: the square root of 25 is 5, because 5 is the number that gives 25 when squared. The square root of 9 is 3, of 100 is 10, of 2 is about 1.414.

It appears here because the natural measure of spread is built from squared distances, which come out in the wrong units. Squaring pounds gives square pounds, which mean nothing, so taking the square root at the end brings the answer back to pounds where it can be compared with the payouts.

Averages add, always, even when the things being averaged interfere with each other. The average total of two dice is 3.5 plus 3.5, which is 7, and you do not need to look at the 36 combinations to know that. This is called linearity of expectation and it is the single most useful fact in the subject.

What makes it surprising is that it does not need the parts to be independent. The average number of people who get their own hat back from a shuffled pile is 1, no matter how many people there are, and it is proved by adding n averages of 1/n each, despite the hats being tangled together in an unpleasant way. Safe to skip; nothing later needs it.

Because the argument is "those big values on their own already account for the whole average". If other values are allowed to be negative, they can cancel the big ones out, and the average stops being evidence about them.

A quick example. Half the time you win 1,000 and half the time you lose 1,000, so the average is 0. Markov with a threshold of 10 would claim the chance of reaching 10 is at most 0 divided by 10, which is zero, and yet it happens half the time. Delivery times, queue lengths and counts of things are all safely non-negative, which is why the inequality is useful in practice.

Often, yes, because of what it costs. Markov needs one number, the average, and no assumption about the shape of anything. A bound that holds for every possible shape has to be loose for most of them: it is being honest about how little it was told.

Give it a second number and it tightens sharply, which is what Chebyshev's inequality does. In practice these bounds are used to prove that something is rare enough to ignore, and "at most one in a million" is a satisfying answer even when the truth is one in a billion.

The ones with nothing in the middle. If a payout is either 0 or exactly the threshold, and nothing else, then Markov's fence sits precisely on the truth. Average 30 with a threshold of 90 is achieved by paying 90 one time in three and 0 otherwise and the bound of one third is then exact.

This is worth knowing because it explains why the bound cannot be improved in general. Any sharper rule using only the average would be false for that distribution. The bound is loose for your case because your case is nicer than the worst one, and the bound was not told which case it had. The lab lets you build this exact distribution and watch the fence land on the truth.

Because positive and negative positions cancel when averaged. For every walk that ends 12 paces right there is an equally likely mirror-image walk ending 12 paces left, and averaged over the pair they contribute nothing. The average is exactly 0 and almost nobody is standing there.

The fix is to stop letting the signs cancel. Square the position first, so left and right both count as positive, average those squares, and take the square root at the end. That is the same repair as the standard deviation in Step 10, applied to the same problem.

It promises that shares settle. It does not promise that a walker returns to the start, that a run of bad luck is repaid, or that anything is due. On a line with no walls, a walker does come back to the start eventually with certainty, which is a real theorem, but the average wait for that return is infinite, which makes it useless as a plan.

Add a wall and the picture changes completely. A gambler with £10 playing a fair game against a casino with millions will hit zero and stop, not because the game is unfair but because one side runs out first. Lab 24 has a wall you can switch on.

Shuffling a pack by repeated small swaps is a walk through the arrangements, and the question "how many swaps until it is properly mixed" is a walk question. Spreading web requests across servers at random is a walk in the queue lengths and the square root law is what says the imbalance stays modest. Estimating a quantity by taking random samples is a walk in the running estimate and the square root is why a hundred times as many samples buys only ten times the accuracy.

The same shape also runs through physics, where it describes a dust speck jostled by air molecules, and finance, where it is the starting model for a price. Safe to skip; nothing later depends on it.

A list has positions, so [red, blue] differs from [blue, red]. A bag, also called a multiset, keeps counts, so two red marbles differ from one. Converting either to a set deliberately forgets some information. Ask whether that loss is allowed before using a set.

Not every item passed means at least one item failed: ¬∀x P(x) is ∃x ¬P(x). No item passed means every item failed: ¬∃x P(x) is ∀x ¬P(x). The quantifier flips and the predicate is negated.

A transitive closure adds xRz whenever a path of relation steps connects x to z. Reachability is the transitive closure of one-step graph edges. Reflexive and symmetric closures similarly add self-pairs or reverse pairs. The closure is the smallest enlarged relation with the requested property.

The direct Fibonacci program recomputes the same F values many times and takes exponential work. Storing each answer makes every state run once, giving linear work. The mathematical recurrence for the value is unchanged; the running-time recurrence changes because repeated subproblems disappear.

E[X+Y]=E[X]+E[Y] whether or not X and Y are independent. Variance is different: Var(X+Y) also has a covariance term. Independence makes that term zero, but simply omitting it from dependent variables understates or overstates the spread.

A finite undirected graph is a tree exactly when it is connected and has |V|-1 edges. Equivalently, it has no cycle and |V|-1 edges, or there is exactly one simple path between every two vertices. These equivalent views support different proofs and algorithms.