Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
I suggest taking a look at this post. I specially suggest Udi Manber's book. –  Sadeq Dousti Dec 31 '10 at 17:21
1  
This discussion on StackOverflow offers several suggestions: stackoverflow.com/questions/2256721/… –  JɛffE Jan 1 '11 at 6:38
1  
I second the Manber recommendation. Also check out How to Think about Algorithms by Jeff Edmonds: amazon.com/Think-About-Algorithms-Jeff-Edmonds/dp/0521614104 –  JɛffE Jan 1 '11 at 6:41
    
"How do I know that solutions that I come up with are correct?" Do you mean that (1) you came up with an algorithm but don't know how to prove that it is correct, or (2) you have have a proof but you are not sure if it is correct? –  Jukka Suomela Jan 1 '11 at 20:13
    
Step one: stop giving straight answers and refer to other's solutions instead. ;) –  Raphael Jan 4 '11 at 22:33

1 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.

share|improve this answer
7  
+1 for Jeff's killer notes. I always enjoy reading them. The Arabic calligraphy of the word Algorithm is very beautiful. –  Mohammad Al-Turkistany Jan 1 '11 at 20:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.