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. 

First browse-read of CLRS

As I flipped through Chapter 35, I have also finished the first browse read of "Introduction to Algorithms", commonly known as CLRS once.   As the name suggests, I only browse through the chapters and occasionally write down solutions I can figure out.  The first read is meant to be shallow but fast.  That's why it only take seven months to finish.  If I read the book by going through every single detail, I probably need to spend many years to go through the book once  -  That's not a prudent way to read an algorithmic book.    Sometimes, you just read it like a book and extract some simple knowledge out of it.  Just like what you do to read any book.

Before I go on, let me side-track a bit, as you might also know, I have another two reads known as "exercise read" and "research read". The former is a kind of read which force myself to do all the exercises.  Whereas the second include some research problems which popped up from my head.   The "exercise read" is closed to a common university graduate course on algorithms and data structure and the former is a bit closed to basic academic research.  Normally I recorded the status of exercises in the "Status XXXXX" post and research problem in the "complementary exercises".    At this point, I only finish up to the half of the chapter 4 in  "exercise read".  For "research read", I can barely go through Chapter 2.   It sorts of show how difficult when you try to go deep.   

My guess is the ratio of chapters they can go through between their "browse read" and "exercise read" could be very different from me.   For most, they will just completely discard the idea of reading an algorithmic book from scratch.   I can see their points but I always maintain that in computer science, if you think deep enough, you will be bound to touch all the topics found in CLRS including the selected topic.   Many people I know have strong algorithmic skills reference "brick" books like CLRS and TAOCP a lot.   If you start to read them, you will get benefits from them even if you don't completely grok. 

Back to the first browse read, I would say in this read, the amount of exercises I really work out diminish as further back of the book.  The three chapters which really stuck me are probabilities,  binary-tree and red-black tree.  Basic math can always be tough.  Basic data structure such as binary tree, can also give one a lot of headache. Red-black tree is a bit of topic which is deeper than the bottom.  Given that I am reading them in a relatively fast way  so I am not surprised if I don't really grok all of them. 

After a class in famous extension school, my understanding in binary tree has tremendously improved.  But for the other two topics are still a bit beyond me.  Some probability problem can be monstrously tough and  famous extension school only teach B-tree (or something like 2-3 tree) so I still need to think through red-black tree quite a bit myself.   

For the first browse read, I think those are okay, again you don't want to catch up with tough problems when you get stuck.   Sometimes you just want to build context in your brain.  That's what I am doing.  

But one thing I am sure: I need to change the way I approach the book - a purely linear path can be very difficult.  In my case in particular, I found that my exercise read in Chapter 4 turns out to be very difficult.  This also means that my mathematical background is not deep enough.   So I decided to back up from there.  That always take time to improve.   

My skill though is more suitable to take care sorting and data structure.  I am psyched about it.  I also think through a lot of problem from the famous extension school course.   That should be a better starting point. 

Now my new plan would be this. 

1,  Turn the browse-read pointer around to the first chapter I haven't finished all exercises.  i.e. Chapter 4.  After the first browse-read, the second read will always teach you something new as well.  During this process, I hope to attain a higher coverage rate on the exercises of the book.  This also allows me to identify chapters which are suitable to my level. 

2,  Abandon Chapter 4, restart the exercise read from Chapter 6 on heap sort.  The goal is to finish Chapter 6 's exercise read.  Occasionally work on exercises on Chapter 4 if I like. 

In any case, let's see how it goes.  I hope this work out and the next step is to readjust and try to go through my study. 

33_P

Chapter 35: Approximation Algorithms

This is a simpler chapter than Chapter 35 as it describe approximations of many NPC problem. (Ah. start to change the habit of calling an algorithm NPC instead of NP.)

As with many later chapters, it is not a chapter I fully grok.  But as always, skimming through a chapter of CLRS always teach your a lot of thing invaluable in computer science.  For example, now I have the notion of what approximation is and what type of varieties it can have.

In any case, this particular read follow the theme I have these days: Try to finish 1 round of browse read first, then deepen.   During the lighter read, I don't have to learn all the things in the book - I just need to make sure I got some basic understanding of the topic.  So talking about it, it's probably ok. But using it will take time to reiterate on a topic.  In another words, I leave the grokking a little bit later.

Okay.  I finally finished the first browse -read, it's time to rethink how I should proceed with the book.

Tree Traversal

Played with one of these traversal problems of tree.  For example, how you can come up with the tree from two different traversal results.

Chapter 34 NP-Completeness

This is a very tough part of the book.  It's also very similar to many books I read in computational theory.  It's perhaps because there is no definitive answer (yet) on the relationship between the class P and NPC.   At the very least I think I understand how P and NPC is defined now.  This seems to give me at least a grip of what's going on when people are talking.   Many people just talk on this kind of things and it's rather easy to talk.  I actually find that most of the proofs are rather difficult and it's not easy to grasp.   Let's see if I can sense honesty next time.

I also learned that boolean satisfiability is an important problem because all problems need to reduce to boolean satisfaibility before they can be proved NPC.  This is an important concept.  So next time, when I read it, I will put more attention.

I am very closed to finish the first browse read of the book.   Did I understand everything in algorithms yet? Absolutely not.  Oh well, at least I learn some basic sorting algorithm and recursion.  They will be useful for life.

