status 20110621

Finished reading Chapter 16 on greedy algorithms.  I can understand activity scheduling and the knapsack problems.  It's also very illuminating. But I got to admit relating them with dynamic programming and matroid theory is currently beyond me. 

My conclusion is this - for this chapter and chapter 15 on dynamic programming.  It's very important to understand how the problems are related.  Though I know how to implement the algorithms, without understanding them, it's hard to go beyond the superficial.  

For now, I will leave it to my another reread.

Browse reading: 450/1144
Exercises up to 4-1.3(finished the brute force implementation)

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.1-5, 4.2-6, 4.2-7, 4.3-{1,2,4,5,6}, The whole Section 4.4, 4.5-1, P4.4(a-c), P4.6b, 5.1-{1,2}, whole Section 6.1, 6.2-{1,2,4,5,6}, 6.3-1, whole Section 7.1, 7.2-{1-3}, whole Section 7.3 and 7.4.3, 10.1-6, 10.1-7, 12.1-{1,2,4} 12.2-{2.3}, 12.4-4, P12.4(a), 15-1.1, 15.1-3, 15.3-3, 15.5, A.1-{1,2,3,4,5,7},  C.1-{2,4,5,7,8,9,14}, C.2-{1,2,4,5}, C.3-{1,2,10}, all in D.1. and D.2-2

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. 

status 20110607

Finished in my head 15-1.3 and 15-3.3

Fuzzy reading: 414/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), 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

CLRS Chapter 15: Dynamic Programming (2nd read)

After more detail read, this time I start to realize the core of this chapter.  It is actually not that important to understand 1000 algorithms which is based on DP. Rather it is important to understand why a problem is a DP and why it is not.  So, the heart of this chapter is actually Chapter 15.3 and I found the examples about unweighted shortest simple path and unweighted longest simple path are the most illuminating.

The key of knowing when you can applying DP (which I frankly feel blurry sometimes) is that you want to know whether there is relationship between a problem and its subproblem.   You also want to know whether the subproblem is being repeatedly solved.  Both can be observed by looking at how a big problem is solved in the first place.

It's also important to understand when will a problem will become intractable polynomially. 

I think I am good for this read.  All of the examples are interesting and currently I have a feel on the rod cutting problem as well as matrix multiplication problem.  The key of these types of problem is to think through the solution yourself and try to come up with the solution.  I guess what I will add now is to always think through the problem dependency tree as well as the structure of the subproblems.

status 20110606(b)

Fuzzy read till P.414. Finished in my head 15-1.1 and 15-1.5.

Fuzzy reading: 414/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), 15-1.1, 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

CLRS Chapter 15: Dynamic Programming

I wish I read this chapter before I learn all the dynamic programming algorithms in my field.  There is a very good discussion on when one should consider using DP and Greedy algorithm and one shouldn't.

I grok the rod-cutting problem.  Though the other problems require a bit more understanding.  I think I will go back to read the matrix multiplication problem if I reread this chapter.

I consider this chapter as highly important because many of the practical algorithms are either DP or greedy algorithm.  So it is a good thing to think through why they were used and how they should be used.

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

Status 20110605(a)

Fuzzy Read till Chapter 15.   The part about Red-Black Tree is a little bit too tough to absorb in one shot.  So I decide to work on it later. DP, greedy algorithm happen to be used in my work a lot.  So Chapter 15 and 16 will likely give me a break. What I want to focus though is the underlying theory of these material.   CLRS is likely the best text book out there which talks about these stuffs.  (Or we have to wait till the whole V4 and V5 of TAOCP to be published......)

This reminds me, may be I should buy a copy of TAOCP V4 soon.

Fuzzy reading: 339/1144 (Until the beginning of Chapter 15 for 2nd Edition.)
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-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