Reread several chapters of sorting (Chapter 7, 8 and 9)

After learning quicksort again in the lecture, I decided to revisit the chapter on quicksort, radixsort and the median.  I have finished all the exercises of Chapter 2 so I am a little bit more confident with mergesort.   Of course,  it is unlikely for me to exhaust any of these topics because there are many tricks.   (That reminds me about my good old to-do list, I should bring it up again soon.)

Several things I learnt in this read - First of all, I think I finally grok why quicksort average case is nlogn.  The intuitive understanding using randomized version is simply to grasp.  The tougher part is the actual O derivation. In both cases, it's not impossible to understand: CLRS's version is actually purely probabilistic so it is easier to understand,  Sedgewick's version (7.2 of AIC) directly solve recursion.  I think it is cleaner.  Both require some understanding of harmonic sequence.  Oh well, who doesn't have it?

Another thing I grokked is how the algorithm of i-th order statistics works.  Arg, how difficult can that be?  If the pivot index equals to i, you get the answer already.   My question here is how to use red-black tree to come up with an answer like this as well. 

A more challenging part is probably how to really write these algorithms.   Now it's not a good time yet, but once I start the 2nd browse read.  I will do something. 

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. 

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.

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

Long Weekend

Three things happened during the weekend.

• I was sick.  With headache and temperature,
• Finished ZAMM,
• Watched the first lecture of MIT "Introduction to Algorithm".

Got to get back to studying.   But getting sick is one gumption trap.  My current strategy?  Try to finish simple stuffs and get through the darkest time when you don't feel you want to learn more.   I will first write up my experience on these 3 small issues.  Then move on again.

After Chapter 2

After finishing all exercises of Chapter 2, I have a great feeling I hadn't had for long time.   The last Math/CS book I read was "Elementary Number Theory".  That was when I first started to work and still have some time to do some math on my spare time.    After that, I was always busy on one thing or the other.   That was like 8 years ago. 

To be honest, I feel like I was always busy because of stupid reasons.  In work, sometimes I just work a lot of hours because ...... well ...... my methods were stupid.  Experience taught me tough and hard lessons.

Back to learning,  after the few minutes of excitement I start to ask myself what should I do next.   By reading Chapter 2, I found that my programming has tons of issues.  So learning is necessary.   But what should be the next thing I learn?

First of all, I hope to go deeper into the study of data structure.  At this point, I would say I only got rough picture of even simple topics such as ...... insertion sort.

A famous poker player, chess player, Dan Harrington once describe how his coach taught him how to play chess.   Every time when Harrington makes a mistake, his coach will ask him to describe what he is thinking.    In chess, if you cannot describe what you are thinking or why you are doing something, then no one (include yourself) can correct you and fix your problem.  

Programming is very similar to chess,  a complex trains of thought is transformed to several lines of source code.   They have to be exactly right.   Consider an insertion sort,  can the index be slightly wrong? Can we skip a particular assignment statement?  Can we switch the indices?    Not really, the hundred something characters by itself form a complex structure.  There are only a few ways to change the code such that it does similar thing but the code are changed. (Consider variations of insertion sort, such as binary insertion sort or even insertion sort with sentinels.)

That's why deepening is important.   In my complementary exercises, I list all the concepts I want to learn about "simple" topics of insertion sort.  Even though I have finished Chapter 2, I am not satisfied with my understanding.   That's what I called Read 3, that's toughest part of understanding - building connection for a concept.

But in this deepening process I want to set one rule to myself.  That is I still want to complete CLRS before I move on to another book.   It's ok to finish some simple exercises from other books but I want to focus on *one* but *only one* book.   Or simply I want to *focus*. 

You may share the same feeling, how many times we were distracted by the beauty of knowledge?   So many of them are fun and interesting.   The dilemma if you learn in this way is that the more you learn, the less you have learned.

On the other hand, a deep study of just one to two chapters always seems to pay off handsomely.  So this time I refuse to get distracted by another more difficult or perhaps more interesting book.   I just want to focus on one single book and see what it taught me.  I believe CLRS is a good book to be read in this way.

So, in short, let's start chapter 3 as well as try deepen what I know.  We will see how it goes.

33_P

Finally, I finished all exercises of Chapter 2!

Just finished P2.4d.  So I finally finished Chapter 2! Phew.  Geez.  It's a quite a bit of work.  But I finally finished all exercises in Chapter 2.  Of course, my learning is way more than just that - I also learn how to write 8 algorithms.   In fact 6 of them can be regarded as separate algorithms.

After chapter Ex. P2.2 and Ex. P2.3, I realized that there are more things remained to learned.   For example, the concept of loop invariants are not something I have drilled thoroughly. Though my proof in bubble sort is correct.  So my loop variants proof for selection and insertion sort are likely to be wrong.    So I will need to rewrite them. 

It's also quite important to implement algorithm suggested by the exercises.  For most of time, one can pick up bugs from the original pseudocode.  

In any case, I will update the status first but the complementary reading list for Chapter 2 tomorrow.

P.2.4

I solved it in my head.  P.2.4-4 is a little bit tricky but there's a hint so it's not impossible to figure out.

Ex. P2.1

Hmm.  It sounds like I got stuck in Exercise P2.1c.  This seems to require math in Chapter 3 before I can completely resolve it.

My options: I will first write down the solution for a,b,d, then move on to P2.2.  And whenever I finish Chapter 3 again, I will revisit this particular problem.

