Shortcut for chapter specific information

Showing posts with label chapter3. Show all posts
Showing posts with label chapter3. Show all posts

Thursday, September 1, 2011

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. 

Thursday, August 4, 2011

Fixed Erratas from Chapter 1 to 4

After learning my lessons from 4-3.8.  I decided to fix errata from time to time to make sure I got the right learning from the book.   I will probably do this every time I start a chapter.

Friday, July 1, 2011

Chapter3 (Read 1)

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

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

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

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

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

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

I believe this view is wrong.  Why?

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

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

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

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

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

Thursday, June 9, 2011

After Chapter 3

Chapter 3 and Chapter 4 are closely related.  So it is a no brainer to start Chapter 4 right after Chapter 3.  In fact, to keep up the momentum, I might just finish one exercise tonight to make sure I move on.  There are indeed many funny things to learn.

One afterthought on Chapter 3.  Chapter 3 impresses me in two ways: one is the amount of Math need in algorithm.  The other is what kind of Math is really useful.   The most important type of Math required in Computer Science is Discrete Mathematics.   It is certain that deep knowledge of Probability, Statistics and Combinatorics certainly help.  But they are not as crucial as understanding the underlying structure of a program (and deeper the argument which leads to a new program).  My deepening routine (Read 3) on this part would be to read CMath 2, 3 and 9 and TAOCP 1.2 deeply.  I feel like this can be done any time I like even when I am not seriously reading those two books.   It is just a relaxing thing to do when you want a problem to solve at night.

I expect I should be able to cruise through Chapter 4 as quick as Chapter 3. But I expect a lot of resistance in Chapter 5.   Probabilistic reasoning is never something easy to grasp.

Finally finished all exercises in Chapter 3

Though there are couple of exercises I don't fully get through.  This is a very Math-heavy chapter. So I sort of expect there are couple of exercises will get me.

Math for computer science has an interesting property.  You can learn it to an arbitrary depth.  You can also learn it just a bit to get by.  The engineering aspect of algorithm will make you think you don't need any Math to get by. 

What is a similar situation?  One good one is whether you need to learn all difficult English words to read.   Do you need to learn the word silhouette to read? Do you need to learn the latin origin of every word before you can read? 

Certainly not.  But this knowledge helps subtly.  It helps when you try to look deeper. 

In any case, learning more in the Big Oh perhaps only give me marginal gain.  CMath and TAOCP 1.2.1 are perhaps the books I can read to deepen my knowledge on this part (They are fun books to read anyway).

Status 20110609(c)

Finished P3-6.  Ah. finally finished all the exercises of Chapter 3!  

Fuzzy reading: 414/1144
Browse reading: 309/1144
Exercises up to P4-1.1
Needs write up: P2.1c, 3-2.4, 3-2.8, P3.1
Exercises which are finished but not on paper: 1.1-2, 1.2-2, 1.2-3, P1-1, 4.3-{1,2,4,5,6}, The whole Section 4.4, 4.5-1, P4.4(a-c), 5.1-{1,2}, 6.1-{1,2,3,7}, 6.2-3, 6.2-4, 10.1-6, 10.1-7, 12.1-{1,2,4} 12.2-{2.3}, 12.4-4, P12.4(a), 15-1.1, 15.1-3, 15.3-3, 15.5, A.1-{1,2,3,4,5,7},  C.1-{2,4,5,7,8,9,14}, C.2-{1,2,4,5}, C.3-{1,2,10}, all in D.1. and D.2-2

Status 20110609(b)

Finished on paper the whole P3-5. (a) took me some extra thinking.  I gave a fishy answer but don't want to dwell on it for too long.

Fuzzy reading: 414/1144
Browse reading: 309/1144
Exercises up to P3.5 (a)
Needs write up: P2.1c, 3-2.4, 3-2.8, P3.1
Exercises which are finished but not on paper: 1.1-2, 1.2-2, 1.2-3, P1-1, P3-6, 4.3-{1,2,4,5,6}, The whole Section 4.4, 4.5-1, P4.4(a-c), 5.1-{1,2}, 6.1-{1,2,3,7}, 6.2-3, 6.2-4, 10.1-6, 10.1-7, 12.1-{1,2,4} 12.2-{2.3}, 12.4-4, P12.4(a), 15-1.1, 15.1-3, 15.3-3, 15.5, A.1-{1,2,3,4,5,7},  C.1-{2,4,5,7,8,9,14}, C.2-{1,2,4,5}, C.3-{1,2,10}, all in D.1. and D.2-2

status 20110609

Finished on paper the whole P3-4.  Some of the exercises can be easily solved once my head is relaxed.

