TAOCP: Finished with 1.2 Mathematical Preliminaries

The final sections of 1.2 grow increasingly more complicated. Section 1.2.9 (Generating Numbers) was particularly nasty, and I got hardly anything out of it. Well, we can use it to find more information of some infinite series. Section 1.2.10 (Analysis of an Algorithm) begins gently, introducing a simple algorithm and demonstrating a flow chart for it. The end of that section was perhaps a little too much, however. Contradictory to my initial plan to skim the sections that are marked for mathematically inclined, I decided to read section 1.2.11.1 (the big-oh notation) as it is not a new concept for CS students and it's a very important concept when discussing algorithms. Sections 1.2.11.2 (Euler's summation formula) and 1.2.11.3 (Some asymptotic calculations) were skipped altogether.

So this brings section 1.2 to an end. I'm at page 124 and to my surprise I only had to skip a few pages from 1.2 Next becomes the MIX section that I have waited for.

TAOCP: (Harmonic+Fibonacci) Numbers

Section 1.2 is nearing its end as I just finished with 1.2.7 and 1.2.8 One could talk a lot of the Fibonacci series and of its relation to phi, but I'm sleepy and will just repeat a handy equation from the book that I didn't know: F_n = round(phi^n/sqrt(5), 0), where F_n is the nth fibonacci number and phi equals 0.5*(1+sqrt(5)), that is the golden ratio 1.618...

Learning Haskell

