Shortcut for chapter specific information

Wednesday, November 30, 2011

I decided to leave. The status of reading CLRS

Gist:
1, I decided to leave my last company.   No matter how my boss explained, I think it is B.S. to stay.
2, Still taking the class but I decided to drop it as I want to take a break.
3, The last few lessons on hash and graphs are very interesting.   Keywords I learned: hash table, chaining, dijkstra algorithm as well as Prim's algorithm.   The last two turned out to be rahter easy to understand.

33_P

Wednesday, November 16, 2011

Hashing, linked list

I should keep my very good habit of reading a topic from CLRS after a class.  My target this time would be hashing and linked list.

After difficult talk ......

I decided to leave.   Why did I decide so late?

I will still go to class in famous extension school but now it's no longer as important......

Wednesday, November 2, 2011

Difficult talk

Today I went to talk with a senior manager of my company.  I thought about this chat for around a month before I go to talk with him.  There are a lot of things I learnt during the talk.

What did we talk about? Essentially I hope to give an official grief of what I am doing at work.  As a low-level employee, a lot of need of being innovative and being aggressive was not taken cared of.    When you work in a big company though, these are tough talks.   You don't want to throw all your raw emotions on other people but you still want to get your frustration and grief through.   In fact, if you believe in someone you can talk with, then it is highly possible that someone can give you a positive feedback.

But human is strange, they are not exactly machine which you can query random things, each has emotion, each has ticks.   You don't just go there when you wake up and try to convince somebody or something.   You take your time, find your spot and try to get your message through.   It is a very tough skill to learn.

Some people are not meant to talk to in a daily basis.   When you come up with something, they will contend you until you succumb to their reasoning.  This kind of "natural debater", if they are insightful or knowledgeable, is worthwhile to chat with them in a well-timed intervals.  At you learn something during the process.  On the other hand, if they are just being contentious for contentious sake, you might want to avoid them and more often you want to confront them with well-crafted arguments.   The purpose, to be honest, is to shut them up.  You don't want them to affect your daily life.   In fact, more than often, you have better things to do.

There are people you want to drop by their office more regularly.   Those are people you want to induce a conversation.  They tend to say whenever they have something to say.   Think whenever they have something to think.   Those are people you want to ask their advises or suggestions.

These are all considerations you want to think through before you talk with a senior-level manager.  Some don't worth your time to talk to them at all.  Others it's completely fine to talk with them, you just need to prepare what you want to say.  The bottom line is you need to communicate, that's a tough thing to do.  You need to follow the convention, the culture, the personality of your boss and most importantly yourself on how to give a cogent argument.

That's what I did.  This is also the first thing I learnt, you don't want to be very reactive on your emotion.  You want to sit down, think it through before you packaged it and let other people know.

Then I learn the second thing, which is how you take care of complains like that.  The senior manager didn't really explicit taught me anything to day.   But he said something like this, "Problem X is essentially a problem which everyone is facing" and I am very convinced by his arguments.  It boils down to the objective reality of the workplace - you either say you are not happy about your workplace.  i.e. you prefer to quit completely.  Or you accept the reality and stay.   That's very reasonable trade-off he presented to me.

Now I also asked the typical question for career, "How can I do better?", "How can I do something else 5 years later?" , "How can I make myself better fit into the dynamics of the group?"  These are very reasonable questions.  If you said something like "How can I get promoted?" or "How can I get more credit?", you are coming from the self-angle.  No one likes to listen to this kind of talk because no one like to work with someone who is selfish.

It is interesting how my manager answered.  On one hand, I believe what he tries to do is to affirm something what I know already.  i.e. Doing my business takes a long time to get promoted.   The technical path I am taking is highly competitive and not easy to be the best.  You need to be the best of the best to attain respect on certain things you say.  Many live in the world of whether "they agree" on something but that doesn't bring a person far enough.   You need to always have some technical support on your argument.  If you are fast and smart, these arguments come to your head earlier.

In a technical debate, you want to be faster and deeper to win an argument,  to be faster and deeper, you have to routinely build context of what you know on the topics.  Eventually, you also need to think creatively to come up with a thought that no one has thought about.     Thinking is a tough skill, because most of the time people don't tell you what they think.  The best way you can do is to mimic what they think and try to simulate their thinking.    You can repeat what they said, but it's more important to understand why and where they come from.  Or else, you will come from seemingly random ideas.  Creativity and Randomness of thought is always closed-calls.

That's why going technical is a deep discipline and it is difficult to master them in couple of years.  Some thinkers are hard to mimic.   The reason : they might be good at thinking, but they don't really know how they come up with their thought.

In any case, I am very convinced that it will take many years before I am considered to be good in the technical aspect.   Now, this is a very useful piece of information by itself.  If it takes so much time, it is then important to either 1) work harder, 2) admit failure and move on to something else.

Now, on the other hand, my senior manager also said that there are aspects of things I can work on.   I told him that I am reading CLRS and I told him that it improves my efficiency.   He said that's good.  Then he went on and say learning data structure will likely give me a better aspect of getting my work done faster.  It certainly doesn't make me have better idea in my field.   It also doesn't give me better chance to get promoted or do anything important.  Then he named couple of things I should work on - the code base, a knowledge in my field, data structure as well as analytic skill on data.

