ArthurNormanQuotes/Michaelmas2001

Advanced Algorithms (Part IB)

For twelve lectures I will stand at the front and wave my hands around madly and those of you who understand semaphore will be able to tell when I'm saying "Help!"

You can look at the nice thick book of horrible algorithms. [Pause] Or the horrible thick book of nice algorithms, depending how you look at it.

If you want a random number, how should you get one? Think one out of thin air? Well, do you really think my brain behaves randomly? [Laughter] Well, if that doesn't work how about asking a friend for one?

Whether you consider this a useful bit to make because I'm so trustworthy is a matter of doubt.

The first time you get an output x, you say "Hooray, hooray, I found it!"

Solving the Halting Problem is quite difficult. "Difficult" here means "undecidable". This means that if we all get together and put our shoulders to it we're not going to make much headway.

You could just stick an emulator for Microsoft Windows, heaven help us, on the front of a Turing machine.

We're theoreticians today. Here, let me put on my theoretician's hat and look wild and ferocious.

Those sure are big mice up there. I think they've got rollerblades.

I present to you conditional Kolmogorov complexity as a way of determining stealing of intellectual property, plagiarism and the like. The fact that it is undecidable may give you comfort in believing that for your Part II projects you can download something from the web and submit that as your entire dissertation.

There are a finite number of them. I admit it may be rather a large finite number, but hey, we're theoreticians and we don't mind large finite numbers.

If it takes them ten zillion years to derive the code from the old code, then they might as well have coded it from scratch and it would only have taken them an afternoon.

With a probability so high that the world is likely to have crumbled into dust with far greater frequency, it will have a Kolmogorov complexity of more than a half n.

If the probability is less than the probability of other things going wrong such as me spontaneously bursting into flames - I'm not going to demonstrate that one right now - ...

I'm sure you can see that the main reason that I'm using this example is that I've got a lot of coloured pens to use.

If I cheat, you will notice that they are the same colour, or that one of them is blank, or that I've written "Ha ha, I bet you don't choose this one" on one of them.

Anyone who thinks it sounds like doubletalk talking about worst case average costs is right: you have to do some fancy footwork here.

This particular one [oracle], as well as chewing laurel leaves, has a big pile of coins which it can toss, making its utterances truly random.

We put this in a cardboard box, to make a random-oracle-in-a-box, and sell it to people in the form of a PCI card which they can plug in their computer.

Getting something which is truly random and has a probability of one half of giving a zero or a one is almost witchcraft, so I think I'll draw a pointy hat on the oracle.

Most reasonable people are happy to say "Well, it's prime enough for me."

If one of them divides into N you can say "Yahoo, wahee, I've found a factor! I'm so clever."

It's not a random sequence at all, but for these purposes it behaves sufficiently shambolically.

This allows us to call it the rho method, on the grounds that any time you draw a squiggle, you look through the Greek alphabet for the nearest letter and use that to name your method. Presumably if the Greek letters don't fit, you look through the other alphabets of the world until you find one which does and transliterate the glyph into something which sounds reasonably English.

[In personal conversation, wrt Part II projects] If it wasn't nasty and hard, it wouldn't be any fun making them do it.

[In personal conversation, wrt the Coton foot/cyclepath which goes close to the William Gates building] When I start driving my Landrover down that footpath...

You would be able to decrease that multiplier there to one plus a tiddly bit for as small a tiddly bit as you like.

If you use the mathematicians' way of doing this you will use many more pages and be left thinking that you're rather clever. Whereas I think this version [the compsci version] will leave you feeling tolerably ingenious.

I am going to chase this through in a way that will put the word "log" on the paper rather a large number of times and perhaps look slightly sordid on that basis, but never mind.

For the first part of this part I will assume that my arrays are infinitely long, but not so infinitely long that we need infinite precision arithmetic to index into them.

This is going to be the long-haired ferocious computer scientist with a theoretical bent who isn't worried about the practicality of writing programs.

If you go all the way back to that stuff which if you're lucky has begun to fade into a dull ache from being a sharp pain, ...

If you've got something where you're going to want to do a lot of big integer arithmetic and you're going to want to test equalities but not inequalities and you're not going to want to print the answer, then this representation will be useful.

I'm going to use the number ten as my prime. Any of you who say that ten isn't a prime, yeah, well, fair cop, but it's still going to be easier.

The program you have written will impress all your friends, because it doesn't look like you're doing anything at all sane anywhere.

One way of getting round that, which works really well and allows you to go from really large numbers to bizarrely stupidly huge numbers...

A nicer - well, well I say nicer, a much less obvious way...

A power of two and an odd number tend not to have many common factors.

The tail end of the last time I gave a lecture rather than making you feel miserable...

Anyone who can present me a good explanation on a single sheet of paper, I will be very grateful and will probably present it to future undergraduates and look very clever.

At this point, one says "Aha! The solution for nearly every problem in computer science and certainly in numerical analysis is to use Newton's method."

[Elliptic integrals are things] that some of you may have heard of, and if you have they probably haunt your nightmares.

Part of the purpose of this course is to persuade you that there are dragons wandering around in the world of algorithms.

... the more conferences you can go to saying "I've proved this or that tenny result, separating these two classes a little bit more."

You've got an oracle that can answer any question you ask it, provided the answer is one bit, and you don't even have to tell it the question in advance.

There are various things you could be doing. One of them is trying to find the biggest value at the roots, or the crock of gold here.

We consider the obvious possibility of a trained monkey as an opponent. Well, actually an untrained monkey.

Arthur plays chess against Merlin and Merlin, being a wizard, makes utterly incomprehensible moves.

You, the Merlin, sit above there, waving your hands above the keyboard ...

It is important that at some point during your undergraduate career at Cambridge there is some mention of Fourier Transform and Fast Fourier Transform because how else can you get out into the world and claim that we have instilled a proper engineering ethos in you, as the British Computer Society wants.

Lots of people have distilled their brains into a small file of ingenuity, which turns into a paragraph in here.

Anything which has got a "log log n" factor multiplied into its cost has clearly got something rather peculiar going on.

This is talking about continuous mathematics which you may have learnt at some point but if you're sensible you will have forgotten.

This is where I have to say that there's a +1 in there, but who the heck cares?

It is useful to change the meaning of symbols as you go, so that locally n means what it should most naturally mean.

Any of you who thinks that this counts as a naive obvious algorithm which everyone should have thought of, well you've got a twisted mind. Congratulations.

The paper I'll be referring to dates all the way back to 1978 so it seems to be ancient history.

Any reasonable course on algorithms ought to have something which Dijkstra did or was in the thick of.

Until recently garbage collection was only used in languages which their proponents thought were the mainstream, but which everyone else thought was that silly language over there.

For me to walk around this department saying that ML is a niche language and one of those which requires garbage collection might be considered politically incorrect. However, I can't see any people in hedgehog jumpers around here.

How many people in this room either have now or have had in the future a computer with two processors in it?

This is one of the things which showed people that formal methods were useful for stuff people were interested in and not just for little examples which theorem provers used to show off.

This allows me to parade my usual parenthesis fetish.

You observe there's a terrible danger of dropping things at this stage.

You just missed spotting the green pen.

There isn't a risk of losing this green pen because whenever I change hands I shade it.

Older than the rest of you lot and therefore past its best-before date, whereas you, of course, are at your peaks.

We all know, of course, that dogs have several processors inside.

We all know that it works with the inside of the dog changing from white to grey to black and then black and white switching.

If anyone waves sufficiently I'll come and hit - no, I won't come and hit them with the stick, I'll bring them some more paper. [Pause] On second thoughts, it's a very nice stick.