June 17, 2018 9:52 AM

Sometimes, Evolution Does What No Pivot Can

From an old New Yorker article about Spotify:

YouTube, which is by far the largest streaming-music site in the world (it wasn't designed that way--that's just what it became)...

Companies starting in one line of business and evolving into something else is nothing new. I mean, The Connecticut Leather Company became Coleco and made video game consoles. But there's something about software that make this sort of evolution seem so normal. We build a computer system to solve one problem and find that our users -- who have needs and desires that neither we nor they fully comprehend -- use it to solve a different problem. Interesting times. Don't hem yourself in, and don't hem your software in, or the people who use it.


Posted by Eugene Wallingford | Permalink | Categories: Computing, Software Development

June 16, 2018 3:58 PM

Computing Everywhere: The Traveling Salesman Problem and Paris Fashion Week

I just read Pops, Michael Chabon's recent book of essays on fatherhood. The first essay, which originally appeared as an article in GQ, includes this parenthetical about his tour of Paris fashion week with his son:

-- a special mapping algorithm seemed to have been employed to ensure that every show was held as far as possible from its predecessor and its successor on the schedule --

My first thought was to approach this problem greedily: Start with the first show, then select a second show that is as far away as possible, then select a third show that is as far away as possible from that one, and so on, until all of the shows had been scheduled. But then I figured that a schedule so generated might seem laborious to travel at first, when there are plenty of faraway shows to choose from, but it might eventually start to seem pretty reasonable as the only shows left to schedule are relatively close.

We can generate a more wholly sort of unsatisfactory schedule by maximizing the total travel time of the circuit. That's the Traveling Salesman Problem, inverted. Taking this approach, our algorithm is quite simple. We start with the usual nxn matrix d, where d[i,j] equals the distance between shows i and j. Then:

  1. Replace the distance between every two show locations d[i,j], with -(d[i,j]), its additive inverse.
  2. Call your favorite TSP solver with the new graph.

Easy! I leave implementation of the individual steps as an exercise for the reader.

