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 20110915(b)

Reread Chapter 12 and Chapter 13. Finished in my head : 12.2-5,12.3-{2-4}, P12-1a, 13.2-2

Browse reading: 813/1144

Exercises up to 4-4.5

Revisit : 4.2-{3-5}, 4-3.6, 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-3}, whole Section 7.3 and 7.4.3, 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, 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 Chapter 12 and 13 again

After rereading the chapter on binary search tree (Chapter 12), I think I finally grok deletion. In fact there are two non-trivial issues of binary search tree, one is to find a successor node when the right node is empty.  (In that case, you are always look for an ancestor whose left child is also an ancestor of the node.

The other is in deletion of a node with two child nodes, you always want to delete the tree-minimum of the right sub tree.  Once these two issues are thought through, you understand all operations of binary trees. (The others are more like simple recursive thinking).

Another good news is that I also reread red-black tree, this time, it starts to make sense on why we have this funny color fix-up algorithm.    The most important is to visualize the two different cases where the red-black properties should be handled.   I don't really grok at this point but I think I understand way more. It is super-complicated but it's also how the thing should work.   I stopped at deletion because it is even more complicated.

It's funny to see the whole business of building a balanced tree is so difficult.  This read is good.  I also finished in my head some exercises.

Lectures note for HW4

Hmm, here comes a tougher part,  issues such as binary tree, balanced trees such as 2-3 trees and B-tree are tougher to understand topic.   Ok, this is a good time to really understand them though.  It also related to my reading in CLRS Chapter 12 and Chapter 13.

status 20110708(c)

Put some deep thought on the exercises in Section 12.1 and 12.2, they are actually not as difficult as I thought.  I demand myself to figure out the "elegant" solution of 12.1-3. I found a good one but it's not necessarily elegant.  Another key question I solved is 12.2-6, it is key because it helps run to understand why TREE-SUCCESSOR works.

Also solved the trivial 12.1-1

Browse reading: 485/1144
Exercises up to 4-3.1

Revisit : 4.2-{3-5}

Checking up to P2.1

Needs write up: 2-3.7 (cute 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, 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,3,4} 12.2-{1,2,3,6}, 12.4-4, P12.4(a), 15-1.1, 15.1-3, 15.3-3, 15.5, 17-1.1, 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 Chapter 12.1

This time I grok more and in fact I even understand the proof of computation given my understanding of Chapter 4.  It seems like it is now a simple topic for me.

My recent stuckness.

For the first time, I have come to a point I feel stuck when I try to proceed in CLRS.   In my case, that means the three threads (browse read, exercise read and deep read) I have been working on are not moving.

Naturally, I am thinking about why.  For each read, there are different reasons and I also figure out their solutions. 

• For my browse read, my understanding of tree, or generally my understanding in discrete mathematics, need to be improved quickly.   Many of the questions require some intuitive understanding of trees.   I will not open the daunting Rosen's Discrete Mathematics and Its Applications.   Because I am fully aware of the damage of studying two text books at the same time.   I will feel too burn out and feeling not learning anything.  What I will do is to study Appendix B of CLRS and perhaps read the whole Chapter 2 of TAOCP.  Then reread, chapter 12 and 13. This should prepare me better on the next reread. 
• For my exercise read, as I mention before, I am beaten up by the exercises.   My solution is to go to sleep and take some mental break from Algorithms   In fact, I already line up couple of things to do while I am taking the mental break from algorithm.  That includes memorizing 80 Kanjis and also read El Alquimista in Spanish.   Both are within reach and fun to do. 
• For my deep read, I just need to work on it one item by item.  It is meant to be a deep connecting study to try to combine everything I know.   This is a phase which takes time.   I am just going to take my time and enjoy the process. 

And yes, enjoy!  Enjoy algorithms.  Indeed, there are many material reasons why I want to study programming.  But at the end of the day, it is fun!  It is also something which makes me tick the most in Computer Science.

Red-Black Tree

I have been thinking how come red-black tree's algorithm is so difficult for me to absorb.  Part of it is that RB tree by itself is not a perfect design (as mentioned by one of the original inventors, Sedgewick).  Part of it is that understanding RBT requires one to understand BST to a certain extent.   One will not understand how the deletion of RBT works if he doesn't understand how deletion of BST works.

In conclusion, let's reread Chapter 12.

CLRS Chapter 12 and Chapter 13.

Unlike the previous 3 chapters.  The material in Chapter 12 and Chapter 13 are more involved and require more thinking.  Those are also material I don't know much.  (Linked-list and hash I have at least solved some trick questions in the past.)

So I decided to read carefully even in the browse read mode.  I think that will pay off.