At Proof School, communication is a core focus across the curriculum. That includes courses in mathematics.

"Graph Algorithms" is the most advanced math class offered at Proof School this block; the level is roughly on par with an undergraduate class for sophomore math majors. As with other Block 1 courses, the main focus of the class is on the process of doing mathematics, with an emphasis on creative problem-solving and rigorous proof.



For those not familiar with the field of graph algorithms, here is a quick introduction. In mathematics, a graph is a set of points (called nodes), some of which are connected by lines (called edges). Graphs are used to model many real-word situations: cities connected by roads, computers on the Internet, positions in a game connected by legal moves, or a social network of people connected by friendships.

An algorithm is a set of precise instructions for solving a computational problem. Graph theory abounds in such problems: for instance, given a graph, how can you tell how many connected pieces it has? How can you tell if it has cycles? Often, the edges of a graph will have numbers associated to them--corresponding, e.g, to the length of a road or the maximal capacity of a pipe. This leads to further questions, such as: how do you find the shortest path between two nodes? How do you select a subset of edges of minimal total length that will allow you to get from any node to any other? What is the maximal possible flow through a network of pipes with specified capacities?

Solving problems like these is not just a matter of programming a computer to search through all the possibilities. Even for relatively small graphs, the number of cases to check grows exponentially and soon becomes too large for even the most powerful computer to handle. The field of graph algorithms uses our theoretical understanding of graph theory and data structures to come up with clever methods for solving such problems. Often, the algorithms themselves are deceptively simple; the interesting part is understanding why they produce the correct answer and proving that they are guaranteed to do so.



Like all math classes at Proof School, our class meets for about two hours a day, with a break in the middle. Students spend much of their class time working on problems in teams of two or three. Since this is the most advanced class in the school, the students' level of mathematical sophistication is quite high, so I do not shy away from giving them serious "problems" rather than "exercises" to think about. The students know that getting stuck is a normal part of the process; I am always available to provide hints, but often the students will refuse my help because they want to figure out the solution for themselves.

Once everyone has gone through all the problems, the teams present their arguments to each other. At this point, they often discover that a proof which seemed clear in their minds can be quite hard to explain in an organized and coherent fashion--and might even turn out to be wrong. Listening to their peers' presentations, students learn to be on the lookout for subtle gaps in reasoning that can completely invalidate an otherwise correct argument. If a gap is found, the class works together to fix it. It is wonderful to see the students' sense of collective accomplishment when they manage to fix the flaw in a particularly thorny proof!

In addition to oral presentation skills, students also get a chance to practice their mathematical writing. Each student is responsible for a careful write-up of the solution to one or two problems each week. Some of the students already know LaTeX (the typesetting program used by professional mathematicians); others are learning it on the fly. By the end of Block 1, our class will have produced a mini-textbook on graph algorithms: the material in my handouts and problem sets will be supplemented by solutions written by the students themselves.

The sequence of increasingly precise formulation of ideas that I ask my students to follow--from brainstorming to discussing to explaining to writing--is a progression that every mathematician will recognize. But, of course, it is not limited to mathematics. The ability to develop an idea from a vague intuition into a fully fleshed-out, persuasive argument is vital for every human endeavor. My goal in all my classes is not just to teach the students mathematics (though I certainly want them to learn a lot of math!), but to use mathematics to teach them how to think better--more powerfully, more precisely, and more creatively.

For their final project in my class, students will have a choice of a more "math-y" or a more "CS-y" project. They can choose to learn an algorithm not covered in class by reading the original paper where this algorithm was introduced. (Fortunately, we are dealing with one of the rare areas of math where research papers are relatively accessible to beginners.) Or they can focus on implementing one of the algorithms that they've learned in class, paying careful attention to issues of running time and appropriate data structures. I am really looking forward to working with the students on these projects: I am sure I will learn a lot from them as well!

-Mira Bernstein