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. 

Quicksort

Just went through the quicksort.  The description is again pretty superficial.   Can't blame the lecturer because quicksort by itself could be quite technical.

There are many variations of quicksort.  The Sedgewick's variation is probably the fastest.   We probably won't go through it. 

There are one good thing about the lecture.  It puts a lot of stress on the partition function.  So one thing I learnt, as it turns out the partition function actually doesn't always divide the array to halves. (!)  It's a very good thing to know.  

Time to implement quicksort once myself.  It's something quite tricky to implement.  Also want to take a look of the analysis of quicksort as well.  Why the average case is nlogn? 

Thinking about the second browse read of CLRS

As I am almost finished the first browse read and far from finishing the exercise read, it makes me think what is the best way to make use of the second read.

The truth is the linear style of the first browse read is not a very effective way to absorbe difficult topics such as red-black tree or dynamic programming.   Many selected topics by itself should also be read in a separate book so a linear-read is unlikely to give too much benefit.

Here are couple of thoughts at this point.  It requires a slight modification of the second browse read as well as the exercise read.

1, First of all, the browsing in the second read should be slower.   The general principle is that I need to understand more than the first read.

2, Second, instead of getting stuck in a particular chapter just like now, my exercise read should incorporate at least another N chapters in future read.   How should I choose the chapters? How large is N?  My answer is that if I can finish more than 50% (more or less) of the chapter exercises, then I should pick it as an exercise read.  Right now that means Chapter 6 (Heapsort), Chapter 7 (Quicksort) and Chapter 12 (Binary Search Tree).  My take is that N is likely equal to 1 or 2 because it's easy to get distracted.

3, I will also let problems I have been working on in work as well as in school to stimulate me.  If I need to review certain material.  I will not hesitate to reread a certain chapter of CLRS.  For example, I probably need to reread the Hash table (Chapter11) and sorting chapter soon.   They are beneficial for my learning in the class.  They will also be essential in my work life.

So let's see how it goes.   Of course, I probably want to start the second browse read first.  This will be quite something by its own.  The last three chapters are interesting and deep.

status 20110614(b)

Finished in my head: whole Section 7.1, 7.2-{1-3}, whole Section 7.3 and 7.4.3

Fuzzy reading: 414/1144
Browse reading: 309/1144
Exercises up to 4-1.3

Needs write up: P2.1c, 3-2.4, 3-2.8, P3.1

Exercises which are finished but not on paper: 1.1-2, 1.2-2, 1.2-3, P1-1, 4.1-5, 4.2-6, 4.2-7, 4.3-{1,2,4,5,6}, The whole Section 4.4, 4.5-1, 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-3}, whole Section 7.3 and 7.4.3, 10.1-6, 10.1-7, 12.1-{1,2,4} 12.2-{2.3}, 12.4-4, P12.4(a), 15-1.1, 15.1-3, 15.3-3, 15.5, 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

Quicksort

Every programmer knows that quicksort is the most prominent method in sorting.  Saving funny sorting scheme such as bubble or shell, quicksort is also very difficult to be analyzed.  So I decided to read through Chapter 7 of CLRS.   Quicksort would probably take me at least 100-200 practices to fully master because there are just too many possible variations.  Just the original Sedgewick's paper and survey paper would make at least 10 variations possible.

33_P

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.)