Indeed, those are important skills. Now, think about the beauty of the talk.  It resolved a human crisis: The "future"-type of question, whenever you ask, signified a younger member in your team are shaken about the future of the group.  It also means that there are some events in the group which make members to be unsure.   If you are good at management, those are things which you should take care.  

Let me continued, not only it resolved a crisis, it also come up with something positive such that I can work on.  How tough is that to learn the 4 aspects of things I just mentioned?  In fact, if you are bright, it will only take you a year or so.   But during the time, the group is still running smoothly.  What else is better.

So the chat was a win-win.  I don't get all the things I want but I see a path.  I also see something positive to work on.  It takes my manager sometime, but he got a closure which at least sometime I will not go to bug him the "future"-question.   Then he also resolve a human problem in the group.  Very smart.

Now, the third thing I thought about is why did I get a win-win in this case?  Well, because I have been prepared and I have a good will .  In general, this is where you start a conversation in the first place, you prepared and think through other people's perspective before you go on talking.    This is third thing I learned.  

At the end, do I agree with what my manager said? Not really but I think he handles it well. Difficult talk is, a skill, but a definite must have in your life.
33_P



Thursday, October 27, 2011

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.




Wednesday, October 26, 2011

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.

Sunday, October 23, 2011

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.

Saturday, October 22, 2011

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.

Wednesday, October 19, 2011

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

Thursday, October 13, 2011

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.

Wednesday, October 5, 2011

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

Sunday, October 2, 2011

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

Wednesday, September 28, 2011

Something special about Java.


I am just taking another data structure class.  As it turns out, An assignment of the form
varA = varB; takes the value of varB and copies it into the location in memory given by the address of varA.  This certainly change my thought and this is a rather subtle point. 

How does this work in C?

To make a living

I have spent a lot of time to ponder on why I work as a researcher and a programmer.  You see, this is one of those fundamental questions which people try to avoid.   Yet,  once you have the answers for one of them, you have a powerful conviction in your life and many difficulties become non-issues.

In the past, my answer of working on research has a lot to do with compassion.  I truly believe that technology can benefit human being.  I still believe so.   Though in reality, humans have a lot to do with technology development and humans......  let's just say you will have your own reason to feel unhappy with them.

Then, there is innovation.  I briefly considered.  In the modern day companies though, you are probably a small part of a very big framework to do something.  When you really publish a paper, you become one of the inconsequential second authors of the paper.  Your idea is usually not being used unless it convinces people high-up.   And when it convince people's high-up, it would become their ideas(!).

Go to read Putt's Law and the Successful Technocrat, you will know what I just said it's true for every single bit.

So, not compassion, not innovation, without them also implies there is no fun as well. Ok, no fun as well...... What can we think of...?  Ah.

Money.

Yes, at the end of the day, your rational judgement of whether you should take a certain job should always boil down to optimizing money.   My job is certainly not a darling.  But I buck up because I want to make a living and pay off my house.  My boss is one of the most brain-proud person in the world and talking with him is suffocating but I always think, "This is just part of the hostile situation, I am going to think of a solution to talk with him".    Some of strategies include I would avoid social interaction with him - so I avoid the group lunch because he is always taking up the conversation token but got pissed when the token is taken from him.  This gives me the reputation of "anti-social".

I decided to take all these.  Not because I have any compassion or can be innovative about the job, but I want to make a living.  I have myself and my family to take care.

But fellows, that doesn't mean this is a compromise.   If you found that you are one of my situations, what you should do is to make sure you equipped yourself during these kind of bad time.  Here is the 5 things I do,


  • Learn: take every chance to learn.   Learn everything that can help you - work-related stuffs such as programming courses or classes, thinking-related stuffs such as Math, Physic.  Learn, Learn, Learn.  Your job sucks, you don't.   Think of how to optimize the experience if it is not the most ideal. 
  • Take control of your life.  Your job is not you.  Your employer is not really your boss.  You are. You should conduct yourself like it is a company.  A good company.  So don't crazy things when time is rough and economy is bad.  Be responsible for your life.  
  • Connect with other people: Your boss sucks it doesn't mean all of your co-workers suck.  You co-workers suck doesn't mean every one besides you suck.   Positive interaction is indeed a random event but whether you want to seek one is decided by you. 
  • See it as  problem: Don't see limitations as limitations.  See it as opportunities for you to grow as a person.  You don't always win in every life's situation.  So when life is tough, you should be in your problem solving mode - think! how should I deal with difficult people?  Treat it as a problem.  Never subscribe to the theory that "I am that kind of person and he/she are those kinds, so we can't get a long forever."  Every problem has a solution.  If you give up, then there is none. 
This is a big motivational but I think it's as every bit true as well.  Go on living, programmers and researchers.  You guys are smart group in the population.  You deserve a good life and feel happy. 

33_P

Monday, September 26, 2011

Finished HW2

Good.  Finally got one thing done and it doesn't seems to be very stressful.

I still hope to get the HW4 and 5 last year to be finished soon.  My speed of finishing the homework largely due to the fact that I have practiced.  Should do the same for HW4 and 5 as well.

Before that, let's relax.  It doesn't hurt to have some fun some time. :)

Finished 2 more exercises in homework 2.

So I only have one left.  This shouldn't be a big deal.

Fellows, don't plagiarize in programming

