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.