Status 20110923(a)

Finished in my head : 7.2-4, 7.2-5, 7.4-2, 8.2-1, 8.3-1, 8.3-4, 18.1-1, 18.1-2, 18.2-1

Browse reading: 813/1144

Exercises up to 4-4.5

Revisit : 4.2-{3-5}, 4-4.3 after section 4.5

Checking up to P2.1

Needs write up: 2-3.7 (nice solution using merging), P2.1c, 3-2.4, 3-2.8, P3.1

Exercises checked: 2.1-2, 2.1-3, 2.2-{1,4}, 2.3-{3,7}

Exercises which are finished but not on paper: 1.1-2, 1.2-2, 1.2-3, P1-1, The whole Section 4.4 except 4.4-3, 4.5-{1,3}, P4.4(a-c), P4.6b, 5.1-{1,2}, whole Section 6.1, 6.2-{1,2,4,5,6}, 6.3-1, whole Section 7.1, 7.2-{1-5}, whole Section 7.3 and 7.4.{2,3}, 8.2-1, 8.3-1, 8.3-4, , 10.1-{1-4,6,7}, 10.2-{1,2,6,7}, 12.1-{1,2,3,4} 12.2-{1,2,3,5,6},12.3-{2-4} 12.4-4, P12-1a, P12.4(a),13.2-2, 15-1.1, 15.1-3, 15.3-3, 15.5, 17-1.1, 18.1-1, 18.1-2, 18.2-1, 21-1.1, 21-1.2, 22-1.{1-3,6,7}, 23.1-1 and 23.1-3, P30-1{a,b}, P30-2b, 30-1.1, 31-1.{1-7}, 32.1-{1,2}, A.1-{1,2,3,4,5,7}, C.1-{2,4,5,7,8,9,14}, C.2-{1,2,4,5}, C.3-{1,2,10}, all in D.1. and D.2-2. 

Reread several chapters of sorting (Chapter 7, 8 and 9)

After learning quicksort again in the lecture, I decided to revisit the chapter on quicksort, radixsort and the median.  I have finished all the exercises of Chapter 2 so I am a little bit more confident with mergesort.   Of course,  it is unlikely for me to exhaust any of these topics because there are many tricks.   (That reminds me about my good old to-do list, I should bring it up again soon.)

Several things I learnt in this read - First of all, I think I finally grok why quicksort average case is nlogn.  The intuitive understanding using randomized version is simply to grasp.  The tougher part is the actual O derivation. In both cases, it's not impossible to understand: CLRS's version is actually purely probabilistic so it is easier to understand,  Sedgewick's version (7.2 of AIC) directly solve recursion.  I think it is cleaner.  Both require some understanding of harmonic sequence.  Oh well, who doesn't have it?

Another thing I grokked is how the algorithm of i-th order statistics works.  Arg, how difficult can that be?  If the pivot index equals to i, you get the answer already.   My question here is how to use red-black tree to come up with an answer like this as well. 

A more challenging part is probably how to really write these algorithms.   Now it's not a good time yet, but once I start the 2nd browse read.  I will do something. 

Status at 20110425(b)

Finished browse reading of Chapter 8.  As it turns out the concepts are not that difficult to grasp.   It's the analysis which is difficult to get it right.

When you talked with experienced programmer, they usually don't feel content if they only know the algorithm by heart.  They also want to know the complete analysis of the algorithm.

That makes me think: I should probably go back to work out the insertion sort (and selection sort) in the manner of Section 2.2.

33_P
Browse Read: 214/1144
Exercises up to Section 2.3-2
Exercises which are finished but not on paper: 2.3-7, 6.1-7, 6.2-3 and 6.2-4. 

Status at 20110422 (b)

I was able to break my reading block on heap sort.  Then I cruised through chapter 7 on quick sort and come to chapter 8.   I believe 6, 7, 8 are advanced topics which require good background in theory.  So reread is necessary.   There are topics which I feel blurry - that include priority queue and the analysis of quick sort.  Those are very important but not easy to fully understand.

I also reread the material about merge sort and Chapter 3 again.   Now I get them.  My mind just wasn't ready for them.  In fact, this is a very good book to own because once you finished Chapter 2 and drill it seriously.  You already know 4 basic comparison sorting algorithm by heart, one even has performance in theta(nlogn).

Browse Read: 200/1144
Exercises up to 2.2-3

33_P
(Correction: there are only 1144 pages in the 3rd edition.)