Unlike many, I don't think the word plagiarism is equivalent to copying.   Some copying can be good, for example, when you have a book filled with text, if you want to make another copy.  Before Gutenberg, that means you would need to create a new print to print it.   On the other, you can simply do a command cp to copy an existing file to make an copy verbatim.   Behind that mechanism, bunch of system calls were made but essentially it's just to duplicate something.   Honestly, that is a rather fascinating things. 

That's said, that means I believe there are good copying as there are bad.   I tend to believe copying in academia is bad because promoting copying could easily discredit the person who really generate the idea in the first place - as a result, not many would then be motivated in thinking of a new idea.   This is indeed the case.  A good example is the Academia in China and India.   It's not unheard of that some Universities from Mainland China copy famous research and claim that it is theirs.    The general public is relentless on pirating software and there is always a way to do so.  As a results, you seldom hear a new idea generated from a Chinese academic publication.   Many are small tweaks.   Those are actually good.   Some are plain-right copy to take care of some kind of requirements in the University.  

Ideas are the source of innovations, innovation is the source of greater efficiency.   If you kill ideas, innovation is gone, when innovation is gone, efficiency will leave you as well.   That's why in general, you would generally feel that an economy based on copying can be glimicky and shallow.  

Now, all being said, programming is not such an academic discipline.   In fact, there are moments we just have to use other people's program.  So why should you care whether you copy something from the internet?    At the end, it depends on whether you want to finish *your job* by *yourself*.   If you copied and you understand how it works, there act of copying is not much different from an act of extracting convenience.  For example, if you understand quicksort, getting a quicksort implementation will allow you to change the partition function.   If your goal is to do an experiment on different quicksort, it sorts of make no sense to implement quicksort from scratch.  

On the other hand, if you are working on a project and require you to write an algorithm from scratch but you decided to choose copy the program *without understanding it), this usually spells trouble in future.  What if you were asked to change the behavior of the program?    What if some body to extend it?  How would you take care of your job?  Those would be moments when your temporary gain in time now will cost you much time in future. 

Another point I would make is that thinking through or grok the nature of one thing, usually bring understand on the other.    What is the act of programming anyway?   All the grandiose theories aside, once you know a certain algorithm, programming is just typing.    Think about insertion sort, I spend quite a bit of time to practice how to write one. Now I can pretty much put it on paper and it will run.  Time taken? depends on my typing. Usually around 2 minutes including compilation and test.  If you know what you are doing for sure, many of your tasks would usually take you 10 minutes to write the first version of the program.    The time which is really costly is the time of debugging.    This is efficiency. 

So my friends who were directed here by Google, allow me to advise you on this.  Don't plagiarize in programming.  You are actually getting slower and slower each time when you copy programs and treat it as your work.  NOT FASTER. NOT FASTER because you hadn't learnt a single thing of the problem.  You are the one who got hurt most in the process. Not me. 

33_P

Saturday, September 24, 2011

Finished all written exercise in HW2 2011

Now it's time to work on programming problems.  It shouldn't be a big deal.

The 501-th post in Self-Study : "Why are we studying bubble sort?"

After about half a year and endless coding,  I found myself posting the 501-th post of this blog.   It's a sign of continued enthusiasm on the subject.   So I decided to write something in this occasion.

Most people I know in work and academia are brilliant.   Many of them have special skills which one would envy.   Algorithmic skills is common and it becomes some kind of source of power in conversation.   A person who can wield the correct algorithmic reasoning takes an edge in the programming well.  

In my view, algorithmic skill is different from programming skill.  In programming, you might decide not to do something deal to non-algorithmic reason.  For example,  A is a new guy and you want to give opportunity to him.  So you will pass a certain programming problem to him even though you don't know what he would do.   This reasoning is completely fine.    Though those are concerns more close to software engineering and even management.  

As algorithmic concern might not be the first consideration.  Why do we study algorithm then? In lecture 1 of the MIT open course of algorithm (SMA 5503), Prof. Charles Leiserson once asked the same questions.   His answer is quite illuminating and it boils down to this - speed of an algorithm is a kind of fundamental tradeoff of many other aspects of a program.   For example, if we want to show cutting-edge graphic, then we need to decide if the underlying algorithm is fast or not.    Leiserson believes that algorithmic performance of a program is like a currency.  Once you know the currency of a program, you can make rational decision on programs.

So this come back to the point of why we are studying bubble sort.   This is a question comes up in the class I am taking in famous extension school.    When it is brought up, a grin and certain condescension was shown to the subject.  

I don't really approve that attitude - for one there are interesting characteristics of all types of algorithms.   The written representation is a form of it.    Whether the algorithm is stupid or not is also not important, they are taught because we want to let new generation of programmer to think algorithm better.    No one would believe that in real life, one would want to use Bubblesort to run sorting given its n^2 performance in both comparison and moves.  But that doesn't mean, one shouldn't spend some time to understand its characteristic and try to learn something in it.   Theoretical interest of an algorithm should sustain one's interest of an algorithm.   If one just think programming practically, why not just skip the whole algorithmic study?

For people who are unconvinced, they should spend sometime to take a look of the sorting chapter of TAOCP.   Knuth is a well-respected figure in computer science and I always find that reading his book make me understand certain things more.  I think my linear search is refined because I read his book.  (Again, if you think this is stupid, you will be surprised on how deep linear search can be.)

