When I cover directed acyclic graphs for my algorithms classes, I usually mention as an example (familiar to the students) a DAG with university courses as its vertices and with prerequisites as its edges.

Today I learned that this is a lie, or maybe I should say more of a lie than I already thought it was. It turns out that, in our course catalog, prerequisites are not just lists of courses that all must be taken first. Instead, even if we ignore the grade thresholds in some of them, they are complicated and-or formulas describing the combinations of courses that are allowed to be used as preparation. Some of them are written in conjunctive normal form (ors of ands), some are in disjunctive normal form (ands of ors), and at least one (our information retrieval course) requires multiple levels of parentheses in its formula.

I had thought that this was mostly because some courses that have different numbers really have the same content, and should be treated as equivalent for the purposes of the prerequisite ordering. In order-theoretic terms, that would mean that we have a quasi-order rather than a partial order. For instance, we went through a refactoring of our curriculum a few years back and our prerequisite listings still include the numbers for both our old sophomore data structures course and our new one. But that's just to avoid blocking the leftover students who took it before we changed; you wouldn't want to take both classes. Or, we have three different ways you can learn linear algebra: by doing lots of hand calculations (the way the engineers want), by learning about vector spaces as abstract coordinate-free things (the way the mathematicians want), or by interacting with MATLAB or the equivalent (the way the computer scientists, and especially the machine learning people want). But you would only take one of these, not all three. So my feeling was that, at least when you restricted the set of classes to the ones taken by any individual student, you would get a partial order.

But even that is not true. Take a look early in the linked catalog page, at our course CS 113, computer game development. Its prerequisites are one of computer graphics, AI, software design, critical analysis of games, graph algorithms, or game design. Why that list? I don't know, it's not my course. But it's completely reasonable to take more than one of these courses, in various different orderings, and the fact that it's an "or" of these courses rather than an "and" means that we're not treating this list the way we would for topological ordering of DAGs.

So, if not a DAG, what is the prerequisite structure? An antimatroid! Or almost. Once you've fulfilled the prerequisites for a course, you can take the course in any later term that it's offered — they don't go stale. More abstractly, an element, once available to be included in an ordering, remains available until it is used. And this is the defining property of an antimatroid. The "almost" is because there are also some constraints that you can't take both of some pairs of classes for credit, but this only applies if you look at the whole course catalog at once. If you look at what any individual student takes, I think it really is an antimatroid. Of course, I may not have examined the catalog closely enough to find the exceptions...

(G+)