RSS

Tag Archives: knuth

The Art of Donald Knuth

The other day I had a few extra minutes before heading off for work so I decided to take a trip to my Engineering Library to check out a book I wanted to study over the summer. The book was called Pattern Recognition and Machine Learning, by Christopher Bishop. It’s preparation for a class I’m taking next semester called Advanced Probabilistic Modeling. Anyway, they didn’t have it. So instead I just figured I’d kill some time by checking out the usual sections of the library. I stumbled upon a book called the ACM Turing Award Lectures: The First Twenty Years: 1966-1985. Seemed interesting enough to pick up for a quick glance and I happened to check out Knuth’s Turing Award lecture. I really enjoyed reading the lecture and came across a lot of ideas that I’ve been trying to say before on this blog, although not nearly as eloquently as that of Knuth. To give a brief summary, the title of the lecture was Computer Programming as an Art, a theme that no doubt very closely resembles Knuth’s thoughts in writing his AoCP series. Anyway, I really should have read a lot of this before because I found it very inspiring. I’m going to just list a few nice quotations from the talk below:

Implicit in these remarks [that computer programming needs to made more into a science as opposed to an artistic, or imprecise, process] is the notion that there is something undesirable about an area of human activity that is classified as an “art”; it has to be a Science before it has any real stature. On the other hand, I have been working for more than 12 years on a series of books called “The Art of Computer Programming.” 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 bibliography reference to some books called “The Act of Computer Programming.

I thought this was quite interesting. It seems pretty clear to me that Knuth was a revolutionary in his thinking regarding programming, even when the notion of telling a computer a list of instructions to execute was something very new. I guess the process that the world took to master (if you can call it that now) the techniques of programming pretty nicely resembles, almost fractal-like, the process of learning of a single individual learning it for himself. That is, it starts by taking a bunch of seemingly random words, characters, numbers and putting them together in some haphazard fashion until the compiler stops yelling at you. Then the individual learns that in fact there is more rigor to the process than just throwing everything at the wall and seeing what sticks. There is the evolution of the learning process from chaos to some order; a science if you want to call it that. But that’s very much only the first stages. Because beyond the beginning stages, everyone pretty much gets how syntax works and where to put your semi-colons and whatnot. It’s the style which is where the fun really comes in. And you may be able to define how many spaces there are in a hard tab or where to put your braces in some document, but the approach by which one tackles a problem is much more innate. That’s how we have neat little algorithms to do our bidding instead of trying to crunch out everything the brute-force way each and every time. Herein lies the transformation from a rigorous science back into something of an art form. I would argue, therefore, that the art of computer programming is an evolution from the science of computer programming, not its predecessor. Expanding on this a bit further is another quote:

It seems to me that if the authors I studied were writing today, they would agree with the following characterization: Science is knowledge which we understand so well that we can teach it to a computer; and if we don’t fully understand something, it is an art to deal with it.

I kind of like this definition actually. It ties in with my previous post about potential functions and how there is an element of creativity necessary to actually do something of substantial value in this field (as with any!). But therein lies the fun of it. To put it shortly, there’s gotta be a reason we still have humans instead of computers writing computer programs. Related to this idea is the following quotation:

The field of “automatic programming” is one of the major areas of artificial intelligence today. Its proponents would love to be able to give a lecture entitled “Computer Programming as an Artifact” (meaning that programming has become merely a relic of bygone days), because their aim is to create machines that write programs better than we can, given only the problem specification. Personally I don’t think such a goal will ever be completely attained, but I do think that their research is extremely important, because everything we learn about programming helps us improve our own artistry.

I totally loved the above quote. I think it does a great job of highlighting exactly what this whole post, and probably this blog, is about. The point here is that reading this speech has provided me with quite a bit of more inspiration. There is something quite nice about reading these words.

Finally, in closing, here’s the quote that explains, in part, the inspiration for the title of this post:

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 the contrary, I was naming them after him. His name: Art Evans.

 
2 Comments

Posted by on May 25, 2011 in Uncategorized

 

Tags: , , , ,

Spring Semester Update

