Algorithms Design and Complexity - How to think in that 'way'?

Question

My question is a general one: How do I start thinking in terms of Algorithm Design and Complexity? I am going to take a Graduate Course in Algorithm Design. I had enrolled in it earlier but dropped it later because I could not keep up with it. I have to take this course as a requirement.

Is there a 'trick' to think in this way? I know this is putting it quite crudely but sometimes a fresh perspective helps to think about a subject differently.

The main problem I have with this course (and similar theoretical courses) is: How do I know that solutions that I come up with are correct? I find the theoretical part to be arbitrary especially when 'proving' a certain algorithm acts or behaves in a certain way?

Our course will be using the standard text: Introduction to Algorithms by CLRS.

Are there any textbooks/sites/books/etc. that might offer a way in becoming confident in this field?

Thanks to everyone,

Jason Dane

Answer 1

I think courses on algorithm design and computational complexity are always challenging for students who not familiar with these subjects because they do require some degree of mathematical maturity and problem solving skill. In my first graduate course on "computational complexity", a friend of mine who had his degree in pure mathematics told me how surprised he was by the fact that although that course didn't require much maths background (at least that's what was told in the course outline), it actually required nearly all the skills he got through all of his pure maths undergrad degree!

I found that I got to know about "the way" most (when I first start my graduate study) by reading and doing exercises from Sipser's book. Be sure that you do the exercises because problem solving skill and mathematical maturity is what you want to learn and not just a bunch of facts or definitions.

However, Sipser's book is only good for complexity and NP-completeness stuffs, it won't suffice to substitute the CLRS book. The only problem with CLRS book is that its advantage of comprehensive coverage might become its weakness since the book might look quite scary or overwhelming for students. So my advice is that you should really go to the library and search for books on algorithms, scan through one by one and choose the ones that fit your thinking pattern most. And again don't forget to do exercises!

For algorithms, I personally suggest the following books (besides the ones suggested by Sadeq and JeffE):

• The very readable and beautiful book Algorithms by by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani.
• The killer notes (or book draft) by Jeff Erickson. (Since JeffE is too modest to suggest his own notes, I have to do it myself.)

In general, whenever you study a certain algorithm or data structure, if somehow the exposition in your textbook is not clear enough for you, then the best way is to search on google for lecture notes of that particular topic. In may cases, different explanations of the same thing eventually give you the complete picture. At least, that's how it works for me.