Will I ever forget this?

I just chatted with my colleagues on using sentinel of linear search.  In my mind, I always assume one can use a negative infinity as a sentinel.

But when one of colleagues come back to me and ask "Doesn't that mean you still have two comparisons? "  Then I was dumbfounded.   And his is right! I was dead wrong!

As it turns out, one should actually use the key as the sentinel.  In that case, one just need to check the return index is smaller than the length of the array or the length of the array +1 at the end of the search to decide if the search is sucessful.

This is a good mistake, I think I will never forget this trick from now on.

status 20110726(a)

Finished 4-3.5 on paper

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

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

Still not in my full speed

This is still a moment I am going slow because anyone of the mathematical problem could be tough to solve.

At this kind of situation, I tend to go with the flow.  It's not particularly helpful if you try to push the progress by thinking a problem for long hours.  In my case, I just like to push it whenever my brain wants to take one more problem. 

Things are getting better, one of my deadlines is cancelled.  I can more focused.  Of course, there is always a fight if you want to be persistent and continue with something difficult like algorithms.

Status 20110725(a)

Finished 4-3.5 on a scrap paper. Just need to put it down in my notebook.

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

Revisit : 4.2-{3-5} 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-{5,6,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 thought after my stuckness

I am not certainly not in full speed in my algorithmic study.  There are two other priorities in my life which are competing. 

One is work.   Though I don't perfectly happy with the work environment, I still consider a must to do a good job in work. 

The other is languages.  I spent some of my time in Spanish, some of time in French.   My original intention of learning them is to open my mind.   In fact, I always find learning a language do some special magic in my mind.   I seem to be ...... smarter.  I also feel I realize something I don't usually do.  

What does language learning teach me?   To me, the biggest lesson is that not everyone is learning correctly.  They put stress on something unimportant.   For example, if you are bad in Spanish subjunctives, what should you do?   In concrete, if you do an grammar exercise which you got them wrong all the time for the first time.  what should you do? 

This is the moment many people would think that they are "not good enough" or "smart enough".   Some would even decide to give up.   Here is a correct thing to do : treat it like a sport exercises, do it again and again until you come to perfection.   The thing is you might not be talented in Spanish, but you might be talented in learning.

You might say if I am not learning this fast enough.  Doesn't that mean I am not talented enough? Doesn't that mean I should just work on something else which my talents are better used?  Again, I think this is a wrong mindset. 

Why? Here is the reason.  If you have the tendency to give up learning one thing, so why not give up another one?   why not give up the third thing? why not give up the forth, ...... or the N-th thing? 


Why not? Once you admit that there can be something beyond you.  I think you need to admit many things else to be beyond you.   It's true scientifically that you can't be No.1 in everything.   But it's also true that your potential is way more than what you have now.   So a better Why-not here :

Why not go for it? Why not keep it on? Why not I try harder? Why not changing my strategy to solve this problem?

That's why when I decide to do something or solve a problem, I usually wrestle with it until the problem succumb to me.   It's a problem that takes a long time to think about?  I wrote it down to a notebook.   If it's a problem that has been solved, I wouldn't waste it, I will try to think of another solution.  How come one should feel happy with an existing and old solution?  Why not come up with someone simpler? Faster? Generalize the solution to something more interesting?

Admittedly, my learning in last week or so has been slowed down.  Also, there starts to be some topics which are tougher than what can I understand.   But I won't give up.  Because I know,  there is nothing so difficult that I can't thoroughly understand in algorithm.   There are only the wrong method to learn, the wrong explanation,  the over-complicated thinking.    And those issues can be resolved.   (Hell, they can be) .   Wrong method to learn can be corrected.  A correct explanation can always be looked up and you can always ask an expert.   You can always simplify your thought.  

There is nothing related to whether one person is smart or not.   He/she can just learn.   So I am not going to be deterred by the thousands of discouragement I got.   I am just going to learn.

status 20110721(c)

Finished 4-3.4 on paper

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

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

status 20110721(b)

Put 4.3-3 on paper.

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

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

status 20110721(a)

Put 4.3-2 on paper. 4-3-3 should be soon.. 

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

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

status 20110719 (b)

In similar manner, I also resolved 4-3.3.

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

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

status 20110719

I finally got 4.3-2 in detail and put that on scrap paper.  I expect similar difficult await for me on 4.3-3. 

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

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

Tiredness

I just feel tired.  Of all the things I have been doing.  Recently I just can't find I got any of them to have some progress.  Or the feeling of progress is just so slow or close to nothing. 

This is the moment I should just start to cut something in my todo and focus on what is important.   At the end of the day, I will say Data structure and Spanish are probably the most important things in my life right now.   French barge in from time-to-time.

But I subscribe to the theory that if you feel tired, you should simply take some rest before you move on.   Working on something all the time doesn't make you more efficient or better.

On my Data structure study: I am thinking may be I should skip 4-3.2 for a while.  Ah, that's probably the way it is.   Sometimes I could underestimate the difficulty of a problem.  So even I thought it is a problem solved, it can take time to work out the detail.

My recent stuckness 20110716

I am stuck in 4.3-2.  It's a stupid inequality but my head just couldn't work it out. 

I start to have this feeling again.  After some good work done in my job, I start to feel less momentum to move  on.  

But this is a gumption trap.  I know for sure that I won't work in my place forever.  It is just the way it is.  Am I just overloaded?  Probably.  Work, Data Structure, Spanish, French and Jogging.  (Turns out I just finished running 5km and I can certainly do more.) 

But I don't want to give up.  I am going deeper on all these aspects of my life.  I am tired but generally elated.   At least I am not wasting time on something nonsensical (like games, poker etc.)

I need some good rest though.   Sometimes I just want to sit down and do nothing.

How do I want to deal with this stuckness?  I will follow my usual strategy - divide the task to be smaller.  Try to conquer them and gain more momentum.   So let's start the process slowly.

status 20110715

Read Chapter 18.  Didn't grok. But I will go forward.

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

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

Reread the rest of Chapter4

Now I start to get to the mathematical part of Chapter4.  I would hope to get some steam.   I have finished in my head most of the rest of Chapter 4 except 4.6.  (Ah starred questions.....).    So I think I cruised through the rest soon.

It's a pity I couldn't implement Strassen's algorithm.   But it is too specific a topic.  I guess I will do this when I am focused on arithmetic algorithm.  (Will I? Probably, mainly for fun.)

status 20110713(b)

Solved 4.3-1 on paper. Solved in my head 4.5-3. 

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

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

status 20110713(a)

Solved 4.3-3 and 4.3-9 in my head.

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

Revisit : 4.2-{3-5} after section 4.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,3,4,5,6,9}, 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-{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.

Decided to skip Strassen's algorithm's implementation

Ah, I want to gather some momentum to move on with the book.

status 20110708(e)

Solved 10.2-1,2 and 10.2-6,7.  Much better. I guess I can sense my true issue in linked list. 

In any case, the point of doing exercises by jumping chapters around is more on making myself warm up different material when I am really working on that chapter.  For me, this is usually very effective.

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-{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 20110708(d)

Solved 10-1.{1-4}.  Those ... are trivial exercises.  What it bugs me is that I have some remote feeling when I looked at the linked list sections.  Ah, after all, if you hadn't implemented this stuff, it would take a while to get use to this feeling.

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-{1-4,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 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.

Status 20110708(b)

Finished the whole Chapter 17. Don't fully understand the accounting method and potential method.  But I think I understand the general idea.  It certainly teach me something new.  In the past I saw the term amortized analysis a lot in on-line training literature. This is the first time I sort of understand what it means.  Also finished in my head 17-1.1. 

Chapter 18 is on B-tree.  I think I should read up Red-Black tree again.  It has been a while since I read it last time. 

Good progress.  Again. I should implement Strassen's algorithm before I move on to 4-3.1. It's just a promise I made myself.

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,4} 12.2-{2.3}, 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 20110708

Finished 4-2.7.  I promised myself. I will implement Strassen's algorithm before I move on to 4.3.1

Browse reading: 450/1144
Exercises up to 4-2.6 

Revisit : 4.3.1

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

TAOCP 4.1 : Positional Number Systems

Fascinating.

status 20110707

Finished 4-2.6. I skipped the implementation of Strassen's algorithm for the moment but I implement it before I start Section 4-3.

Browse reading: 450/1144
Exercises up to 4-2.6 

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

Ok. Let's implement Strassen's algorithm today

It's just fun.  I couldn't help to do it.

I am going to take a Data Structure course!

It's a win. I am able to convince a stakeholder to let me take a data structure class in September! Alright, I am going to fully utilize this opportunity!

33_P

status 20110704

Finished 4-2.1 and 4-2.2.  It's better to move on after I implement Strassen's algorithm. After that I will follow the book's advice to skip to 4-2.6. Both 4-2.6 and 4-2.7 are fairly easy to solve. 

 

It's also a bit unfortunate my laptop battery is damaged.  Need to fix it soon.  

Browse reading: 450/1144
Exercises up to 4-2.3

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

CLRS Solution Checking

I have started a sporadic effort on checking the solutions of my own work.  Of course, it is done in a very slow pace given my schedule.

I tend to believe that many people abuse homework solutions because I saw a lot of my College classmates did that.  It is probably the least honorable thing to do though many people did that to survive college.

At the same time,  I think posting solutions will probably not make this situation of plagarism better or worse.   In our work, copying a solution but not understanding it will always make one suffer.   For good and bad, many of my classmates didn't end up going deep in technical job.  For those who copied without thinking, they probably won't generate too much of deep thought neither.

Saying so, I would be more circumspect when I post my solutions.  For example, I hope to cross check my work with couple of other sources before I put them out.   I also want to release them slowly such that it gives me some time to churn on it and discover mistakes and alternative solution.

So after some thoughts, I still decide to release solutions but it would be 5 chapters at a time.  It has to be good work and has reasonable degree of scholarship. 

33_F

Chapter3 (Read 1)

After every exercise read of a Chapter, I would like to write an after-thought post on how I think.   I wrote one for Chapter 2 so I will also write one for Chapter 3.

I finished Chapter 3 much faster than Chapter 2.  Mainly because Chapter 3 is more mathematical than algorithmic.  So I usually spent less time in implementation.  Though it's interesting to see that Chapter 3 gave me more pain because some of the problems simply requires more than normal amount of creativity. 

There was once I read a post by Prof. Terrence Tao, widely known as the "Mozart in Mathematics" and the youngest professor in the history of UCLA's Math. department.   In the post, he encourage young researchers to think and innovate.  At the same time, he also suggest when you got stuck, you should revisit old proofs, old exercises. 

When I first read it, I am quite surprised.  These kinds of advice are usually from Math Tutor to non Mathematical inclined students.  But when you think about this, this is actually a great advice. 

We usually think Math and Science as a kind of chain process - one reason is derived from another.  You can visualize this by thinking the arrow of implication go from one argument to another.  And progress in Math and Science is simply whether we create a new arrow.   And the speed of progress depends on how fast these arrows create.

So if you thought in this mode, then what really matter is who is working on a problem.  Because if a person a "smarter", then they can certainly solve a problem faster.

I believe this view is wrong.  Why?

In real-life, people who can solve problems in a particular field (or a task) are usually people who associate more.  That is to say, if you can associate concepts to your problem, you would be more likely to resolve an issue. 

That explain a lot of sayings in Math learning like "You should learn the fundamental well".  

At a certain level, a different point of view will bubble up.  Like Prisig, let's call it the Romantic point of view, that is to say ideas such as Intuition, Creativitiy become more important.  I believe there is certainly degree of truth.  But intuition and creativity always mean somebody has a mysterious hunch to get a problem solved.   It doesn't really explain why such hunch exists in the first place.  That makes me believe the theory of association is a better view.   Another advantage of it: it is something one can acquire by hardwork and it's learnable. 

That is why I believe my read in Chapter 3, though a bit painful, it won't be a flop.  I learned something in that process.  To really quantify, I need to count how many factoids I acquired.   But it is how human learn. 

Similar issues will come up in Chapter 4.  I hope I can use the same mind set to resolve the problems

Status 20110701

Checked 2.1-2, 2.1-3, 2.2-{1,4}, 2.3-{3,7}

Browse reading: 450/1144
Exercises up to 4-2.1
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,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

Updated complementary exercises for CLRS 20110701

Things I have finished:
-(DONE) Chapter2: Watch the MIT video on Chapter2
-(DONE) Chapter3: Read TAOCP on Big Oh.
-(DONE) Chapter3: -Read the Wikipedia's entries in the big Oh notation, iterative logarithm and all Math related subject.
-(DONE) Insertion sort: C, perl, python
-(DONE) Insertion sort: sentinel version of straight insertion sort
-(DONE) Insertion sort: binary search (now a separate item)
-(DONE) Insertion sort: binary insertion sort (now a separate item)
-(DONE) Selection sort: recursive version of insertion sort
-(DONE) Selection sort: C, perl, python
-(DONE) Merge sort: C, perl
-(DONE) Merge sort: Read sedgewick Chapter 8
-(DONE) Linear search: C, MIXAL
-(DONE) Binary search: C
-(DONE) Binary Insertion sort: C
-(DONE) Maximum Subarray Problem : C

Chapter 2 General:
-Write up the summary of the videe on Chapter 2
-Read all the solution sets after I finished the videos.
-work out cost analysis similar to P.26 on selection sort, linear
 search and merge sort (tedious).
-Think how to draw the recursion tree for the insertion sort algorithm.
-Work out all proofs for the following algorithms
  -insertion sort
  -selection sort
  -bubble sort
  -binary insertion sort
  -merge sort
  -linear search
  -binary search
-Implement 2.3.7, P2.1, Horner's rule in P2.3 and inversion
 calculation in P2.4.  2.3.7 has two solutions, one is trivial, one is
 based on merge.  Think them through.

Chapter 3 General
-Finish all exercises of Sedgewick Chapter 2.
-Finish all exercises below Level 25 of TAOCP Section 1.1 and 1.2
-Read CMath Chapter 2, 3 and 9.  Finished all easy exercises.
-Alternative definitions of the asymptotic notion.
-What is the difference between the definitions of Sedgewick with CLRS?

Insertion sort: (C++,java, lisp, ASM, TAOCP Pseudo, TAOCP MIX, TAOCP MMIX.)
-start to write a performance driver
-shell sort, how does the decrement business works?
   -Pratt's increments.
   -Sedgewick's increments.
-library sort
-tree sort(from wikipedia, what is it?)
-insertion sort improvement, all suggested by Exercises from TAOCP.
-insertion sort with linked list
-How does the idea of insert leads to merge sort?
-performance, worst case, average case
-different ways to avoid -INT_MAX as the sentinel. (state of art?)
-non-adaptive version of insertion sort.
-TAOCP Exercises in 5.2.1
-Sedgewick 6.3 Exercises

Selection sort: (C++,java, lisp, ASM, TAOCP Pseudo, TAOCP MIX, TAOCP MMIX.)
-stable version of selection sort.
-bidirectional version of selection sort.
-comparison with insertion sort.
-comparison with bubble sort
-recursive version of insertion sort
-cycle sort
-heap sort variants
     -tournament sort
     -smoothsort.
-TAOCP Exercise in 5.2.3
-Sedgewick 6.2
-Sedgewick 6.2 Exercise

Binary Insertion sort:  (C++, perl, java, lisp, ASM, TAOCP Pseudo, TAOCP MIX, TAOCP MMIX)

Bubble sort: (C++, perl, java, lisp, ASM, TAOCP Pseudo, TAOCP MIX, TAOCP MMIX)
-shaker sort
-TAOCP 5.2.2


Merge sort: (C++, perl, java, lisp, ASM, TAOCP Pseudo, TAOCP MIX, TAOCP MMIX)
-timsort
-performance, worst case, average case
-Improvements from Sedgewick.
-Non-recursive version or Bottom up version
-in place mergesort.
-no extra memory implementation (state of art?)
-variations of merge sort.
-implement merge sort with k list and a k-list merging. 2.4.1.
-TAOCP Exercise in 5.4
-Sedgewick 8 Exercises.
-Shene's 5-9 Exercises.
-where can I find problems which apply merging?
  -Implement CLRS 2.3-7 using merging
  -like to calculate number of inversions.

Linear search: (C++, perl, java, lisp, ASM, TAOCP Pseudo, TAOCP MIX, TAOCP MMIX)
-TAOCP 6.1 and exercises.  Remember, it's not as trivial as you may think.

Binary search: (C++, perl, java, lisp, ASM, TAOCP Pseudo, TAOCP MIX, TAOCP MMIX)
-At least 100 problems which applies binary search.
   -TopCoder's exercises on binary search.
   -Implement CLRS 2.3-7.
   -Shene Chapter 4.
-After reading Gries, make sure you prove your own binary search is correct.
-TAOCP 6.2 and exercises.
-Chapter 4 and 5 of Programming Pearl exercises.
-Sedgewick 12.4
-Fibonacci search
-Range search
-Variations of binary search.
-Thinking: variations of binary search.  They produce different lo, up bounds. Interesting.
-Thinking: can we combine the idea of distribution in binary search?
-Thinking: what happens if binary search is applied to a sequence with N inversions?

Inversions:
-Try to understand TAOCP 5.1 as much as I can.
-Try to do exercises in TAOCP 5.1.

Maximum Subarray Problem:
-perl, python, C++, java, lisp, ASM
-(* hightly recommended) Finish all exercises in Programming Pearl Chapter 8.
-Thinking: How do you extend maximum subarray problem?