Today marks the beginning of Spring Break for us and the midway point of the semester as well. This is most definitely the hardest semester I’ve ever had so far and although it’s very stressful at times, I’m really enjoying it a lot. I guess in some ways this semester was a way for me to determine how much I actually loved computer science at the its core – to see how much I enjoyed it if I fully immersed myself in it. The results so far are better than what I had expected: Even though the great majority of the my homework and assignments are about computer science and even though I am studying or attending class on some CS subject nearly every single day, my interest in it has only increased. I feel very at home when learning about the theoretical aspects of computation and complexity, or knee-deep in the analysis of some algorithm. Even though the workload is just so very barely manageable, I’m glad I am taking what I decided to take and I’d like, to the extent possible, to complete all six courses I am enrolled in this semester. Six courses is a bit on the high side for an engineer here, but I guess it’s more about how interesting you find them. As I’ve said before, it only feels like work if you can actually distinguish it from play. In any case, most of the work that I have fits comfortably in the category of play, so it’s basically an excuse to do something I’d probably be doing – or wishing I could be doing – during that time anyway.

I had a few goals for the year. One to take at least one graduate class before the end of the year; to study lesser known data structures and algorithms; to learn at least one more popular language and one more obscure language; and to get an introduction on quantum computation. Of those, I am in the process of accomplishing the first few of them. Thanks to my class on approximation algorithms, which is both tough and very enjoyable, I am satisfying the first one. In my Theory of Algorithms course, we are covering quite a few different interesting data structures as well as algorithms. Although these are not exactly “lesser known” in the greater sense of computer science, they’re also not the ones you usually learn in an introductory course. Specifically, I was very happy to see that we covered Fibonacci heaps, rank-pairing heaps, AVL trees, and RAVL trees. These, especially the first, are among the more advanced data structures used for very large data sets in industry. If I recall correctly, I believe Google Maps uses some implementation of F-heaps in storing data. In general, self-adjusting data structures are extremely interesting and it’s so neat to get a pretty bound on their performance regardless of how convoluted the implementation and procedures may be. As far as the other goals, I’m making (slow) progress on picking up Python and we’re using C++ for our computer graphics course. And as far as lesser known languages, our compilers course is taught strictly in ML – a functional language. I am yet to fully wrap my head around those exotic things. More thought is necessary on that front.

Although I’m satisfied with the coverage of algorithms for trees and graphs so far, I’m now also interested in learning about probabilistic algorithms. I was turned in this direction after seeing the power of probabilistic rounding techniques in solving LP-relaxation problems for approximation algorithms for very common problems such as vertex cover. Although they may not always provide an optimal bound, they do sometimes make the code and analysis much simpler and offer better worst-case performance. And they are everywhere too. From the example I just mentioned to an implementation of MST in linear time (!) in the number of edges, randomized and probabilistic algorithms play a huge role. And looking at it from a more pure sense, it’s also particularly interesting to see how the nature of random numbers can reveal insight on the structure of computation. I’m starting to develop some ideas of my own; perhaps the better word for them would be “questions” or maybe just situations and combinations of known elements in a way I haven’t seen anywhere. Hopefully I will soon be able to gain the mathematical and analytical machinery to actually see if these ideas make any sense at all.

In other news, my copy of Knuth’s classic Art of Computer Programming Vol. 1-4A finally arrived this week! As you may know, the fourth volume was just released after something like 38 years. I’m very excited to check it out. It’s currently sitting, still shrink-wrapped, on the table beside me. During the next week I’ll see if I can make sense of it. On another note, I am very pleasantly surprised by the quality of CLRS, another very excellent algorithms book. The analysis is surprisingly clean and the writing is precise, which makes it a pleasure to read. And they tackle complicated concepts with ease, making it look like it takes hardly any effort, which is impressive. Over winter break, I had started on Michael Sipser’s Introduction to the Theory of Computation, another classic text. It turns out this gave me a very nice edge when we were covering DFA/NFAs, regular expressions, and context-free grammars in compilers. Although I had had an introduction to these concepts in a previous course, I accredit Sipser’s book for teaching them to me in a rigorous sense. Once again, I see the same ease with with Sipser explains these concepts and proofs and it’s quite impressive. It makes it as painless as possible to cover these proofs with sufficient depth. So I will have to continue on with that text, seeing as it coincides very closely with what I am interested in. And as for the last goal, it is yet unfulfilled. I need a whole lot more knowledge before I go near that subject. Perhaps next semester or next spring. There’s just so much learn.

 
Leave a comment

Posted by on March 12, 2011 in Uncategorized

 

Tags: , , , , , , , , , ,