This is the mindset which keeps me going as a researcher, programmer and generally a human.  I hope this is a good attitude to share with everyone of you.

33_P

Friday, September 23, 2011

Status 20110923(a)


Finished in my head : 7.2-4, 7.2-5, 7.4-2, 8.2-1, 8.3-1, 8.3-4, 18.1-1, 18.1-2, 18.2-1

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

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. 

Thursday, September 22, 2011

problem 3

There is a tricky question on mergesort on how many comparison of a small sorted array.  This is highly depends on the implementation of the merge function.  Got tripped so it's a good lesson.

Finished second problem. in HW2

Nothing to brag.

Verified first problem in HW2

Learned one thing: it is always better to trace this kind of problem on paper before you decide or say the answer out loud.

Let's move on.

Got the new HW2.

Also worked out the new written problem 1.  Still want to verify it with code.


Wednesday, September 21, 2011

Finished HW4 1a, 1b

Not very hard.  But IDS is something beyond me.

(a while later) : oops, also finished as well.

Quicksort

Just went through the quicksort.  The description is again pretty superficial.   Can't blame the lecturer because quicksort by itself could be quite technical.

There are many variations of quicksort.  The Sedgewick's variation is probably the fastest.   We probably won't go through it. 

There are one good thing about the lecture.  It puts a lot of stress on the partition function.  So one thing I learnt, as it turns out the partition function actually doesn't always divide the array to halves. (!)  It's a very good thing to know.  

Time to implement quicksort once myself.  It's something quite tricky to implement.  Also want to take a look of the analysis of quicksort as well.  Why the average case is nlogn? 

Monday, September 19, 2011

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.


Having some fun with iOS game programming

I was playing with couple of game code a friend gave me.   Small developer but certainly quite innovative and knows what they are doing.   To me, it's quite of refreshing experience.   I don't have any expectation but it makes it even better because you feel you have nothing to lose.

At this point, I am still learning tidbits which I have learned when I was in college.  Say things like sprite format, pixel design, simple event loop programming and effects.  It doesn't come together yet.  Again, it takes a while before you claim you grok something and I am still in the process of learning.

A curious thing I would put here though, game programming is very similar to machine learning.  Why is that? In both of these fields, there are many instances you will need to know a particular trick to get things going.  So being knowledgeable about programming and techniques is a must if you want to even communicate with your peers.

Another similarity is that they are both seemingly small but are deep in terms of their implications.   Both of them can be regarded as new product of human invention since (really) 70s, but we don't really understand them.  We have insights but it doesn't means we have exhausted the possible research problems.

I don't know what this will bring me as I am just trying to get something I can usefully spend my time on.  Oh well, this is probably much better than gaming or pokering. :)

Saturday, September 17, 2011

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.

Goal this weekend

* Finished HW4.
* Write up 4-3.6
* Do more on Objective-C programming.

Book Review : Greg Bear : Moving Mars

Foundation series is perhaps the first hard sci-fi series I have ever read.  I basically dig it up at random from a Barnes and Nobles.   Then I start to read it up.  That was perhaps the first time I feel probability theory and random process is probably the most important mathematical field in the world.

There are three essential hard sci-fi authors : Asimov, Clark and Heinlein.   All of their books, provided that it is penned by them, worth a read.   The Foundation series crossover with the Robot series and the Empire Series.   Clark's Space Odyssey is always a classic.  If you hadn't read Starship Trooper, Stranger in a Strange land and The Moon is the Harsh Mistress, then you probably miss a piece of your understanding in American politics.

Of course, it is quite boring to follow just one of them.   Even if you follow just the essential three.  You will find that some of the ideas were recycled quickly in their novels.   Heinlein has built a world which requires the reading to read several previous work to understand what's going on.  (That's annoying.)   And as I just mentioned, the Foundation series crossover with the Robot series.  So at the very least, you will need to know the three laws of Robotics.

The good thing about science fiction though is that the effect of a series is rather small.  Writers are very hard to get a living.  And sci-fi writers probably have even more difficult lives.   The good ones consider this effect and write to make sure the reader understand what's going on.

Still, the best concept of sci-fis seems to me always come at the first book. So in a nutshell, if you read sci-fi, try just to read a book as one book.  If you fall into the trap of buying multiple books and read them as series, you might waste a lot of cognitive load.

I move along to Greg Bear to "diversify" my reading.   Greg Bear is another name which you will hear all the time from sci-fi fans, purportedly because he is another good hard sci-fi authors and in these days hard sci-fi authors are hard to get.   They are either too technical (Gentry Lee) or they don't really understand the science.

The premise of Moving Mars is that in an alternative future, human would be able to move to Mars and there are constant political conflicts between Mars and the Earth.   At the juncture of the conflict, a scientist of Mars discovered that they can treat the universe as a computer.   Time, distance doesn't matter any more.   Dilemma in quantum theory is gone and Mars would be able to use it as a leverage against Earth.

Quite dramatic, though it is not as believable as one can see from our evidence.   So I don't consider this as a strength.  Though Bear shows his authorship by building up a great story which interleaved political conflicts and other believable scientific inventions.   For the political conflict parts, I will keep the spoilers.   For the scientific inventions, here are couple of things I think it's quite believable.

1, Enhancement: a kind of human improvement either on physical or mental ability.   The change are based altering the neuro pathway of human brains.
2, Travel on Mars:  this is again another believable ideas.

