Partial Reread TAOCP Chapter 5

I was sick yesterday so I stopped any programming activities for a day.   Feeling refreshed now, I decided to delve into implementation of Shell sort and try to understand the goodies.  As a bonus, I also tried to read through multisets, runs, Young Tableux and involutions.   I am sure each of these topics would leave a mark in my mind in future because all of them are very closed to what I am interested most : number theory, group thory and combinatorial theory.   So I have tried to penetrate 5.1.{2,3,4} and 5.2.1.

All of them are deep stuffs.  I got to admit that in the chapter of multiset (5.1.2) and Young tableux (5.1.4), I had to skip some of the contents.  I might want to reread some preparatory material before I read it again (and I just simply believe that one day I will fully understand all the contents one day. Ha. :) ).

I also start to have some intuitive understanding why the increment problem in shell sort is such a difficult problem.  Once a problem can be related to number theory.  You know that it is one of those deceptively simple problem.  That is why most of the introductory book just simply skip this topic.  As far as I understand from Sedgewick paper, this problem is mostly being attacked by empirical method.

This makes me excited because this is the probably the first period of time which I realize my work can have well-defined open mathematical problem.   In the past, what I saw were mostly emprical problem on improving a system X.  Or to device a probabilistic method to improve System X.  Those are interesting problems and fun to work with at the start.  After a while,  without the guidance of theory, this kind of work will stale and deteoriate to only discussion on performance.  Boredom followed.  One might say theory is very hard to be applied in practice.  I tend to believe though that the focus of research could occasionally drift in a mindless manner.

I also thought about whether I should keep track of my progress on reading TAOCP.  Nah, after I while I think reading one single book is already too tough.  CLRS is substantially easier to start with than TAOCP.  Its exercises are also more guided but one should still start CLRS with probably graduate level of Math to fully appreciate the importance of some Theorems in the book.  So I guess if I can finish the 2nd read, I am an alright programmer.   Let's think about the next step at that point.

What I would do though is that from the point of implementing Shell sort, I will start to also write a driver for all the sorting algorithms.  This is the moment I want to quantitatively understand the characteristics of different sorting algorithms.  Different increments should be examined carefully.  It sounds like it will indeed take me some time to understand insertion sort.....

Speaking of which, it's time to get back to CLRS and do an exercise or two, or reread BST.   Small blocks but it's still take some cognitive load to get through.