BTW.  As it turns out there are a number of solution sets floating around in the web.  My take on it: only use it as a last resort, I did look up solution for P2.1c but I have already tried it.   That I think it's a reasonable attitude - You can't just look up the solution without trying and you need to move on when you hit difficult problems too.

Ex. P2.1

I think through a,b and d. For c, I am certainly confused by the definition of the theta notation.  Let's read ahead to Chapter 3 to make sure I understand them.

Status at 20110505

Finished Exercise 2.3-2, 2.3-3.

2.3-3 is trivial.  2.3-2 though, I just translate my C-code back to CLRS style of pseudocode.  It is long, just the MERGE function takes 22 lines.  I bet there is a better way to do it.

Browse Read: 236/1144
Exercises Up To: 2.3-4
Exercises which are finished but not on paper: 2.3-7, 6.1-7, 6.2-3, 6.2-4, 10.1-6 and 10.1-7.

Finishing merge sort gives me a boost.  The basic form is not tough but it's quite involved.  Young me could have used more than a day to program it without knowing what goes wrong.   In any case, probably data structure should be learnt when one is proficient in one particular programming language.   (Or as I suspect, one should learn another language to appreciate what "language" means.)

Status at 20110428

Finished the reading on median.  The algorithm is very smart!  In fact, I should spend more time on thinking using similar technique to solve problems.

Also started the basic data structure chapter.  This is also where all the classical data structures are presented in the style of CLRS pseudocode.  It certainly makes much more sense to me now.

Browse Read: 236/1144
Exercises up to Section 2.3-2
Exercises which are finished but not on paper: 2.3-7, 6.1-7, 6.2-3 and 6.2-4. 

Status at 20110425

* Finished 2.3-1.  It's trivial. 
* Also thought through 2.3-7, it's a cute question. It teaches a pattern. Whenever you got stuck at a problem, try to sort some of the data.
* Exercises 2.3-2 - 2.3-6 are all cute exercises which guide the reader through slightly advanced concept such as binary search as well as binary insertion tree. This makes one able to learn 5 sorting algorithms in this chapter.  Pretty neat indeed.
* It's also time to make merge sort to be one of my move. Pretty neat idea as well.

Browse Read: 200/1144
Exercises up to Section 2.3-2
Exercises which are finished but not on paper: 2.3-7, 6.1-7, 6.2-3 and 6.2-4.

Status at 20110422 (c)

Solved 2.2-3 and 2.2-4.  Both are not difficult.  This reminds me though.  I need to analyze the worst case and average case analysis of insertion sort and selection sort.

My exercise read will move on once I do that.
Browse read: 200/1144
Exercise up to 2.3-1

33_P

Status at 20110422 (b)

I was able to break my reading block on heap sort.  Then I cruised through chapter 7 on quick sort and come to chapter 8.   I believe 6, 7, 8 are advanced topics which require good background in theory.  So reread is necessary.   There are topics which I feel blurry - that include priority queue and the analysis of quick sort.  Those are very important but not easy to fully understand.

I also reread the material about merge sort and Chapter 3 again.   Now I get them.  My mind just wasn't ready for them.  In fact, this is a very good book to own because once you finished Chapter 2 and drill it seriously.  You already know 4 basic comparison sorting algorithm by heart, one even has performance in theta(nlogn).

Browse Read: 200/1144
Exercises up to 2.2-3

33_P
(Correction: there are only 1144 pages in the 3rd edition.)

Status at 20110422

Finished 2.2-2 on paper.  My selection sort pseudocode took 10 lines.  That is 2 lines and 1 variable more than necessary. I am going to improve it before I start practice writing it.

So far,
Browse Read: 159/1155
Exercises up to : 2.2-3

33_P

Status at 20110418 (b)

Finished 2-2.1 .  Not something difficult.  Also looked at 2-2.4.  I don't think I know the answer on top of my head but you can call it a kind of Zen's questions.

When I write it down on paper I would report.

Browse read : 155/1155
Exercise up to 2-2.2
33_P

Status at 20110418

After couple of days of tiring housework, I decided to work on the book slowly again.  Just finished Section 6.1 and I start to feel comfortable about the terminology of heap sort.

Another interesting thing happens in my mind, I start to hope to do the next exercise.  Just like when you are young and you are see a Math problem books.  You want to solve all problems in it.   It's not much different here.

Sometimes I think I might be just the programmer version of Julie in Julie and Julia.   Well, I guess real-life is always difficult. It's just difficult in different ways for different people.

Browse Read: 154/1155
Exercise up to : 2.2-1

33_P

Status at 20110414

My reading goes slowly. Finished all exercises at 2-2.  Writing proofs and solving exercises are always mind-provoking.  I also found that seriously read through heap sort takes some mental power. 

Ex 2-1.3 is a trivial problem with a very simple pseudocode answer.  Though writing a good proof is a tougher problem.  I might put my proof here and see how wrong it is. 

Ex 2-1.4 reminds me my class in logic design.  At the end of the day, my solution still requires defining sub-routines of XOR and NOT.   It seems to me they are necessary. 

-Browse reading : 150/1144.
-Exercise up to 2-2.1.

Loop Invariant

I start to learn what a loop invariant is and I wish I learned it long time ago.   It is a good habit to always think like this so that one can *prove* one is doing the right thing.

Intuition can help but it will fail when situation is complicated.  Besides, a loop invariant type of thinking can simply the loop and make it short.  (I like short program a lot.)