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²⁰⁰ 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