The setup of the novels are quite sophisticated and craft well.  So even though the book is a bit long (500 pages on a paperback), you still have a feeling that you want to read it on.

It took me a while to finish the book since I am more focused on algorithmic studies and languages these days but I think this book worth the while.   I will also start to read books from Bear again because I think he is a good author.









Friday, September 16, 2011

Reread Chapter 18

As it turns out Chapter 18 only less than 20 pages.  While it's still more in-depth than many discussions of balanced trees, one can see the authors are not big on this topic (like deletion is not even described and left for the author).

In any case,  though the algorithm is more difficult than a binary tree.  It is much easier to understand than red-black tree.  More importantly - it is simpler to visualize what really going on.  So I decide to skip the algorithmic description for the moment.


Finally upload the first App into my IPod!

It's certainly not as difficult as I thought.   Though it is more a tedious process.

Now I finally get to the part which I can really play with.  So what should I do?   The person who gave me this program specify two issues he wants to improve.   I guess I will first work on them first.

Thursday, September 15, 2011

The tougher class

I took a look.  It is more challenging but if I work hard and take it as my only class.  I believe that I can work it out.

Taking another class with it would be a separate problem.  That probably won't be what I'll do next semester anyway.

B-tree and 2-3 tree

Now I see.

As it turns out the operation of B-tree is probably much simpler than red-black tree. (In a way I think RB tree is actually more advanced).

You can also gauge the difficulty of the class by how much it discuss balanced trees.  In fact, most of the time, you will only see cursory description of them like insertion in an introductory class.

This is good.  That means if I review Chapter 16, I will probably know how to do all the problems in HW4.

status 20110915(b)


Reread Chapter 12 and Chapter 13. Finished in my head : 12.2-5,12.3-{2-4}, P12-1a, 13.2-2

Browse reading: 813/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,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. 

Reread Chapter 12 and 13 again