Finished the whole homework

I just need to check whether the answers for written problems can be compiled. Then I am all set.

Finished all programming assignment!

Yep. I got it. It's a bit tough but things are working fine. Now let's go back to work on written question number 2. May be tonight I can finish the whole assignment.

Finished Programming problem 2 in Assignment 3

It takes some time but it is much easier than I though. (Also fixed the bug. Now only one more exercise to go. )

Finished Programming HW1 of Assignment 3

Finally. Let's do some testing first.

Programming HW1 of assignment 3

Great. As it turned out there are quite a bit of repetition of this problem from last year.  So my effort of pre-working on the homework is not a waste. 

I still have two more functions to write but I don't think it is too big a deal.

Finished HW4 of assignment 3

The stack problem is not that difficult to solve.  There are some technicalities on how to take care of string with odd or even length but that's not super difficult.

How to use a stack to test a palindrome?

Come to think of it, it's actually very simple.  You just need to push the first half of the string into the stack and for the second half, if the element is the same as the top of the stack, you can pop it out from the stack.   If the stack is empty, this means you have a palindrome.   If there is any one element which you can't pop, then we are not looking at a palindrome. 

Finished HW3 of assignment 3

After some considerations, I have finished the mildy tricky node deletion problem for doubly linked list.  There are 4 special cases.

 This is quite interesting so I might as well implemented it.

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

Some thought on Chapter 34

First of all, I don't grok.  Perhaps it is related to the fact that I don't fully understand dynamic programming and graph algorithm.  Understanding those will be a cornerstone to understand the basic of computational theory.

But oh well, at this point, I have mind to move on with the browse read.   The first browse read could be sloppy but I am ok with it.  Several of the selected topics are just one book by themselves.

33_P

Restart doing the homework.

After the exam, the pressure is really lifted.  This time I will skip problem 2 and go ahead to work on other problems first.

No worries.  There should be more hint along the way.

While I am taking an exam......

It has been a while when I go to a lecture.  The feeling is funny.   First  ofa ll, picking a seat in a lecture room is oddly similar to picking a seat in a movie theatre.  You want to be maximally separated from other strangers.  You also want to make sure you can see the subject of the lecture. 

Then there was the strange feeling of "Oh, that's great. I am back to school again. "  I wonder whether you have seen the musical Avenue Q.  There is a song said "I wish I can go back to college."  Indeed, most of us feeling very happy when we can go back to college just for a little while.    We know it's kind of bad for us to stay there for long time.  But..... just a little while. just a little while seems to make us feel happy. 

You also has another nostalgic feeling : what if I can skip this class?   Nah.  all my rationality is fighting against my young playful tendency (an honestly naivete) now.   I am paying for this so I can only come through.   It is not an issue of whether I can get good grade any more but I just want to get something out of the class.    The knowledge is the key.   Not the circumferential thing, such as grade, which doesn't matter starting from the beginning.

As for how I will do, very likely it won't be that good.  But I am probably more well-prepared than the past.  After all, we all just being examined too many times......

Finished Problem 1 of HW3

After a while, I finally worked out one problem but I got stuck in the second problem. It might take some time to think it through. In any case, it's good to start. It always takes some time to finish the homework anyway.

After taking a break in programming

I stopped for a while but I start to gain some momentum. Now I decided to restart doing the actual HW3. Will that be difficult? Probably not, it's just basic linked list problem. Though, doing it in Java is probably something harder. So keep my mind on it as Java is also an essential skill these days.

Chapter 33: Computational Geometry

Brief Scan of Chapter 33. I don't really grok the whole thing but I am some fragmented idea on Graham's scan. This is something I should reread and perhaps read a more serious book.

RIP. Mr Jobs.

In our time, it's hard to find someone you can call a visionary.  Mr. Steve Jobs is worthwhile for the title.


News from CNN

I need to get back to self-study

This is still the most important thread in my life now.  It is also the one which brings the most emotional benefit to me. But well, after a crazy work schedule, I am happy to be relaxed for a while.

More game programming

After working a while on the game I took up, it is not as difficult as I thought.  In fact a lot of logic are pretty interesting.  

Whenever you feel you don't understand something, try to understand it from main.   If you can work out the whole logic of how your main function goes down to a particular functionality of your program.  Then there must be something wrong with your thinking.  The program I touched today is in Objective-C with Cocoa.   So part of what I am doing today is just to understand what's going on with the whole framework how it works.  

The bought me dividend and what the code soon becomes obvious with me.   So I start to be able to change the code in a quicker manner.

Game programming is also a strange subject.  Sometimes, the fun of the game really depends on not just the game logic.  It also depends on the graph and music or more importantly the whole combination.   The game I picked up was rather odd at the point I picked it up.   Though after a while of meditation, the impression change.  And it only takes a change in the background music.

I was able to compile and ObjC program with class!

Sounds simple.  The devil is the detail.   In fact, when I try to compile my code using simple gcc, I always have trouble to get the library for NSObject.  It took me about an hour to sort of test the solution out.

In any case, I finally get the the part about creating class goes up and running.   This makes sense now.  I might need to write my own tutorial soon.

Let's take a break.  I will go to figure out some more examples of Objective-C.

Started to learn some Objective-C

I am trying to follow this tutorial:
http://www.otierney.net/objective-c.html