Planarity, Kuratowski's theorem, Euler's formula
Paths in graphs. Bridges of Konigsberg (Euler paths and circuits), Round the World (Hamilton paths and circuits).
Graph coloring, chromatic number, four color theorem
Graphs. Edges, vertices, degrees
Examples of big graphs: the web, Erdos numbers. Connectedness, average degree of a vertex, components
Erdos references
Standard graphs. Complete graph - simplices in R^n
The cubic graph, cubes in R^n, labelling vertices with bitstrings
Redid the proof that equivalence relations and partitions were essentially the same thing, and then showed that surjections were essentially the same thing too.
Started thinking about graphs.
Partitions - examples, and a formal definition. Bell numbers count them.
Equivalence relations - defined "reflexive", "symmetric", "transitive" and then defined "relation" - a set of ordered pairs of elements from some universe U - that is, asubset of UxU.
I ended the class showing that partitions and equivalence relations are essentially the same thing, described differently.
This is all standard discrete mathematics. You can find definitions and examples in Bender and Williamson and all over the net. Google "equivalence relation" and "partition", find sites that explain things in a way you're comfortable with.
Counting to infinity. Started with Hilbert's Hotel as a concrete example introducing the idea of a a one to one correspondence as a way to "count" without numbers - that is, a way to say that two sets are "the same size".
Treated the same idea more formally, with bijections, a definition of infinite, \Aleph_0 and countability. Showed that 2^{\Aleph_0) is a larger infinity than \Aleph_0 - i.e. it's uncountable. Discussed Cantor's diagonalization method in several examples, related back to Hilbert's Hotel (committees of mathematicians) and connected this kind of argument to the halting problem.
As usual, you can find all of this material on the web with sensible search terms.
Digital signatures (briefly)
Starting on sets, relations, functions, ... You can read about this stuff in Bender and Williamson
After a very brief introduction of the private key system
encrypt(M) = C = M + k (mod n) decrypt(C) = M = C - k (mod n)I proceeded immediately to the RSA private key system. Alice finds two large primes p and q and chooses an e relatively prime to n = (p-1)(q-1). She publishes n and e. If Bob wants to send Alice a secret message M he encrypts with
encrypt(M) = C = M^e (mod n)In the meanwhile, Alice has calculated the multiplicative inverse d of e mod (p-1)(q-1), which she can do with the Euclidean algorithm but no one else can do quickly without factoring n. Then
decrypt(C) = M = C^d (mod n)Proving that decryption works depends on Fermat's Little Theorem and on a special case of the Chinese Remainder Theorem that I glossed over in class.
I followed the discussion in Rosen's text. You can read about this algorithm in many places on the web.
We did a few examples that suggested that when p is prime and 1 < a < p
a^(p-1) == 1 (mod p)(I write == for the triple equal sign for congruence since it's quicker that way in html).
That's in fact true. I showed two proofs available on the Fermat's Little Theorem wikipedia page.