Previous lecture | Table of contents | Next lecture |

I reviewed again how to compute squares of numbers, and discussed
Square Inquiry. I tried to do this very slowly but I do not think
enough people understood me: the difference between a number and the
size of the number is sufficiently strange to people. We eventually
saw that doubling the size of a 2,000 digit number caused time needed
for an elementary version of square inquiry to increase by a factor of
10^{200} or something like that. I did not think that people
in the room could appreciate large numbers sufficiently, so I then
tried to find the number of molecules of water in the Atlantic
Ocean. This was hard, and of course turned out to be a number far less
than what Square Inquiry would need. First I had to approximate
(overestimate) the volume of the Atlantic Ocean, and then I had to ask
people how many water molecules there were is a given volume of water
(and of course we digressed to talk about moles -- not the underground
mammals!)

A less fictitious example was factoring. I tried to discuss how long factoring would take and tried to indicate that a simple-minded approach would involve quantities which were much more like Square Inquiry rather than squaring.

I then discussed "P", polynomial time algorithms, and tried to indicate the idea of an oracle, an object which might give the answer, but whose answer could be checked in polynomial time. I very briefly discussed the P/NP controversy. I am sure that I did not adequately indicate that a P algorithm would need to be one for which there was polynomial time implementation possible. I also tried to tell the class about video games for which there was a "cheat" button, and made some analogy to oracles.

A homework assignment about algorithms was given out **[PDF|PS|TeX]**.

Previous lecture | Table of contents | Next lecture |