Continued Fractions

Jeff Mermin focused on elementary properties of: how they provide "best" rational approximations to real numbers, distinguish quadratic irrationals, and are closely related to the Euclidean algorithm. A series of diversions led to coverage of the definition of limits, the definition of real and p-adic numbers, and infinite cardinals.

Cryptology

Jason Martin began with basic substitution ciphers, then moved to poly-alphabetic substitution ciphers. From there the group investigated linear feedback shift registers, stream ciphers, and finally block ciphers.

Probability Theory

Deena Schmidt focused on applications ranging from gambling to genetics. Topics included the Monte Hall problem, birthday pairings, counting principles, conditional probability and independence, Bayes Rule, random variables and their distributions, Gambler's Ruin problem, random walks, and Markov chains. Concepts were introduced with lots of examples, and students worked though challenging problems in class.

Student Projects

With help from the organizers, students concluded the year by researching and presenting topics of their choice. Some of the projects included differential cryptanalysis, the ENIGMA machine, group theory, the P vs. NP problem, and an extension of continued fractions to provide better approximations. At least one student independently produced existing results. Two students wrote a computer program to play poker that was entirely original and quite impressive.

Game Theory

Sharad Goel's module focused on developing some basic theoretical techniques in game theory and applying those tools to analyze a number of concrete games. After discussing solution concepts such as pure and mixed Nash equilibria and dominated actions, the class studied a number of real life situations that could be modeled as games, including auctions and elections.

Combinatorics

Jay Henniger's module focused on various problems in with an emphasis on developing student ability in forming logical arguments and writing proofs. Participants studied perfect covers of chessboards, magic squares and magic cubes, binomial coefficients, chains and clutters. Students often worked together in small groups and frequently considered multiple methods for solving a given problem.

Topology of Graphs and Surfaces

In Jim Belk's module, students worked in groups to explore such concepts as isomorphism of graphs, embeddings of graphs on surfaces, homeomorphisms, cell divisions of surfaces and Euler characteristic. This culminated in a discussion of Conway's ZIP proof for the classification of surfaces.

Random Walks, Markov Chains and Electric Networks

Todd Kemp's module focused on random walks, graphs and electric network theory. Topics included discrete harmonic functions, Kirkhoff's laws, the interplay between electric networks and random walks, Polya’s results on recurrence or transience of random walks on integer lattices, and random walks on trees.

Cryptology

Jeffrey Mermin gave a six-week overview of cryptology. Topics included substitution ciphers, detailed analysis of the Vigenere cipher, shift registers, a brief description of DES, and several public-key protocols, including RSA and Diffie-Hellman. Also discussed were complexity analysis of encryption and decryption algorithms, and the difference between known plain- and known cipher-text attacks throughout.

Graph Theory

Kristin Camenga’s module included such topics as Eulerian circuits and Hamiltonian cycles, edge and vertex coloring, graph Ramsey theory, and algorithms for shortest paths and minimum spanning trees.