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

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

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

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. 

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.

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? 

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

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.

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.

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.

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. 

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.

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.

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.

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. 

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.

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.

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.

What's next?

I was thinking about this during trip home.   I guess I am a bit tired after finishing 3 sets of problems.   The truth is I may be doing this too quickly.

So, what I hope is to make sure this experience worthwhile.   It is not just a matter of getting good grade and bragging right.   Programming by itself is fun.  It is like Math but you can do something to get it better.

That's why I am thinking I might halt working on homework 3 for a while.   Before that, I will first put all the answers of the exercises in my notebook.    This gives me some time to reflect on the material.

Finished the whole homework

Amazing, finished the whole homework within a day! That's awesome.  I have a lot of fun with it.  So let's go home and jot down all the notes into my notebook.  That move back to homework 3.

I am very impressed by a heuristic used in one of the exercises.  Got to go ask the lecturer why it works so well.

Finished design and code up of number 3.

It still takes me around 2 hours for this problem involving backtracking.  Indeed.  It takes more mentality to make sure the data structure is applied correctly.

So , let's debug it.

Finished Question 2 in the Programming Question

Again, this is faster.  It's probably because I am more familiar with the Java String class.

Also, just found out that Java String class is actually inmutable.

Finished Problem 1 again in HW1

Nothing much, this time it took only 15 minutes to debug.  Again, it is an improvement.

Coded up Programming Problem 1 again

This time there is a significant improvement in terms of time.   Mainly because I am more familiar with a lot of Java class.

Completed New written exercises for new Homework 1

It took around 2 hours.  I think this is fair enough.

I have changed......

In the past, if I knew the homework set has changed, I would be so unhappy.  I would curse the instructor why he/she couldn't just stick to the old syllabus.

