status 20111027

Change the browse read pointer back to Chapter 4. Change the exercise read to chapter 6. 

Browse reading: 65/1144

Exercises up to Chapter 6. (After Chapter 4 and 5 are skipped, not start the read yet)

Revisit : 4.2-{3-5}, 4-4.3 after section 4.5, revisit Chapter 4 and 5 when time allowed. 

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. 

Some thought on my exercise read.

I have thought about this for a while.   It is indeed quite difficult to get through the exercises of Chapter 4. This could simply be a matter that I don't fully grok some of the nuance of the subject.   Solving recursive relation is a deep subject.  I have improved on it but my mathematical skills is still not good enough.   That sets me to a position which I can't move on.

So I am thinking.  I might want to skip both Chapter 4 and 5.  They can be too mathematical (as well as tedious) for me at the moment.  I can work on Chapter 6 directly and try to think if I can finish some exercises in Chapter 4 and 5.   This will unstuck me and it's meaningless to get stuck for such a long time without moving along.  Insight such as grokking the solution of T(n) = 2*T(n/2) +n is useful enough to move on.

I am also working on my cloud blog all the time.  It's a lot of fun to write.  When I have chance I will also expand it to support more languages and more topics.   Should I do the same for "Self-Study"  I don't know.  After all, "Self-Study" is really just my diary.  Making it to attract readers is a bit far-reaching for me.

33_P

Status 20110919(a)

Put 4.3-6 on paper. Put the pointer back to 4-4.3 and work on it first. 

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

4.3-6

I ended up putting this on paper but my solution is merely copying the original author.  Things look much clearer after I followed the reasoning of the answerer.  I have seen other solutions though they usually hadn't considered the flooring operation correctly.

Of course, I will be challenged again in 4.4-3.

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.

Some thoughts on CLRS's treatment on recurrence relation

As you may observed, I have been stuck in Chapter 4 for quite a while.  Notably on Section 4.3 and 4.4.  There are exercises which I don't fully grok.  That obviously makes me think of why.  This usually gives me some insight.

When you take a look of teaching material on recurrence relations,   most of the honest text will tell you that solving general recurrence relationship is in essence a guess job.   This is where the substitution method shines.

Of course we all know that there are useful exceptions.  There is the divide-and-conquer type.  That is when you have the situation where there is a term T(n/a).   Basically, tree method, the master method shine.

Now of course, if you talk about Math, many interesting things could happen.  So for example, just on the divide-and-conquer type of recurrence - so what if we have a linear combination of the term T(n/a)?  This is where master method will not work and you need to retreat back to tree method.

If you are looking for a standard method,  then you have to use Akra-Bassi method which states the general solution of  T(n) =  Sum T(n/a_i) + f(n) .  This is the stated in the bibliographical references but not covered in CLRS.

Now how about another important class where.   T(n) = Sum T(n-a_i)?  This is usually known as linear recurrence relation (ref: the famous "Discrete Mathematics and Applications").  In that case, one needs to introduce powerful method such as generating function to solve this kind of question.  Again, this is not something which is not covered in CLRS.

So here you have it, CLRS basically hadn't covered many standard techniques in solving recurrence relation.  But its exercises are a bit unforgiving because it has question such as 4.3-6 which require solving recurrence such as T(n) = T(n/2+17) + n or 4.4.5 which requires solving T(n) = T(n/2) + T(n-1) + n.  In a ways, both of them are kinds of recurrence relation which are both linear and divide-and-conquer.  The goal is to train the reader to learn "how to guess?".

That is perhaps why some of these problems are not easy. 4.3-6, for example, takes some space to explain if you try to solve it using substitution method.

In a way, CLRS's treatement on recurrence is both too simple and too difficult.  I don't blame the authors.  In my opinion. its real strength, especially in 3rd edition, is that it motivates the reader how to think of recurrence relation and how they occur.   Concrete Mathematics reads similarly but it would take 7 chapters before the readers can reach the point of learning how to solve recurrence using generating function.  So as an introductory text, CLRS is doing a fairly good job.

But for readers who are looking for an encyclopedic text, do bear in mind that, CLRS needs to be supplemented by other books.  If you want to understand the "full" story, you still need to read TAOCP and CMath.

Ah learning, learning.

Finally looked up the solution of 4.3-6 and some thoughts.

