Author: jeff

I finished Part I a while ago (yay!) and am currently in week 2 of Part II.

Tangential thoughts: a particularly challenging aspect of studying algorithms is proof of solvability and correctness. How can you tell if a computation is possible to solve at all? If you devise a new method for computing something, how do you know that it really works in every case? Mathematical reasoning can allow you to definitively prove that something does what you intended it to do. This is especially important when empirical verification makes it difficult or even impossible to cover all possible cases.

Sedgewick usually glosses the proofs in his lectures, since they’re not the core focus of the course. Some of these proofs are pretty hard to grasp even at a general level of description.

This aspect of algorithms dovetails with my excursion into functional programming in that both are deeply mathematical. They both indicate a view of computing as a branch of formal mathematics. Edsger Dijkstra was a strong proponent of this approach to computer science. I don’t claim to understand what this means in a very deep way, but I found the following example in Dijkstra’s essay, “On the Cruelty of Really Teaching Computer Science”, extremely helpful in starting to grasp this principle:

Consider the plane figure Q, defined as the 8 by 8 square from which, at two opposite corners, two 1 by 1 squares have been removed. The area of Q is 62, which equals the combined area of 31 dominos of 1 by 2. The theorem is that the figure Q cannot be covered by 31 such dominos.

Another way of stating the theorem is that if you start with squared paper and begin covering this by placing each next domino on two new adjacent squares, no placement of 31 dominos will yield the figure Q.

So, a possible way of proving the theorem is by generating all possible placements of dominos and verifying for each placement that it does not yield the figure Q: a tremendously laborious job.

The simple argument, however, is as follows. Color the squares of the squared paper as on a chess board. Each domino, covering two adjacent squares, covers 1 white and 1 black square, and, hence, each placement covers as many white squares as it covers black squares. In the figure Q, however, the number of white squares and the number of black squares differ by 2—opposite corners lying on the same diagonal—and, hence, no placement of dominos yields figure Q.

Not only is the above simple argument many orders of magnitude shorter than the exhaustive investigation of the possible placements of 31 dominos, it is also essentially more powerful for it covers the generalization of Q by replacing the original 8 by 8 square with any rectangle with sides of even length. The number of such rectangles being infinite, the former method of exhaustive exploration is essentially inadequate for proving our generalized theorem.

And this concludes my example. It has been presented because it illustrates, in a nutshell, the power of down-to-earth mathematics; needless to say, refusal to exploit this power of down-to-earth mathematics amounts to intellectual and technological suicide. The moral of the story is: deal with all elements of a set by ignoring them and working with the set’s definition.

The bombshell here is that learning to code shouldn’t be treated as a matter of what he calls its “operational semantics.” It’s a mistake to focus on what code does or how it behaves in its execution. Instead, you should think about code as a purely formal system:

… A programming language, with its formal syntax and with the proof rules that define its semantics, is a formal system for which program execution provides only a model. It is well-known that formal systems should be dealt with in their own right and not in terms of a specific model. And, again, the corollary is that we should reason about programs without even mentioning their possible “behaviors.”

This isn’t academic. When people often talk about the ability to “reason about code,” I think this is what they’re talking about. It’s a skill that can be hard to pin down exactly, but you can recognize it right away in the programmers who have it. They can well envision the challenges in designing a piece of software without being at a computer or writing any code; they can predict the consequences that a given change has for complex systems; and they can often effectively troubleshoot bugs by asking the right questions rather than rooting around in code. This is the holy grail of programming.

Needless to say, it’s a life-long pursuit.