Chapter 34 NP-Completeness

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

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

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

Some thought on Chapter 34

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

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

33_P

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.