After rereading the chapter on binary search tree (Chapter 12), I think I finally grok deletion. In fact there are two non-trivial issues of binary search tree, one is to find a successor node when the right node is empty.  (In that case, you are always look for an ancestor whose left child is also an ancestor of the node.

The other is in deletion of a node with two child nodes, you always want to delete the tree-minimum of the right sub tree.  Once these two issues are thought through, you understand all operations of binary trees. (The others are more like simple recursive thinking).

Another good news is that I also reread red-black tree, this time, it starts to make sense on why we have this funny color fix-up algorithm.    The most important is to visualize the two different cases where the red-black properties should be handled.   I don't really grok at this point but I think I understand way more. It is super-complicated but it's also how the thing should work.   I stopped at deletion because it is even more complicated.

It's funny to see the whole business of building a balanced tree is so difficult.  This read is good.  I also finished in my head some exercises.

Wednesday, September 14, 2011

Bad looking situation in homeworks

Hmm, it sounds like I need to work a bit harder.  I also have a Spanish class on late September.  Of course, if I can't finish all things by then.  I won't enjoy my Spanish class as much. 

Let's hope to finish HW4 and HW5 within this week.

Lectures note for HW4

Hmm, here comes a tougher part,  issues such as binary tree, balanced trees such as 2-3 trees and B-tree are tougher to understand topic.   Ok, this is a good time to really understand them though.  It also related to my reading in CLRS Chapter 12 and Chapter 13.


Stuck in getting provisional profile in IOS development.....

While I have momentum, I will go ahead to do it right.

Okay, also finished the last exercise

It's time to move on to homework 4 then.

Need to read up Shell sort again

In lecture, we just talked about Shell.  Of course, the treatment is rather elementary.  I would probably spend some quality time to understand Knuth's description.

Coded up the last problem of Homework 3

It is another rather simple problem.  Though of course, testing it will be another story.

Sounds like I finished the second HW

It turns out it's not very difficult and with the right syntax the code actually makes a lot of sense.

33_P

Finished coding of the second homework in HW3

Coding seems to be fairly simple.  But I am not entirely sure how to use the iterator() function well enough.  So I think compilation might take me some time.

status 20110914(a)


Browsed Chapter 30,31 and 32. Finished in my head : P30-1(a,b), P30-2b, 30-1.1, 31-1.{1-7}, 32.1-1, 32.1-2

Browse reading: 813/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, 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. 

Tuesday, September 13, 2011

Some fun with iPhone development

As a way to stimulate my brain, I am developing my capability on writing iOS applications.  This should be fun because it is stretching my comfort zone.  

So far, I have successfully write a Hello World app and put it through an iPhone simulator.  Though it is much more difficult to get it run it on a device.  (Ask my fellow iOS developer.)

That will also mean I need to get myself fairly proficient in Objective-C.  I am confident that this will not be as difficult as Java. 

Chapter 30, 31 and 32

I browse read through Chapter 30 on integer multiplication, Chapter 31 on number theoretic algorithm and Chapter 32 on strings matching.   Those are topics I have some exposure so browsing through them is not particularly difficult.

One surprise : Karp-Rabin algorithm.  I am surprised to see string manipulation is related to integer algorithm.  Ah I guess when you think of it - what's not related to theory of number then?

A nice tetris exercise

This is an interesting exercise I might want to do as I meant to do more things in game programming anyway.  Let's play with it when I have time.


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.

Monday, September 12, 2011

Let's stop for a while and do some light reading

It took around an hour to finish the first exercise.  I probably need another two to finish the next two.   So I want to take a break first.

Changed detailed description of the blog

I have just made a change in the detailed description of this blog. So far, appealing to audience is not my key concern.  In a way, I am still struggling in going through the fundamentals of algorithms......

Life is a bit slow for me lately.   Sometimes I would have the following dark thought - I would think solving a little recurrence relationship probably won't help me in my career too much.   This is an illusion based simply on greed and impatience.  Learning a subject in either Math or Computer Science is always an epic struggle, no matter what you are learning.

In my own field, I have struggled for many years without getting my peers or my supervisors approval.  Then I realized my search has been too narrow.  Computers doesn't serve just on things like machine learning.  There are wide varieties of applications which are interesting and improve human's life.

The betterment of human's life is my true concern and life's goal.  What is better if your skill can make other people feel happy?  That's why we write game, we automate things, we attempt to control other objects, we engineer.

So I changed my description, I no longer just want to read the book CLRS.  I hope that my story of struggle and growth in the process of reading (which is well-known to be hard) can be beneficial to other people.

HW2 : Alternative implementation of multiset using Linked List

This is certainly not difficult. Though it will take some time to fill in the 8 functions supposedly used in the Bag's interface. In real life, you are always filling in functions anyway. I guess I have nothing to complain.

Partial finished exercise 1

There are some methods weren't exposed in the code yet. They are not that difficult to mock up but I guess I start to realize my weakness in linkedlist. It is mainly an issue of how to get the initialization condition right. I need to be a bit mindful on these issues. It's ok to move on though. I found that exercise which requires implementing a certain interface is actually more useful.

Let's move on to the programming problems

Today's goal is to finish them. It shouldn't be too difficult to do. One thing for sure. After that I want to make sure I check the written problems' answer. This will buy me a lot of milage later on. Before that I might do some light reading first.

Sunday, September 11, 2011

Last problem....

Hmm, that is a little bit tricky. I need to think through how to reverse a doubly linked list elegantly. Currently I use 5 assignment . Should it be less? All written homework should be regarded as finished. Though I have a shaky feeling. Let's code up some of them and test whether my idea is correct.

Finished Ex 4 of HW3

Is that correct? I think the pop and push function certainly do. But I am not sure about the peek function.

Finished exercises 1-3 in HW3

To be safe, it's better to check the answer by setting up some faked examples. I plan to do it *after* I finished the programming exercises.

HW4

Also looked ahead at homework 4. It is more involved because it will take some time to absorb material such as heap. When i think about this, may be I should think through how the data structure in HW3 works. A detail thinking of each function.

Blogger can be very annoying to use

The recent change of the editing tool doesn't really help the problem that sometime the program simply switch the font without letting the users know. This is quite annoying in general

HW3 - first look

I took a look of HW3 - Ah.  It is not as difficult as I thought.  As it turns out, there are some code required in the program which wasn't exposed.  Once look at it, the whole thing makes sense.

Ok.  Let's take a break, then I will start to play with it.

Today's goal

After working on the lecture notes and tutorial for a while.  I think I am confident on how it should be done. Let's try to finish all written exercises of HW3 today.

33_P

HW3 last year

I took a look of homework 3 last year.  It is mainly problems in linked list and implementation problem.

It is reasonable as linked list is an important data structure.  So I guess it makes sense for me to spend some reasonable amount of time on it before I move on to homework 4 and 5.

In general, I also feel I am not very comfortable with linked list.  This always take practice.

Finished and Submitted HW1

After some small changes on the code. I finally submitted the homework.  Of course, I will remind myself to always refine the code if I got any new requirements.

Ok. Let's head back to HW1

After some rest last week, I think it's time to refine HW1 and make it to a state which can be submitted.  I also hope to start HW3.  It's just time!

Half a year of self-study - what did I learn?

I spent last half a year just to read a single book and finish 2.5 chapters of the exercises.  If I told myself this half a year ago, I would think I am crazy.

Of course, now I think different.   It is a good textbook and I found that reading it taught me many things.  The major change is this - I see algorithm and programming differently.

In the past, I would probably just go to copy an algorithm.  Now most of the time I will think about how to solve a problem first before I do anything.   The thinking time could be as short as 10 seconds or can be as long as 1 - 2 hour.

Should I go on? Absolutely yes.  Learning is always one big grinding process.  It always reward the patience.

In last half a year, I also learn one more thing : it's not just trying to work in a bigger company, it is a matter of whether you getting skills to improve your career.    My honest reason to start doing all sort of data structure learning is because I want to get a better job.   But now, after reading glassdoor though,  that illusion is gone.  It might still be a good thing to get a job in big company but the goal is no longer that it is a better job.   More than likely, it is a worse or a similarly bad job as what you are working on.

But why do I still keep on learning Data Structure?  Here is the answer, it is something that you can use in many facets of computer science.   If you want to start up, you need to have better skill in Data structure.  If you want to go back to academia, you need to have better skill in Data structure as well.   If you want to get promoted in your company, your skill of Data structure will also count.   If you are in a deadend, why not finish your job faster and do something else quickly?

That's the mind set, don't give up, my fellow.   Your job may be a deadend, but your career is most certainly not.

Saturday, September 10, 2011

Your Programming Jobs : a realistic look

It is tempting to think other grass is always greener.   Life is not that easy.   While I sometime feel utmost dissatisfied with my job, I do find that it could be equally tough to survive in other companies which could be highly competitive as well.

So before you decide to leave, think this through - have you done researches on other companies and make sure that they are *better*.    This type of research, in my case, not only I find that companies I admired could have poor employee's satisfaction.  They might be poorer  than or equally difficult to work in as your current company.   

A good site could be glassdoor.com which I found an amazing amount of insight could be found from the current employees of a place.   Go ahead to look at big names company, you will see that universal satisfaction is usually an illusion created deliberately. 

Your programming job : your current job and your future ones

It's always a big problem to decide working environment.  I seldom feel life should be job-based.  I always think life should more like project-based.  If you feel you like to do something - you move on to do them. 

Of course, it is not uncommon to have situation where you don't like your current project.  Then you would like to move on.   It's a very reasonable way to think about it.   Though it's important to understand, by itself, resignation could be a tough undertaking - It is a delicate situation, you certainly didn't like a certain place for a reason.   Though those are not moments to trash other people because you know that you might be working with the same sets of people all the time.   It's also moment which open to issues such as counteroffers.  

In short, always try to be professional on every task you do - For example, take resignation as a task.  How would you take this task seriously and do a good job on it?  When I consider situations I need to leave a place, I will replace all my emotions on the job by this set of cool, objective questions. 

Friday, September 9, 2011

Looked at a bunch of programming interview questions

I told myself : "I am getting there.  not yet. closed.  I am just getting there. Be patient."

Creativity and Society

When you are a creative person, the biggest pain in life would be someone disallows you to do anything creative and constructive for the world.   That's a big waste of a person's time and life.

The biggest sin of one human being is to waste other human beings' time.  That's why unemployment is a social problem and bureaucracy is despicable.

It is a real sin for anyone try to impose their view to other people.  That's why we humans have a universal feeling where only one opinion, only one thought, only one religion or only one philosophy is not right.   Because every man is entitled to their own opinion, their own thought, their own religion and their own philosophy. This should be an explicit boundary.  No human being should cross it.  We just let too many people to cross this boundary......

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.

First read of Chapter 28 and 29

Browsed read Chapter 28, matrix multiplication and Chapter 29, linear programming.   Both of these topics are deeper than a chapter.  Though CLRS description is probably deeper than an usual programming book . It is also complete in the sense that it solves the major problem in those two domains.

Both of these two chapters have many practical applications.  This is a bit unlike the other chapters : I don't think I will ever use algorithms in number theory, computational geometry and integer multiplication.

A meaningful browse read is to build/re-build  connections between seemingly unrelated concepts.  Currently, I feel satisfied with that level of understanding.   As each of the advanced topic is probably a book, I won't push myself too much to really digest them.

Status 20110909(a)


Browsed Chapter 28 , 29.

Browse reading: 813/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, 22-1.{1-3,6,7}, 23.1-1 and 23.1-3, 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. 

Lecture on Wednesday

After an exhausting Wednesday, I decided to take a good rest on Thursday.

I am glad that I went to the lecture because it taught me new things.   As I mentioned, I was able to finish the homework in a day though I am curious about the backtracking problem - how come the heuristic is so fast?  As it turns out,  what it does is to accelerate the search such that it reach to the constraints faster.

This is a good insight.  If one devise a search, the key is to always make it work with an optimizing criterion sooner such that some paths can be pruned out.   Simple insight but it's highly useful.


I also learned that I am not allowed to use POJOs in the homework.  Bummer, this won't kill me, though I might need to spend some time with the homework and revise  -  it's expected though, after all it is a graduate course.

Wednesday, September 7, 2011

Archived another homework

Again, this is a pretty time consuming process.  Luckily, I decide not to archive programming question so the load is lower.  Though it still take time to cut and paste.

One more to go and I will start to work out homework 3 of last year.

Another thought about studying CLRS

Hmm. When I think about this, this is probably a point I said it couple of times.   But you come to think of it, it should be trivial.

Normally, you read a textbook in order to take a course, but for a book like CLRS, you actually take a course in order to read the textbook.   The former is the mindset for students, undergrad or grad alike, who want to get good grades from a class, getting good GPA and so on and so forth.   In real life : it's equivalent to "meaningless".

The latter is the mindset for practitioner who want to refine the skill and push it to a certain extreme.   That, again, is probably the reason why not many people are willing to read the CLRS as a book.

status 20110907(a)


Browsed Chapter 25 to 27,  finished the sink problem in my head : Ex 22-1.6.

Browse reading: 813/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, 22-1.{1-3,6,7}, 23.1-1 and 23.1-3, 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. 

Chapter25, 26 and 27

Browsed read Chapter 25, All Pairs Shortest Path Problem, 26, Maximum Flow Problem and 27, Multithread algorithms.  I don't really grok any of them but it makes me fairly excited to read on them.  In fact, it is not necessary to have previous background on 25 and 26, you can simply start to read them if you feel interested.   This taught me couple of interesting thought - you can resolve seemingly difficult problem such as shortest path problem to a cheaper alternatives.   You can also model bipartite matching with maximum flow problem.  

I feel similarly to the multithreaded algorithm chapter.   Though I don't really grok but I feel it is very exciting to learn that you can analyze a multithread program with a simple sprawn/parrallel model.   Even if the shared model is not the trend in future, I would probably still want to learn this by heart first.   Because when you think about this, what is better when you learn something and you know that they won't change?

Again, these are fairly exciting read.  I also start to see connections of earlier chapters to these advanced topics.  In fact, one can imagine the most important chapter is perhaps the dynamic programming chapter.  Once you understand that, all the graph theoretic derivation will start to make sense.

Tuesday, September 6, 2011

I should move on to homework 3

Today I am pretty much taking rest.   Working out 3 problem sets is quite a bit of load to my head.   Though finishing exercises past year give me a very good idea how to proceed on the material this year.

At this point I still need to archive HW2 last year and HW1 this year.   Though I hope this can be done sooner, if I understood the material earlier, I will feel more comfortable in this year homework and the class. 

Mistakes I made in undergraduate years

One of my bad habits during the undergraduate years is to skip lecture.    You can't blame me, 9 a.m. lecture is quite a drag.    The basic course are okay but you can't do this on advanced courses.  They are usually too difficult to skip.

I have no such illusion in famous extension school.   I will take every section I could take.  Go to every lecture I could go.   I simply want to immerse in the class this time.

Shene's book

Flipping Shene's book "Selected Well-Known Problems" is probably the only must-have algorithm book in the Chinese-speaking world.  (In case you don't know, yes I speak Chinese.)