After a month of getting stuck in 4.3-6.   I passed the 1 month period which I vowed to not look up a solution if I couldn't solve a problem.  Eventually,   I found the solution on the web and it was not a short solution and it takes some time to understand.

What was the issue then? As it turns out, it's because I use a wrong form of guess.  So no matter what I do, I still couldn't find the answer.

Another thing I learn is that one should always try to understand how the base case works first.   The implicit question asked in every questions in Section 4.3 and 4.4 is that "What the initial condition is?"  If I had thought through, may be I could resolve the issue.

Oh well, at least I am unstuck.  This problem should be studied and it deserved a write-up.

Status 20110902(a)

Back-record : Finish 4-4.4.  Finished in my head: 21-1.1 and 21-1.2.

Browse reading: 505/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,6}, 12.4-4, P12.4(a), 15-1.1, 15.1-3, 15.3-3, 15.5, 17-1.1, 21-1.1, 21-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.  

First homework assignment

It didn't arrive yet but I was able to search for the last year assignment using Google.  I tried my hands on the written questions.  Of course, they are just a breeze.   Once you can finish CLRS Chapter 2 to 4.  You are way more powerful to solve basic programming problems. 

Java is also pretty nice to use when testing algorithm.  It is also elegant in the way I don't need to implement my algorithm with static array which is kind of ugly. 

There are totally 5 assignments and there is a programming project after that.  I guess my first goal is to finish all assignments first.  As the difficulty is fairly low.  This should take me around 40-60 hours to finish them. 

Recurrence and its definition in CLRS

I started to realize why I am a bit more lost than I thought in Chapter 4.

Part of the reasons is that CLRS doesn't always define precisely how the recursion equation was.  For example, is it floored or ceiling?  This always bring me a lot of confusion. 

I wish I can use the generating function method to solve some of the issues.  CMath is very good in this aspect. Though there are certainly technical problems : how do I handle terms such as T(n/2)?

This is a good path.  Because I start to connect several things in my head to resolve my stuckness. 

New strategy to unstuck myself

Get faster and skip some of the problems. 

It is sort of meaningless to stuck in the same type of the problems if I don't really learn any skills from it.  I am in the process of working on Chapter 4 for a while but I couldn't move on quickly from it.  So it is a moment to take some decisive actions.

Let's see how it works out. 

status 20110830(a)

Skipped 4-4.3

Browse reading: 505/1144
Exercises up to 4-4.4

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

Skipped 4.4-3

I still don't know how to resolve the issue of "constant within the bracket".  So I will go ahead to work on 4.4-4 first.

status 20110823(a)

Finished 4-4.2 on paper.  Not tough at all.

Browse reading: 505/1144
Exercises up to 4-4.3

Revisit : 4.2-{3-5}, 4-3.6 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, 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,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.

status 20110805(a)

Finished 4-4.1 on paper.

Browse reading: 505/1144
Exercises up to 4-4.2

Revisit : 4.2-{3-5}, 4-3.6 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, 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,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 Section 4.4

As it turns out, the second example is a bit more complicated than I thought. 

Also, it is a very important thing to make sure I go the right thinking even the purpose of the recursion tree method is to provide a guess.

Fixed Erratas from Chapter 1 to 4

After learning my lessons from 4-3.8.  I decided to fix errata from time to time to make sure I got the right learning from the book.   I will probably do this every time I start a chapter.

CLRS Section 4.3

It turns out to be a rather difficult section to go through.  Particularly in proving the bounds.   It takes some creativity to get the proof going.

I also mentioned that I couldn't resolve 4.3-6.   I believe this is one of those situations where you make assumptions about your proof.   I am not exactly happy with those types of proof.   So I would want to spend some time to prove it vigorously myself.

The thing that I really feel happy about is that I still have momentum to work on the book.  It is my ultimate goal.  Many people study algorithms in a course or two.  Not many can go through CLRS.  I will become one.

status 20110804(a)

Finished 4-3.9 on paper.

Browse reading: 505/1144
Exercises up to 4-4.1

Revisit : 4.2-{3-5}, 4-3.6 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, 4.3-9, The whole Section 4.4, 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,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.

4.3-9

Ah. There is really something wrong.  As it turns out my initial estimate is too conservative.   So the bound is not tight.

This taught me something : make sure you run recursive method and the master method before you really go ahead to proof the bound.   Good lesson