## Theory is practical in practice

Regarding DOF’s recent post Theory is Practical, I had a real life example of this today. This week’s problem set in my class was about graphs, and one of the problems reads

Whenever groups of pigeons gather, they instinctively establish a pecking order. For any pair of pigeons, one pigeon always pecks the other, driving it away from food or potential mates. The same pair of pigeons will always choose the same pecking order, even after years of separation, no matter what other pigeons are around. Surprisingly, the overall pecking order in a set of pigeons can contain cycles – for example, pigeon A pecks pigeon B, which pecks pigeon C, which pecks pigeon A. If A pecks B, we say that A is dominant and B is submissive.

(a) Prove that any set of pigeons can be listed in some order so that every pigeon pecks the following pigeon.

(b) Prove that any set of n pigeons can be listed in some order so that the number of pairs of pigeons where the dominant pigeon appears before the submissive pigeon is at least [some expression]

The concreteness of this problem was designed to help the students understand not only cases where graphs can be applied, but to make the problem easier to understand. I certainly thought that it would have this effect when I read it, and it seems much less intimidating than “Prove that every orientation of a complete graph has a Hamiltonian path,” which is what the question is “really” asking. My office hours indicated that it did not succeed in these goals. This was the question I got asked about *much more* than any other question, and most students seemed really confused by what the pigeons had to do with the problem, or even what the problem was asking. It’s interesting to me the amount of confusion which this caused. The students are still struggling with the basic concepts of graphs, so they had a lot of trouble thinking of the “right” way to abstract the problem, and then on top of that prove things about it.

I’m not sure what the best solution is for all this. Throughout much of the course, I’ve heard about how the material seems irrelevant to computer programming, and that the material is too abstract. Should we ignore complaints about the material, and give the students a heavy dose of abstraction, give the applications after students have done the homework (which might lead to frustration when students don’t know what theorems are “for”), or perhaps keep using problems like this. I don’t know, but it’s certainly interesting to think about.

(This is not to harp on the author of the question, who is a very good teacher. I think these issues are difficult, and there is no right answer. I just found the students’ response interesting and noteworthy.)

While not particularly useful for teaching purposes, this is highly utilitarian in real life endeavors:

If the facts don’t fit the theory, change the facts. — Albert Einstein

I’m going to admit to a mental failing here. I never had any trouble with math. I’ve always had trouble with graphs, I don’t know how they help or what they are intended to do. Particularly pie charts. I suppose its not that I lack the mental wherewithal to learn about graphs, it’s more that my brain refused to deal with them until somebody told me why I should. Nobody ever did. Aren’t they just a different way to describe something one has already described? If one hasn’t already described the thing with symbols, numbers, words, and letters, how can one make a graph anyway? And if the underlying work has been done, why do the graph?

The purpose as I understand it is to represent data in a way that people with different learning styles can understand. Some people need a visual representation, some dont.

Lucas: so in your problem above, there is no dominant pigeon? Each dominates one and so each would be considered equal?

Gerry: I think that graphics are frequently much more useful than tables, especially when there are a lot of data points. An average physics paper, for example, might have between hundreds and trillions of data points (depending on the area), and giving a table would just be impractical. Of course they are frequently misleading, but so is the written word, and so are tables. These are the kind of graphs that my students are studying, though. They’re studying something more like “dots with some lines between them. (In the spirit of this post, there are “vertices”, and edges joining them.) Think of power lines as “edges” and power plants and houses as “vertices”, and you’ll start to get the idea. There’s a nice picture in the wikipedia article I linked to that will probably make the idea clearer, as well as links in the unlikely instance that you’re interested in learning more about graphs. They have a huge number of applications to computers and communications industries, for example in sorting and searching algorithms, compiler optimization, and package routing (either at FedEx or Cisco systems).

Webs05: There may or there may not be a pigeon who is dominant over all other pigeons. The idea is that every pair of pigeons had a contest at one point, and they remember the result of that contest (even if the one who lost went all karate-kid and could now pick the shit out of the winner). I probably would have chosen sports teams (or maybe chess tournaments) if I was looking for concrete representation of what the question was asking, though I’m not sure how much it helped. Most students seemed more confused by what these pigeons were all about than what the question was (mostly) testing.