Uh, no taocp today because I got stuck in Haskell.Org's haskell-98 tutorial. Functional programming has been unknown to me. We don't have a Lisp-derived language as the first language in the univ. (it's the evil Java there!) so not until ~one year ago did I start to satisfy my curiosity and downloaded the legendary Lisp lecture videos from MIT servers. I wrote some basic algorithms in Common Lisp and liked it but I never had the motivation to watch the whole lecture series nor write anything real in Common Lisp.

Having recently become a regular reddit/programming reader I've seen a lot of Haskell related articles in the hot list. At the univ. I've seen a bit of Haskell fanaticism, and functional progr. fanaticism in general, going on, too. Because of that I decided to find out more about this language.

Right now, having read one-thirds of the tutorial, I can already say that I'm happy that I opened it. Never have I seen such a beautiful definition of quicksort before:

qsort [] = []
qsort (x:xs) = qsort [ y <- xs | y < x ]
             ++ x ++
             qsort [ y <- xs | y >= x ]

Yes, the pivot could be chosen more carefully as this can easily fall to O(n^2), but ignoring that, this is a marvelously lucid piece of code.

TAOCP: Slow progression

I've been busy in the past few days, and only tonight found time to proceed reading taocp. The section was 1.2.6 Binomial Coefficients. For the first time I found myself skipping some paragraphs that were full of equations. Much of the equations described how to play with Pascal's triangle, that indeed is a fascinating object.

How little streams of knowledge converge, generating joy

The rewarding moments of studying are those when we realize new applications for previously learned knowledge. Tonight I had to skip taocp and read the Dragon book (_the_ compilers book), because I'm attending a compilers course at the university. So the topic was syntax directed definitions and attribute grammars, and among other things, it discussed the evaluation order of node attributes of a syntax tree with attribute dependence edges already in place. It was immediately obvious that by topologically sorting the graph we can find a valid evaluation order.

In computer science studies, it's not always very clear what the real applications for the techniques presented are. This was one of the happy moments when previously learned knowledge came in to good use.

I remember my history studies in senior high, when it first felt difficult to understand some of the reasons behind historical facts. In the end, after all courses, the little streams of knowledge finally converged and started to explain each other. Understanding is vital in studying, because when you understand something, you don't have to be a good memorizer. It's enough to remember the main points actively, and then you can reconstruct the the rest by deduction.

My advice to fellow students is: don't think reading as memorizing, think it as understanding. This way you won't need to read anything twice.

TAOCP: Half way into mathematical preliminaries

I have now taken a custom of reading taocp right before going to bed. Tonight I read sections 1.2.3 (Sums and Products), 1.2.4 (Integer Functions and Elementary Number theory) and 1.2.5 (Permutations and Factorials). I've now read almost a half of section 1.2, and the text is getting denser. I'm definitely waiting for the maths section to be over and get to delve into the description of MIX which is the hypothetical computer used throughout the book series.

TAOCP: Induction and logarithms

Knuth suggests that it may be wise to skim through the mathematical sections from the beginning of the book when reading for the first time. I decided to read on and only start skimming when it becomes overly heavy. The sections about mathematical induction and logarithm were pretty basic stuff, not too hard to read, although many of the exercises were beyond my math scope.

In one exercise it was asked what is the value of log_pi (pi), that is, base pi logarithm of pi. We can immediately declare an answer following the definition of a logarithm, but because rational numbers act in an awkward manner as base, couldn't we just declare it undefined? The right answer given by Knuth is 1, of course.

Next time it is sums and products who will accompany me.

TAOCP: Foreword and 1.1. Algorithms

Here we go. In the foreword, I found it amusing that Knuth kindly informs that the reader should have written and tested three computer programs in order to have enough pre-knowledge for his book series. I think we can't count a "Hello, world" as one here. The statement is arbitrary of course.

Having read the reading instructions + the state machine I decided to keep picking the "yes" edge from the state "2+2=5" which leads to the "skim math" state, and concentrate on programming. I won't be missing the math though, it's prevalent all over.

The first actual section (1.1.) was written in a sound way. I'm not sure I fully understood the formal definition of a computational method, though. So I'm planning to re-read that part next time.

TAOCP is here

Great, the material is finally here, and it is now possible to start the mission I talked about in the first post of this blog. Ah, the sweet scent of a new book.

GPS - First notable mobile phone feature since sms

I finally bough a new mobile phone after four painful years with Sony Ericsson k700i. Now some of the Nokia N-series devices, such as my N82, have an integrated GPS module and a pretty good maps application. It immediately came handy when I was in a neighborhoods that was completely unknown to me. From the metro station I just walked to the address I was supposed to go following the moving cross on the mobile phone screen. I have been waiting for this feature for many, many years and now that I finally got it and it actually works, I'm very pleased. This is the first new mobile phone feature since sms messaging that has real value to me. Additionally, the camera is actually taking decent pictures. The camera in k700i was a useless toy.

Top C64 remixes

Having listened Slayradio in excessive amounts for a couple of years, some of the remixes have stood out, and here are my favorites in random order.

• Da Phuture Kemist - Tristesse
• DJ Skitz - Super Huey (Storm Mix)
• Infamous - Spy Vs Spy
  
• Peter W - Outrun (no speed limit remix)
• Thermostatic - Metal skin
• Machinae Supremacy - Sidology 2 Trinity
• Machinae Supremacy - Great Giana Sisters
  
• DJ Mitch - Cauldron (Hexenkche Walpurgisnacht HardTrance Mix)
  
• Chronberg - Gyroscope - Unzalicious version
• Makke - Glider Rider
• Dreamer - Turrican
• Obscuresounds - Arkanoid
• Binster - Ghouls And Ghosts Poltergeist Mix
  
• Dafunk - Hardcore Power (We Believe in Goa)
• Dafunk - Destruction - The New Beginning (rmx)
• weebl - Deltaplus
• Tonka - The Last Ninja - Palace Gardens Loader

Most of them are available from http://remix.kwed.org/

gltrail - realtime logfile visualization

At work I'm hacking on a software that manages a rather large number of servers over the internet. A month ago I was thinking that it'd be cool to be able to monitor the messages flow between the machines in realtime in some graphical format. I started to do it with Python and wx, but then my motivation went elsewhere and the project got stalled. Today I ended up at fudgie.org which introduces gltrail - a realtime logfile visualization tool, main purpose being Apache access.log monitoring. It's got a strikingly similar user interface that I had planned, although gltrail is way more cool than I could have come up with (just watch the video on the site). Fortunately the software is licensed under GPL so if I later have time and motivation I've got great help now. Thank s/god/rms/ for free software!

Computer Programming as an Art, 1974

While the books are being shipped I took the opportunity to read Knuth's 1974 ACM Turing Award paper titled the same as this blog entry. The paper was written a decade before I was born. Should anyone find this topic interesting, I recommend reading the paper. Below I try to summarize the main argument however.

It is explained in the paper that the term art used to mean "something devised by man's intellect, as opposed to activities derived from nature or instinct." Basically what we nowadays usually call science was previously considered art. Later the two terms began to have more independent meanings. Science was now considered to stand for knowledge and art for the application of knowledge.

Knuth's arrives in a conclusion that science is knowledge which we understand so well that we are able to teach it to a computer, while art is something which we don't fully understand. The story tells how programming has transformed from being pure intuitive art to more of a scientific matter. We have progressed in making software, being now capable to proof program correctness and do meaningful measurements of the software development process.

Knuth tell us that making software is, however, both science and art. He states that his viewpoint of programming as an art is an aesthetic one. The main goal of his work as educator is helping people learn how to write beautiful programs. The following quote from the paper may be worth mentioning.

"My feeling is that when we prepare a program, it can be like composing poetry or music; as Andrei Ershov has said, programming can give us both intellectual and emotional satisfaction, because it is a real achievement to master complexity and to establish a system of consistent rules."

The paper talks about a number of other issues as well, such as of the importance of great programming tools and languages, and different programming styles.

In the end it is claimed that a programmer who views himself as an artist will enjoy programming and also perform better. I've never though of it that way. For me it is clear that should you enjoy your work for whatever reason, that alone will enhance the quality of the work. I don't certainly feel being an artist when I'm coding, but I certainly enjoy being the creative force, a god-like transformer of pure, abstract ideas to machine readable instructions, and see the machine obeying my commands (though in the bad days the machine just can't understand me and keeps segfaulting).

Challenge

I really envy hard-working, enthusiast people who voluntarily get involved with massive projects in their free time in the subject they so love. I occasionally have some free time, too. My plan is to read through perhaps the most significant "introductory" text from our field. That is The Art of Computer Programming.

Everyone knows Donald E. Knuth's legendary TAOCP series but hardly anyone has read it. It contains the fundamental knowledge from our field - computer programming - in rigorous detail. TAOCP is still in progress, the first three volumes (Fundamental Algorithms, Seminumerical Algorithms, Sorting and Searching) are already available and have been for several decades. Volumes 4 to 7 are in progress. I hope aging Knuth will have enough time to finish the series.

I don't know if I can maintain motivation through the three available volumes but I certainly are going to try. The books are already on their way from an American net-store (dollar is cheap nowadays!). They've estimated to deliver the books in two weeks.

I plan to document my progress or lack of progress in this blog and comment the chapters as I go. I'm not going to set a strict schedule for myself because the amount of free-time is not a constant. I unfortunately cannot follow the reading instructions that Knuth generously offers in the first volume. However I try to keep reading a few pages regularly, because huge time gaps will definitely kill the project. And no, should I succeed I'm not planning to send a resume to Bill Gates (nor Paul Allen for that matter).