Fuzzy reading: 414/1144
Browse reading: 309/1144
Exercises up to P3.5 (a)
Needs write up: P2.1c, 3-2.4, 3-2.8, P3.1
Exercises which are finished but not on paper: 1.1-2, 1.2-2, 1.2-3, P1-1, P3-{5,6}, 4.3-{1,2,4,5,6}, The whole Section 4.4, 4.5-1, P4.4(a-c), 5.1-{1,2}, 6.1-{1,2,3,7}, 6.2-3, 6.2-4, 10.1-6, 10.1-7, 12.1-{1,2,4} 12.2-{2.3}, 12.4-4, P12.4(a), 15-1.1, 15.1-3, 15.3-3, 15.5, A.1-{1,2,3,4,5,7},  C.1-{2,4,5,7,8,9,14}, C.2-{1,2,4,5}, C.3-{1,2,10}, all in D.1. and D.2-2

I am going to move on in Chapter 3 today

I stopped two days.  Tuesday for a library trip. Wednesday for cooking.  There are also something good going on at work (unusual).  So I am sort of justified to be a bit late.

I am also perhaps a bit stumbled on P3.4.  A bit mesmerized by dynamic programming.   Now I know how much I don't understand it.  Ah, it always take some time to grok. 

Monday, June 6, 2011

Status 20110606(a)

Finished P3.3.  I have thought through the problem so it is not that difficult.  Also updated Fuzzy Reading pointer to Chapter 15. I read Chapter14 but it seems to be very specific to red-black tree. Probably one of the toughest subject in the book.
Fuzzy reading: 360/1144
Browse reading: 309/1144
Exercises up to P3.4 (a)
Needs write up: P2.1c, 3-2.4, 3-2.8, P3.1
Exercises which are finished but not on paper: 1.1-2, 1.2-2, 1.2-3, P1-1, P3-3, P3-4{a,c,d,e,f}, P3.5d, P3.6, 4.3-{1,2,4,5,6} , Section 4.4 4.5-1, P4.4(a-c), 5.1-{1,2}, 6.1-{1,2,3,7}, 6.2-3, 6.2-4, 10.1-6, 10.1-7, 12.1-{1,2,4} 12.2-{2.3}, 12.4-4, P12.4(a), 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

Saturday, June 4, 2011

Plan on Chapter 3

I am going to go through the whole Chapter 3 by Monday. (Tomorrow: I want to prepare a presentation for my Spanish class.)  I have finished most of the exercises.  Some are notably more difficult but I think I have closure with them.  It's a good time to move on.  I am also excited by the prospect of moving towards Chapter 4. Working on summation is always fun for me.

status 20110604(e)

Finished 4-3.1 in my head. 

Fuzzy reading: 339/1144
Browse reading: 309/1144
Exercises up to P3.3
Needs write up: P2.1c, 3-2.4, 3-2.8, P3.1
Exercises which are finished but not on paper: 1.1-2, 1.2-2, 1.2-3, P1-1, P3-1, P3.2(b,d-f), P3-4{a,c,d,e,f}, P3.5d, P3.6, 4.3-1, 4.5-1, P4.4(a-c), 5.1-{1,2}, 6.1-{1,2,3,7}, 6.2-3, 6.2-4, 10.1-6, 10.1-7, 12.1-{1,2,4} 12.2-{2.3}, 12.4-4, P12.4(a), A.1-{1,2,3,5,7}, C.1-{2,4,5,7,8,9,14}, C.2-{1,2,4,5}, C.3-{1,2,10}, all in D.1. and D.2-2

Status 20110604(d)

Finished P3.5(a-c) in my head.  With the right frame of mind, this few exercises are fun to solve and mind provoking. 
 
Fuzzy reading: 339/1144
Browse reading: 309/1144
Exercises up to P3.3
Needs write up: P2.1c, 3-2.4, 3-2.8, P3.1
Exercises which are finished but not on paper: 1.1-2, 1.2-2, 1.2-3, P1-1, P3-1, P3.2(b,d-f), P3-4{a,c,d,e,f}, P3.5d, P3.6, 4.5-1, P4.4(a-c), 5.1-{1,2}, 6.1-{1,2,3,7}, 6.2-3, 6.2-4, 10.1-6, 10.1-7, 12.1-{1,2,4} 12.2-{2.3}, 12.4-4, P12.4(a), A.1-{1,2,3,5,7}, C.1-{2,4,5,7,8,9,14}, C.2-{1,2,4,5}, C.3-{1,2,10}, all in D.1. and D.2-2

Status 20110604(c)

Finished P3.3(a) on rough papers, finished P3.3(b) in my head.  (a) is not entirely trivial but well taking log always help.
 
Fuzzy reading: 339/1144
Browse reading: 309/1144
Exercises up to P3.3
Needs write up: P2.1c, 3-2.4, 3-2.8, P3.1
Exercises which are finished but not on paper: 1.1-2, 1.2-2, 1.2-3, P1-1, P3-1, P3.2(b,d-f), P3-4{a,c,d,e,f}, P3.5d, P3.6, 4.5-1, P4.4(a-c), 5.1-{1,2}, 6.1-{1,2,3,7}, 6.2-3, 6.2-4, 10.1-6, 10.1-7, 12.1-{1,2,4} 12.2-{2.3}, 12.4-4, P12.4(a), A.1-{1,2,3,5,7}, C.1-{2,4,5,7,8,9,14}, C.2-{1,2,4,5}, C.3-{1,2,10}, all in D.1. and D.2-2

