Start to take a data structure course today

I will start to take a data structure course today.  It comes with a company-reimbursed course from an extension school of a certain famous university.  I will call it "extension school" from now on because I really don't want to be confused as the students of that famous university.

The course in the extension school are quite rigorous.  It might not be as hard as the MIT 6.046J but it certainly requires some degree of programming. 

One interesting part is it is using Java instead of pseudocode. Not necessarily a good choice.  But I will treat as a chance of learning.  Java can be something very useful for future.

If this starts well, I will also take several hot topic courses in the school.  Such as mobile and web programming.  These skills start to be essential if I want to find a better job.

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.

My recent stuckness

What is it this time? What makes me distracted? Nothing much, the turbulent nature of the stock market.

As many normal adults, I trade stocks amateurishly for fun.   So I am obviously affected by events happend during August and the lower credit rating of the States.

Those are also moments one will also easily distract because an event like that easily change the near term assumption of a person's life.

Money, generally is a gumption trap.  It makes one distracted from his purpose.  For the last 2 weeks, I saw the necessity of being distracted to take care of all money matters.  I promise myself though not to make this a thing to keep.

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.

I lost patience and I have to come back!

It's just a matter of persistence - I remind myself.

Of course, life has so many unexpected term.

Changed Layout

The old layout which are the keywords are cluttered at the top is too confusing.  I decided to separate the Chapter specific information and other keywords. 

Stuck in further reading and its solution

I have stuck in further reading of the book.  Mainly because there are just some background knowledge I don't fully grasp.

For example.  In reading B-tree, since I don't fully understand red-black tree.   I am not really sure about what is it about.

So I think it's time to turnaround and re-read the book from chapters I have done any exercises yet.   That is Chapter5.   This time I can be a bit deep on each chapter.   When I get back to Chapter 19 again, there should be a brand new understanding of what's going on.

CLRS is indeed quite difficult to read.  I am ready to take several courses in order to understand it.

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

4.3-9

Finished 4.3-9, but there are something's wrong.  The solution doesn't seems to be tight. Let's review it before I commit.

4.3-6

Hmm.  I just read the text again, it seems to mean to be a trivial problem.  There must be something I don't get it right. (Update at 20110912) I found the solution and I am just waiting for a good chance to start to work on the exercises again. Probably after I finished my first class with famous extension school.

status 20110803(c)

Finished 4-3.8 on paper. As I explained in the previous post. I actually solved the fixed problem.

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

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.

CLRS 4.3-8

There turns out to have an error in 4.3-8.   The non-recursive term is actually n rather than n^2.   It is a known error from the authors.  

There turns out to be around 70ish such errors exist in the book.  I better correct them first before I move on.

Status 20110803(b)

Finished 4-3.7 on paper.  It is quite trivial. (Compared to 4-3.6)

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

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.

Some other thoughts on 4.3-6

I suspect this is just a technical problem.  The issue I encountered is this.

When I tried to hypothesis the form to be nlogn - clogn -dn -f,  but some positive just pop up.

Another method I tried is to make the assumption of N>17.  In that case,  nlog(n+17) will be smaller than nlog2n.  So I can always get back to a close form. But that turns out to make the expression too big.  

Looking up the web, nothing is really useful.  Sounds like I am on my own.  My guess is this involves the mechanical the proof and the proof of Master Theorem will likely give me some ideas.   I will wait before I look up the solutions.  (Let's not spoil it)

Status 20110803

Given up 4-3.6

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

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.

CLRS 4.3-6

I stumbled on how to solve 4.3-6.   Feel a bit ashamed but I found that the constant 17 is very difficult to remove.  That includes some attempts of mine to subtract a lower terms.

I decided to leave this problem to "something to visit" in my status.   During the time I might go ahead to look at different techniques of solving recurrence.  There is something missing in my understanding/techniques.