The “Art” in “The Art of Computer Programming” (by Knuth)

I was recently talking to a professor, who wanted us to realize the term “Art” in the title of Knuth’s book series “The Art of Computer Programming”. Just for the record for myself, I wanted to cite, what I was refering to when I explained him the truehumorous origins of “Art”:

People frequently ask me why I picked such a title; and in fact some people apparently don’t believe that I really did so, since I’ve seen at least one bibliographic reference to some books called “The Act of Computer Programming.”.

In this talk I shall try to explain why I think “Art” is the appropriate word. I will discuss what it means for something to be an art, in contrast to being a science; I will try to examine whether arts are good things or bad things; and I will try to show that a proper viewpoint of the subject will help us all to improve the quality of what we are now doing.

One of the first times I was ever asked about the title of my books was in 1966, during the last previous ACM national meeting held in Southern California. This was before any of the books were published, and I recall having lunch with a friend at the convention hotel. He knew how conceited I was, already at that time, so he asked if I was going to call my books “An Introduction to Don Knuth.” I replied that, on tile contrary, I was naming the books after him. His name: Art Evans. (The Art of Computer Programming, in person.)

—via Preface of “Literate Programming” citing Knuth’s Turing Award speech in 1974

In the talk he went on with a long discussion about the relation of “science” and “art” in terms of computer science…

The “Art” in “The Art of Computer Programming” (by Knuth)

A matrix leadsto symbol

During my course “Numerical Computing and Linear Algebra” in the last semester I encountered a strange symbol the professor was using. You can watch the symbol in action in this board photo. Neither Detexify, symbols-a4.pdf nor other students in the NRLA newsgroup knew this symbol. So I had to create it myself…

My version is available as a demonstration snippet. It uses TeX kerning to put a \shortmid in front of the \leadsto symbol. Please be aware of the notes supplied below the snippet.

A matrix leadsto symbol

The pythonic difference of “notequal” and “not equal”

As Stephen A. Goss points out correctly, the statements not (x == y) and x != y are not equivalent. Thomas and Karl wanted to know why.

I was guessing that different special methods are called, but let’s start from the beginning. python has the basic concept that any operator corresponds to a special method. Special method names start with two underlines (in most cases) and can be implemented by any class. This is the pythonic way for operator overloading. Facing the question I tried to disassemble the python code:

>>> import dis
>>> def f(a): return a != 1
>>> def g(a): return not (a == 1)
>>> import dis
>>> dis.dis(f)
  1           0 LOAD_FAST                0 (a)
              3 LOAD_CONST               1 (1)
              6 COMPARE_OP               3 (!=)
              9 RETURN_VALUE        
>>> dis.dis(g)
  1           0 LOAD_FAST                0 (a)
              3 LOAD_CONST               1 (1)
              6 COMPARE_OP               2 (==)
              9 UNARY_NOT           
             10 RETURN_VALUE        

Okay, so when comparison is called, there are different parameters for the operator (please note that those parameters are not the values because python bytecode works stack-based and they got pushed before). A “3 (!=)” for a != 1 and a “2 (==)” for not (a == 1) followed by a UNARY_NOT. I really don’t know python bytecode by heart and therefore we had to look up the language reference.

The language reference explains all the python special methods in detail.

There are no implied relationships among the comparison operators. The truth of x==y does not imply that x!=y is false. Accordingly, when defining __eq__(), one should also define __ne__() so that the operators will behave as expected.

So the simple explanation is that obj != obj2 calls obj.__ne__(obj2) and not (obj == obj2) calls obj.__eq__(obj2) and afterwards the __nonzero__ special method of the result of __eq__. For me it is pretty straight forward, because for all builtin types those calls behave the way you expect it to do so and using different operators invokes different source code. However, I don’t think that calling __nonzero__ is more intuitive than a __not__ method (which is restricted to the operator module). See the snippet and Guido’s rationale for more information.

The pythonic difference of “notequal” and “not equal”

A complete, binary tree always has 2^n-1 vertices. Why -1?

Thinking about a problem, I came across the following basic graph-theoretical question:

Given is a complete, binary tree G(V, E). The cardinality of V always needs be constructed with

with n being an element of natural numbers excluding zero. Where does the minus 1 come from?

Graph Theorem
Examples for relation between number of vertices and 2^n-1

The solution lies in the logarithmically structure of the tree. The height of a complete, binary tree corresponds to

. Therefore firstly, the number of vertices can be described with

where d is the depth of the tree and

adds the additional 1. Secondly, if we look at the table with logarithmic values, we can see that 2 instead of 1 is the first parameter to return 1.

i log2(i)
1 0.0
2 1.0
3 1.58496250072
4 2.0
5 2.32192809489
6 2.58496250072
7 2.80735492206
8 3.0
9 3.16992500144

Thanks, credit goes to Felix for the clue 🙂

Note. This blog post uses MathML supported by any HTML5 web browser natively. WordPress obviously does not. It inserts stupid line breaks before <math>.

A complete, binary tree always has 2^n-1 vertices. Why -1?