Status 20110604 (b)

Finished P3.2. A breeze compared to P3.1 (if you want to solve it right).
 
Fuzzy reading: 339/1144
Browse reading: 309/1144
Exercises up to P3.3
Needs write up: P2.1c, 3-2.4, 3-2.8, P3.1
Exercises which are finished but not on paper: 1.1-2, 1.2-2, 1.2-3, P1-1, P3-1, P3.2(b,d-f), P3-4{a,c,d,e,f}, P3.5d, P3.6, 4.5-1, P4.4(a-c), 5.1-{1,2}, 6.1-{1,2,3,7}, 6.2-3, 6.2-4, 10.1-6, 10.1-7, 12.1-{1,2,4} 12.2-{2.3}, 12.4-4, P12.4(a), A.1-{1,2,3,5,7}, C.1-{2,4,5,7,8,9,14}, C.2-{1,2,4,5}, C.3-{1,2,10}, all in D.1. and D.2-2

Status 20110604

Refinished P3.1(a,b) and finished P3.1(c,d). I am going to let e goes for now because I couldn't work out the inequalities correctly. P3.1 needs a write up, it's not as trivial as I solved it in my head.
 
Fuzzy reading: 339/1144
Browse reading: 309/1144
Exercises up to P3.2
Needs write up: 3-2.4, 3-2.8, P2.1c, P3.1
Exercises which are finished but not on paper: 1.1-2, 1.2-2, 1.2-3, P1-1, P3-1, P3.2(b,d-f), P3-4{a,c,d,e,f}, P3.5d, P3.6, 4.5-1, P4.4(a-c), 5.1-{1,2}, 6.1-{1,2,3,7}, 6.2-3, 6.2-4, 10.1-6, 10.1-7, 12.1-{1,2,4} 12.2-{2.3}, 12.4-4, P12.4(a), A.1-{1,2,3,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.

Friday, June 3, 2011

P.46 of CLRS (3rd ed.)

To think through P3.1, I decided to go back and read P.46 carefully.  You might notice that at the bottom of the page there is a proof of why ax^2 +bx+c is formally Theta(x^2).  The fun part about this kind of proof is not the proof itself.  It's usually why the author construct such a proof.  I spend some time to think it through and the construction is very cute. 

This is very helpful, I think I can finally solve P3.1(c) correctly.

Thursday, June 2, 2011

Theta for polynomial

Ah, now I realized I made a mistake in the proof of 3-1.2 and P3.1.  My choice of c1, c2 and n was simply wrong. 

It is actually not that trivial.  Good.   Though I am confident that I know the answers when all coefficients are positive and the exponents are positive.  That's a good start.  Let's consider it again when I wake up.

status 20110602 (c)

Finished P3.1(b), it takes a bit more energy to think through when the equality sign should hold.  Small thing but that's what it matters most.
Fuzzy reading: 339/1144
Browse reading: 309/1144
Exercises up to P3.1(c)
Needs write up: 3-2.4, 3-2.8, P2.1c
Exercises which are finished but not on paper: 1.1-2, 1.2-2, 1.2-3, P1-1, P3-1, P3.2(b,d-f), P3-4{a,c,d,e,f}, P3.5d, P3.6, 4.5-1, P4.4(a-c), 5.1-{1,2}, 6.1-{1,2,3,7}, 6.2-3, 6.2-4, 10.1-6, 10.1-7, 12.1-{1,2,4} 12.2-{2.3}, 12.4-4, P12.4(a), A.1-{1,2,3,5,7}, C.1-{2,4,5,7,8,9,14}, C.2-{1,2,4,5}, C.3-{1,2,10}, all in D.1. and D.2-2.

status 20110602 (b)

Finished P3.5(d) and P3.6 in my head, It's sort of tough to establish a bound for P3.6(h) but I guess I have a reasonable idea.

Ok. I simply just want to move on from this point on.
 
Fuzzy reading: 339/1144
Browse reading: 309/1144
Exercises up to P3.1(b)
Needs write up: 3-2.4, 3-2.8, P2.1c
Exercises which are finished but not on paper: 1.1-2, 1.2-2, 1.2-3, P1-1, P3-1, P3.2(b,d-f), P3-4{a,c,d,e,f}, P3.5d, P3.6, 4.5-1, P4.4(a-c), 5.1-{1,2}, 6.1-{1,2,3,7}, 6.2-3, 6.2-4, 10.1-6, 10.1-7, 12.1-{1,2,4} 12.2-{2.3}, 12.4-4, P12.4(a), A.1-{1,2,3,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.