I bought the book around 12 years ago during my Master.  It's the first book which makes me feel interested in algorithmic study in the first place.  It's format is unique.   It is not a text book but it extracts famous problem and their latest development.  


Prof. Shene is also a big fan of digital camera and principle.  Way to go!  I am going to read the book again from Chapter 7 to Chapter 9.  After that I would have finish a round of browse read. 



Solved the sink problem with complexity n

It's also known as the celebrity problem.   The question is who is the one in a party who is known by other people but no one knows him?

It turns out that there is O(n) solution for this problem.  (The n^2 solution is rather trivial) I was able to think it through.

Good.  Sounds like I can check away another problem of CLRS.

Archived first homework last year

It took me a while (1 to 1.5 hour) to stuff all my answers on my notebook.  Oh well. I guess this is just the way it is.

How difficult is CLRS?

While I started this reading project 6 months ago, one question has always been in my mind - how difficult is to read CLRS?

My background is not straightly from computer science.  The first few comments I heard is that "it is impossible to read CLRS as a book." .  

Yet during my reading, I have stumbled upon several individuals who tried to the similar things as I do.  That is to deep read the whole book once -> i.e. browse, read, finish all the exercises and (optional) research.  

None of them really finish such a feat (nor I would claim I come closed) but many of them can finish couple of chapters with what I consider as correct answers. 

