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.

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.

Reread Chapter 13 (2nd time)

Even with some understanding of Chapter 12.  The chapter on red-black tree is still quite daunting read.  The operations of insert and delete require consideration of several cases.   So it would take some time to think them through.

So, let's say I am still in the process of digesting chapter 13.   When I read it the second time, this will be a part which I spent a lot of time to drill.   Simply because every balance binary tree ideas would be at least as complicated as this one.

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.