(By the way, Chabon's article is a sweet story about an already appreciative dad coming to appreciate his son even better. If you like that sort of thing, give it a read.)


Posted by Eugene Wallingford | Permalink | Categories: Computing

June 14, 2018 8:39 AM

Making Exceptions

When I became head of my department, one of the things that became a near-daily part of my life was enforcing administrative rules and fielding requests for exceptions to those rules. I like writing code a lot more, but these decisions involve a surprising amount of judgment, which can make them occasionally interesting.

A couple of weeks ago, Matt Reed wrote about the challenge of making exceptions to administrative rules. He opens by pointing to someone else's tweet asserting that exceptions to rules will largely flow to a certain group of students: those who grow up believing they have a right to question the rules. Reed acknowledges that this is true but goes on to argue that, even so, exceptions are an essential part of a fair system. I agree with him that there is a lot going here.

One of the few administrative tasks about which I had well-formed ideas before I started as head was applying rules. I'm in the group of students that many people would think of as privileged enough to be comfortable asking for exceptions. But I was also raised as a rule follower and, as a result, almost never asked for exceptions. I went through school following the rules as they were given to me and finding ways to move forward when the rules slowed me down. Occasionally I would learn that a friend had asked for an exception on a lark and ended up with an easier path. At first, I usually felt foolish for not asking myself; later, I would feel bad about myself for being a patsy, or cynical toward the system.

So, when I became an administrator, I wanted to be careful to apply the rules fairly, as they were intended, and not make exceptions just because someone asked for an out. It's tempting to help out a student when he or she asks for a break, but what about those students who didn't ask -- because they didn't know they could, or because they were afraid, or because they assumed the request would be denied? Things get hard sometimes when a faculty member presses for an exception to help a student they like or want to help. The faculty member will often say, "Well, the student wouldn't ask for this, so let's help them out anyway." But my thoughts stay with the students who won't ask and don't have an advocate. What about them?

If we start getting a lot of requests from faculty and students for an exception to a specific rule, I figure it's time for us to consider changing the rule.

However, as Reed argues, with any non-trivial rule, there really are exceptions to the spirit of the rule that we need to take into account. In his words, we need to exercise a little "epistemological humility". Even wise and experienced faculty members can't envision all possible circumstances that may arise when they write a rule. It's even harder to anticipate how a policy will interact with the myriad other policies enacted in the department or by other departments on campus. When those unexpected circumstances or interactions arise, we have to make exceptions if we really want to be fair. This means exercising judgment.

In my time as head, I have worked hard to walk the fine line between enforcing the rule as intended and making exceptions when exceptional circumstances arise. The challenge comes in dealing with groups of people at either end of a spectrum:

  • Some faculty want to make exceptions all the time. "It's just a rule," they say. "Why make someone suffer?"
  • Some faculty never want to make exceptions. They fear that our (or their) judgment will be called into question, and it's simpler -- and safer -- to never go out on a limb.

I learned early on that I was not omniscient and that the only way to be fair to students and faculty is to make exceptions. But I prefer to exercise judgment carefully. In order to do that, I ask for well-considered justifications.

To be honest, the justifications on most of the student requests I receive boil down to "because I want you to" or "because it would help me". If we enforce a prerequisite, it will push back a student's graduation date. (Sadly, failing a course has consequences...) If we enforce a distribution requirement, the student will have to take a course they don't like, or take a course from a professor they don't like.

In most of these cases, I sympathize with the student's plight, but that doesn't mean I can grant an exception. I try to probe for more details to see if there are grounds for further consideration, but most often I simply have to be the bearer of bad news.

(I've been talking about student requests a lot here, but my years as department head have taught me that faculty are not all that different. Some never ask for exceptions to rules that apply to them, while others ask freely. A surprising number of the requests also boil down to "because I want you to".)

With some effort, it is possible to walk the fine line. As Reed says:

The folks of whom exceptions are being asked need to be able to explain why they said "yes" to student A and "no" to student B. Ideally, they should know not only the rules, but the reasons behind the rules. That's a tall order, but in many cases, it can be done.

My general practice works something like this: Require that each request for an exception come with an actual justification that explains the exceptional circumstance. If the given justification is weak but I think there may be something worth considering, I work with the student (or faculty member) to elicit the deeper rationale behind the request. If the ultimate justification is solid, then I consider making an exception, sometimes in consultation with the faculty. Absent a solid justification, I enforce the rule. In those cases, I try to help the requestors understand why and, if possible, try to help them find other ways to handle the challenge facing them.

In my dozen or so years as head, I've surely made a few mis-steps, granting a request or two that should have been denied and denying a request or two that probably should have been approved. But I've worked hard to make good decisions, to recognize those cases in which I needed to update my thinking, and to recommend that we change rules when they no longer serve the purpose we intended. As with so many other tasks that we teachers and department heads perform, a little epistemological humility comes in awfully handy. Mistakes and struggles remind us to stay humble.


Posted by Eugene Wallingford | Permalink | Categories: Managing and Leading

June 03, 2018 10:50 AM

Two Thoughts on Teaching

... from my morning reading.

First, a sentence from Bryan Caplan, about one of his influences, philosopher Michael Huemer:

I think what's great about this book, and really all of Mike's work, is he always tries to start off with premises that make sense to people who don't already agree, and then try to get somewhere.

I value people who take the time to construct arguments in this way. It's surprisingly rare in academic discourse and public discourse. Teachers usually learn pretty quickly, though, that the most effective way to teach is start where your students are: recognize the state of their knowledge and respect their current beliefs. I try to remind myself of this principle regularly during a course, or I'm likely to go off track.

Second, the closing exchange from a 1987 interview with Stanley Kubrick. Kubrick has been talking about how the critics' views of his films tend to evolve over time. The interviewer wrapped up the conversation with:

Well, you don't make it easy on viewers or critics. You create strong feelings, but you won't give us any easy answers.
That's because I don't have any easy answers.

That seems like a pretty good aspiration to have for teaching, that people can say it creates strong feelings but doesn't give any easy answers. Much of teaching is simpler than this, of course, especially in a field such as computer science. A closure is something that we can understand as it is, as is, say, an algorithm for parsing a stream of tokens. But after you learn a few concepts and start trying to build or understand a complex system, easy answers are much harder to come by. Even so, I do hope that students leave my courses with strong feelings about their craft. Those feelings may not match my own, and they'll surely still be evolving, but they will be a product of the student engaging with some big ideas and trying them out on challenging problems.

Maybe if I keep reading interested articles on the exercise the bike and making connections to my craft, I can get this computer science thing down better.


Posted by Eugene Wallingford | Permalink | Categories: General, Teaching and Learning

June 01, 2018 3:05 PM

Prepare to Appreciate the Solution

This post isn't really about chess, though it might seem at first to be.

In The Reviled Art, chess grandmaster Stuart Rachels says that most grandmasters don't like composed chess problems because they are too difficult. It's easy to imagine why average chessplayers find problems too difficult: they aren't all that great chess. But why grandmasters? Rachels contends that problems are hard for tournament players because they are counterintuitive: the solutions contradict the intuitions developed by players whose chess skill is developed and sharpened over the board.

Rachels then says:

Most problems stump me too, so I conceive of the time I spend looking at them as time spent preparing to appreciate their solutions -- not as time spent trying to solve them.

I love this attitude. If I view time spent banging my head against a puzzle or a hard problem as "trying to solve the problem", then not solving the problem might feel like failure. If I view that time as "preparing to appreciate the solution", then I can feel as if my time was well spent even if I don't solve it -- as long as I can appreciate the beauty or depth or originality of the solution.

This attitude is helpful outside of chess. Maybe I'm trying to solve a hard programming problem or trying to understand a challenging area of programming language theory that is new to me. I don't always solve the problem on my own or completely understand the new area without outside help or lots of time reading and thinking. But I often do appreciate the solution once I see it. All the time I spent working on the problem prepared me for that moment.

I often wish that more of my students would adopt Rachels's attitude. I frequently pose a problem for them to work on for a few minutes before we look at a solution, or several candidates, as a group. All too often some students look at the problem, think it's too difficult, and then just sit there waiting for me to show them the answer. This approach often results in them feeling two kinds of failure: they didn't solve the problem, and they don't even appreciate the solution when they see it. They haven't put in the work thinking about it that prepares their minds to really get the solution. Maybe I can do more to help students realize that the work is worth worth the effort even if they don't think they can solve the problem. Send me your suggestions!

Rachels's point about the counterintuitiveness of composed chess problems indicates another way in which trying to solve unorthodox problems can be worthwhile. Sometimes our intuitions let us down because they are too narrow, or even wrong. Trying to solve an unorthodox problem can help us broaden our thinking. My experience with chess compositions is that most of the ideas I need to solve them will not be helpful in over-the-board play; those kinds of positions simply don't occur in real games. But a few themes do apply, and practicing with them helps me learn how to play better in game situations. If nothing else, working on unorthodox problems reminds me to look outside the constraints of my intuitions sometimes when a problem in real life seems too hard.


Posted by Eugene Wallingford | Permalink | Categories: General, Teaching and Learning