If they can do it, how come most cannot?    I am not inclined to blame talent as the reason  because I always think if you are not talented, you can simply learn better.  

When I start a course in famous extension school, CLRS is listed in two advanced Data Structure courses.  They are in two different topics.   Then I start to realize what really happens.  

      CLRS is probably not difficult but it will take almost 6-7 graduate courses to cover the whole book. 

And of course, most do not have the time to take 1-2 graduate courses because they can be very time-consuming.  And time is precisely what many people perceive they have little. 

But bear that in mind, CLRS is completely readable if you are used to read Mathematical text and long books. (If you are not, are you really a programmer?), the rest is just patience and persistence. 



Status 20110906(a)


Finished Chapter 23 and 24.  Finished in my head: 23.1-1,23.1-3. Consciously decided to skip Chapter 19 and 20 Move my reading pointers for 185 pages.  Now at Chapter 25.

Browse reading: 685/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, 22-1.{1-3,7}, 23.1-1 and 23.1-3, 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 in Chapter 19 and Chapter 20

After a month long of lacking of momentum, I decided to skip both Chapter 19 and Chapter 20 in my reading.
Both of these topics require very solid understanding of the basic data structures.  I only have some understanding but they are not solid.  So I will skip it for now.

Does it really affect my further reading? I don't think so. Fibonacci heap is ok because it is mostly used in implementing priority queue.  I have no idea how Van de Boa trees would be used.  I guess for that reason, I don't have too much trouble to read through the graph algorithms chapters.

That will also mean I will have a 2nd browse read.  What does that mean?  After I "browse" the book once.  I will restart browsing from the chapter I hadn't do any exercises yet and start to reread from there.    For me, that would be Chapter 5.  As I already know many got stuck in the first few chapters, so the fact that I can restart from Chapter 5 means I am upgraded from the time I first start in March.

Alright, it's time to update the status.

Chapter 23 and Chapter 24

Browsed read both Chapter 23, Minimum Spanning Tree, and Chapter 24, shortest path.  If you don't know, you would think that minimum spanning tree is a tougher problem.  In fact, due the structure of the problem, you can claim it is easier.

The graph chapters seems to be more familiar to me.  I guess that's because I have always working with graphs anyway.

I got to admit though, after the advanced data structure chapters, the book is more like seminar book rather than a text book.   There are multiple topics which are suitable to use in a graduate courses rather than in an undergraduate course.   That makes the original MIT courseware amazing because most of the students are probably in their 20s or even teens when they go through those courses.  From guys of MIT, I heard that it is a very tough course even in MIT.   Though I would say the worst students will probably be some programmers.