CS202/2004/Schedule/2004-09-22

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

More InductionProofs: strong induction. Sequences.
We also talked about the diagonal Ramsey numbers as an example of a sequence for which we have a definition but we don't know (and probably will never be able to find) all of its values. The sequence starts 1, 2, 6, 18, but subsequent numbers in the sequence are unknown. You don't need to know about Ramsey numbers for the course, but if you want to find out more about them a good starting point is here.

Readings: RosenBook Section 3.2.