I have changed.   Now I see programming as a life time career.   Although I tried to avoid doing programming at work (because it's a waste of time), I do hope that I can use programming to do a lot of fascinating thing that enriched everybody's life (me included).

With that line of thinking, who cares about the 20 hours were used?  It is a good use of time because this 20 hours will mean a lot for me as a programmer.  How would I know more Java before this 20 hours? How would I know backtracking before this 20 hours.

In ZAMM, Prisig discussed education systems.  And how come a motorcycle technicians will eventually be interested in deeper knowledge such as Mathematics and Mechanics.    The answer is he no longer feel satisfied by the shallow knowledge shown to him by cheap manuals and folklorish wisdom.   He become something actively accept and reflect on how he can do better.

This is everything bit as philosophical as one goes to reflect on problems such as why life exists, why do we live or whether there is another being exists in the world.  In fact, this active absorption of knowledge may by itself, make us humans as we are.

Today

Let's try to solve all written problems in the morning and all programming problems in the afternoon.

In fact.....

I should still go ahead to work on old problem set 3.   If I am not prepared, chances are I will take me up to 20 hours to finish problems after set 3.

I will try the following schedule.
1, Finish the homework this year.
2, Try to finish all homeworks last year.
3, Go back to work on CLRS.

This is all set then, I have no need to start another class now.

Does it worth the time to do the past exercises?

I think so.  It is repeated a little bit but I teach you something about the nature of programming.   Sometimes you don't do things because of grade.  You just try to learn something.   The biggest thing I learn is backtracking which is pretty interesting technique.  Now I can wield it to solve some problems I couldn't solve in the past.

I might simply go ahead to redo HW1.  Let's see whether I can finish it by 5 today.

Uh-oh

Need to redo all the exercises.  As it turns out there is a new version of the homework.  Not dramatically different but the answer will be very different.  So if I was using the old version of the homework, I will have no score.

Not all is lost.  Experience helps.  See if I can finish the first homework today then.  I will also skip the last experimental problem of second homework and go forward to the third.

Shell Bubble sort

Just finished an interesting variants (from homework) on shell bubble sort.  Unfortunately I cannot report on this due to the fact it is homework.  But there are certainly many interesting characteristic.

The last exercise require me to run the code couple of times to gather data.  This is quite interesting.  Let's keep it interesting and draw some curves or something.

Finish another question in HW2.

Pretty simple.  It only takes around an hour.  Ah I really don't like to use Java primitive array.  It is not as nifty as the built in data structure such as ArrayList.

After last exercise

I start to feel mildly tired.  Compare to CLRS, the course is on the simpler side.   There are two courses which are more advanced in the famous extension school.    Despite the problems are simpler, they are more tedious and take more time to resolve.   To me, it is a test of patience and endurance.  The truth is in real life, I don't usually like to think of a problem to its ends.   In my work, I simply hope to finish of the work due to the fact the task is not so motivating.

It takes time, I tell myself.  And indeed, it takes time.    But I tend to believe I have certain degree of talent as well.   So I think this chunk of time is well spent. 

My goal is still to finish HW2 today and work out the rest of the problem set in the rest of next week.   I don't think I can make it before Thursday (so I can do late registration for other courses) but I can certainly try.

This fall......

If things work out fine, I might consider to take another course this fall.  Of course, there is an assumption - I need to finish the homework by Friday next week.  This test my skills in Java.  But it shouldn't be super tough neither.

For the course, I am thinking of another Java or a C class.  The programming would be more challenging so let's see how goes.    I can certainly use the on-line option if I want to.

If I couldn't, oh well, let it be.  I can't be too overly aggressive anyway.

Finished the first programming question in HW2.

It is actually CLRS 2.3.7.  I have done it before (oops! but that's not cheating. :) )   So I vaguely remember the solution.  I found that when I merged the array.  I wasn't using the smartest method though. I should be only merging half of the array.  But how, I still haven't figured out yet.  I will probably do it later instead.

Hmm.  This question takes me a while to solve.  If I can use the binary search solution, I should be able to solve it in 2 hours.  Oh well, I follow the rules.

Let's decide on Thursday.....

If I can finish the homework by then.  Well, let's if it's possible first.......  I hate to over-commit too much.

Should I do more?

Nah.  Keep my bed time at 12.  It doesn't really worth it to burn out for the homework.  I guess the toughest homework will be homework 5 and the course project.  Given my pace, I am thinking one week will be a conservative estimate of when I can finish them all.  So it doesn't seem to be a tough deal.

Of course, I will hope that no one yell that they find they can also find the future homework.  If that is the case, I am pretty sure the future homework will change and I need to do it again.

No matter what I think I am in good shape.  Let's read a novel and probably crash the bar.

My expectation tomorrow

I should be able to finish homework 2 by the end of tomorrow.

Is homework 3 difficult?  I don't think so.  Not until homework 4, I am still working on something I know quite well.   Not by heart for sure, but know quite well already.  With the aid of computer, most of the problems can be easily resolved. 

So I will aim at finishing at least half of homework 3 as well.   Of course, that assumes I will have a break at night.

Finished written problems of homework 2

A breeze, none of them are very difficult.   It does take a few hours to get them right but it's still a good refresher of what I learned in the past.

Questions related to sorting

Nice. Finished the first question about sorting.  As expected, some questions trip me.   There are two reasons, 1 is that the implementation of the lecture could be different from mine.  So I need to study the algorithm a bit before I can decide.  Second is that some algorithm is intrinsically tricky to think through.  For example, quicksort and mergesort are two sorts which take some serious time to consider.

But oh well, this is nice because it gives me some insight to some existing sorts which I thought I know (such as selection, insertion, bubble) and some new sort (such as quicksort and radixsort).

Sorting algorithms from the basic Data Structure course

I spent around 30 minutes to take a look.  It is quite cursory.  Also the goal is to mainly bring up the students on the knowledge of the big O notation.  Of course, you also won't expect there is anything difficult other than just mentioned the basic definition of Oh and Theta.

Bubblesort is using power of 2 which is a bad practice.  Whereas quicksort is not using Sedgewick's implementation.   So one can expect the learning is rather amateurish.

Of course, that is my goal for now. I just hope to finish the class.

Finished homework set 1

Good.  I only need some polishing to get it submitted.    It shouldn't be too tough.

There are interesting question from this assignment.  Mainly on how to calculate the square root of a number.  I might want to post a note here.

courses

I spent some time to look at the courses in the class.  There are certainly many things I am interested to learn.   I also look ahead what I should take in next semester.

My thought at this point: To help my work and my reading in CLRS, I might go ahead to take both a Discrete Mathematics class as well as Linux/Unix programming class.   The Linux/Unix Programming class could be heavy for me.   But the discrete Mathematics class is likely something I can go through on top of the programming class.

They also count as part of the coursework - Ah.... what a nonsense, who are these people to decide what a "degree" is?   But oh well, I will play along.   After I start working, I always remind myself: always treasure the time you can learn something for free.   Learning is expensive and not every time you have a chance to learn something without paying a huge chunk of money.

My goal today

Finish the first set of homework.  Then move on to the next and complete half of them.

My homework

I decided to make it a policy, always try to submit after I hear all the materials from the lecturer and the teaching assistants.  In that way, I will learn what other people think before commit to a solution.

Given that there is not much change in the first homework, I might go ahead to finish at least another one during the weekend and hopefully the rest in the next week.   Then I will only need to take care of the test and exam. (Hopefully)

The whole home work 1 is posted.....

Looks like I hit the Jackpot.  I can simply work on the last year problem.   There should be a high similarity.

This will also buy me some time.  After all, my goal is to work on CLRS.

Finished the 3rd problem.

Pretty easy once you understand the concept.

*Also try to write a program to solve N-queen problem.
*Also try to write a program which solve 4 number operation problems.

Recursive Backtracking Revisited

After going through the notes on recursive backtracking, I have a much better idea on how to solve the third homework problem.  As it turns out it is not a super hard problem.

There is a template of backtracking and it looks like this in this not so right CLRS pseudo

FindSolution(X):
    if X is valid solution:
          return true
   else
          return false
   for value you want to scan
         if the solution is valid
              putValue on the state space.
              if(FindSolution (f(X))
                     return true
              removeValue from the state space.
   return false

The lecture note use an example from N-queen to discuss this problem which is fairly interesting.  I was quickly able to adapt the template to make my solution.

Let's implement and see if it works.

Status 20110902(b)

Finished in my head: 22-1.{1-3,6}

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

Chapter 22 : Elementary Graph Algorithms

I quickly browse this chapter and turns out to be highly useful.  Now I learned the basic of another highly used graph representation : adjacency list.  

I also thought through some problems.   What it bugs me now is that I don't fully grok basic things such as BFS, DFS and topological sort is - I guess that makes sense, when I learn those things, they are all presented in the context of AI or machine learning.  It is hard that those presentations are very fundamental. 

What it fascinates me now is how generic of these methods and what they can achieve - that is way more interesting than AI or machine learning. 

Status 20110902(a)

Back-record : Finish 4-4.4.  Finished in my head: 21-1.1 and 21-1.2.

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

Chapter 21 : Disjoint Set

Quickly browse it once.  Except Chapter 21.4 which involved the proof of union rank heuristics, it is not a very difficult chapter to read.

I like this, may be I will read in leisure of the chapters in graph as well.  There are around 20% of the Data Structure required understanding of the graph algorithms.

Multiset Implementation

In the lecture of the Data Structure class, a concept called multiset was suggested.  Currently, we are still at the stage of using an array to implement.  But of course, there are obvious issue with this approach.

This could be an interesting problem, what does CLRS and TAOCP suggested on this?  May be  I should take a look.

Recursive-Backtracking

Take a look of the lecture notes.  It doesn't seem to be too difficult.  But oh well, I am done for today.  Let's go to sleep first and work on the rest of the problems.

Solved another HW problem

Things work out.  It took a while to finish another homework problem.  But it's generally enjoyable experience.

Starting from now, I will probably jot down tip on Java such that my life will be easier next time.  Tidbit on things like how String function should be written should be committed to either my memory or some convenient note.

There is only 1 more question to go.  It requires understanding a technique called recursive backtracking.  This is a little bit different from just recursion.  So I wonder what the term means in this class.  

Time to take a break.  I will work on the problem sets again tomorrow.

Some notes on my java implementations

I will undoubtedly rewrite a lot of stuffs in Java during the Data Structure class in the famous extension school.   I would hope to just post the code here because it benefits all other people.  But of course, I also want to avoid the situation where some body suspect I copied my code in the class in case they see this blog.

So my take is this, I will probably just post code when I finish a class.  In any case, that will take some organization anyway.

A sudden feeling

I suddenly feel I am quite elated with the simple questions I solved in the Data Structure class for the famous extension school.   Famous extension school is famous because its programs are one of the top of the world.  But famous extension school is still a worthwhile place to study for a moment because it charges a large sum of fee for courses.   Studying there may not be the most-valued thing in the world but the education is decent.   You can think of its graduate program as at least in the top of the 2nd tier.

Some of its graduate exhibit a trait which I dislike : that is to claim they are graduated from the university itself.   But extension school is still an extension school.  Its quality is still poorer than the core.  It's pretentious to claim you graduate from the core which only a few very talented can do. So I always refer it to the "extension school" because I don't like to brat with the name.

In such a context, being able to finish the homework with ease is a pretty encouraging thing.   That might mean I might really able to apply jobs in some Big shots company.   But well, let's wait and see.  Programming skill is something it takes time to refine.


Another interesting feeling I have when I walked home is that programming could be something fun and interesting.  Unlike work in my job which is dull and super-uncreative, a lot of programming tasks are artistic and challenging.  This makes me feel happy about my choice to admit to the famous extension school.   It really adds something positive to my life and balances out my rather s*ty work life.

First programming exercise from the class

It takes around 1-2.5 hours to finish the first programming exercises.  I will say mainly it's because of the setup time.  But other than that, it's no biggy.  I think the 10-20 hour estimates per week is not a bad one from the course instructor.  If one is not experienced with Java, it will take a little bit more time. Strictly speaking, I am not that great neither. But things working reasonably well.

I might want to spend time to put experience of Java into this place as well.  I hope to make sure I learned something during the process.

First homework assignment

It didn't arrive yet but I was able to search for the last year assignment using Google.  I tried my hands on the written questions.  Of course, they are just a breeze.   Once you can finish CLRS Chapter 2 to 4.  You are way more powerful to solve basic programming problems. 

Java is also pretty nice to use when testing algorithm.  It is also elegant in the way I don't need to implement my algorithm with static array which is kind of ugly. 

There are totally 5 assignments and there is a programming project after that.  I guess my first goal is to finish all assignments first.  As the difficulty is fairly low.  This should take me around 40-60 hours to finish them. 

After finishing the first class

Refreshing.  Though I know that its level is probably not as good as the MIT course, I still feel benefited from the interaction.

The extension course was a basic introduction to simple data structure.  But underneath that, it also teaches Java.  For example, one of the key thing that I learned is how stack frames were represented in the stack and it is nice to see how things were represented neatly in the stack/heap diagram.

The course also taught me Java and I want to take advantages on it.  It is a good idea to keep up with the most popular programming language.

I have great expectation with this relearning process.  There are many course in this famous extension school are very valuable.   For starter, the mobile and web programming courses will be very useful.

My goal though is still trying to work out the whole CLRS.  It is more daunting than 1 to probably up to 3 university class.