<p>I think courses on <em>algorithm design</em> and <em>computational complexity</em> 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!</p>

<p>I found that I got to know about "the way" most (when I first start my graduate study) by reading and doing exercises from <a href="http://rads.stackoverflow.com/amzn/click/0534950973" rel="nofollow">Sipser's book</a>. 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. </p>

<p>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! </p>

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

<ul>
<li>The very readable and beautiful book <a href="http://www.cs.berkeley.edu/~vazirani/algorithms/all.pdf" rel="nofollow">Algorithms</a> by by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani.</li>
<li>The killer <a href="http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/" rel="nofollow">notes</a> (or book draft) by Jeff Erickson. (Since JeffE is too modest to suggest his own notes, I have to do it myself.)</li>
</ul>

<p>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.</p>

CC BY-SA 2.5
2011-01-01T20:43:28.373Z
+1 for Jeff's killer notes. I always enjoy reading them. The Arabic calligraphy of the word Algorithm is very beautiful.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-01-01T19:17:56.297Z
2013-11-01T00:45:51.017Z
2013-11-01T00:45:51.017Z
Dai Le
<p>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. </p>

<p>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. </p>

<p>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?</p>

<p>Our course will be using the standard text: Introduction to Algorithms by CLRS.</p>

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

<p>Thanks to everyone,</p>

<p>Jason Dane</p>

CC BY-SA 2.5
2010-12-31T17:21:39.760Z
I suggest taking a look at [this post](http://cstheory.stackexchange.com/questions/3253/what-books-should-everyone-read/3262#3262). I specially suggest Udi Manber's book.
Sadeq Dousti
CC BY-SA 2.5
2011-01-01T06:38:58.407Z
This discussion on StackOverflow offers several suggestions: http://stackoverflow.com/questions/2256721/good-book-for-thinking-in-terms-of-algorithms
Jeffε
CC BY-SA 2.5
2011-01-01T06:41:11.790Z
I second the Manber recommendation.  Also check out *How to Think about Algorithms* by Jeff Edmonds: http://www.amazon.com/Think-About-Algorithms-Jeff-Edmonds/dp/0521614104
Jeffε
CC BY-SA 2.5
2011-01-01T20:13:59.990Z
*"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
CC BY-SA 2.5
2011-01-04T22:33:29.943Z
Step one: stop giving straight answers and refer to other's solutions instead. ;)
Raphael
CC BY-SA 3.0
2012-11-19T20:09:40.693Z
1. Learn how to program. 
2. Participate in programming competitions.
Pratik Deoghare
<cc.complexity-theory><ds.algorithms><soft-question><advice-request><research-practice>
Algorithms Design and Complexity - How to think in that 'way'?
Jason Dane
# Algorithms Design and Complexity - How to think in that 'way'?

(Asked by: username_0 on 2010-12-31)

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,

username_0

**Tags:** cc.complexity-theory, ds.algorithms, soft-question, advice-request, research-practice

> **Comments:**
> **username_1**: I suggest taking a look at [this post](http://cstheory.stackexchange.com/questions/3253/what-books-should-everyone-read/3262#3262). I specially suggest Udi Manber's book.  
> **username_2**: This discussion on StackOverflow offers several suggestions: http://stackoverflow.com/questions/2256721/good-book-for-thinking-in-terms-of-algorithms  
> **username_2**: I second the Manber recommendation.  Also check out *How to Think about Algorithms* by Jeff Edmonds: http://www.amazon.com/Think-About-Algorithms-Jeff-Edmonds/dp/0521614104  
> **username_3**: *"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?  
> **username_4**: Step one: stop giving straight answers and refer to other's solutions instead. ;)  
> **username_5**: 1. Learn how to program.  2. Participate in programming competitions.  

---

## 1 answers

### Answer by username_6 on 2011-01-01. Score: 18

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](http://rads.stackoverflow.com/amzn/click/0534950973). 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](http://www.cs.berkeley.edu/~vazirani/algorithms/all.pdf) by by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani.
* The killer [notes](http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/) (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.

> **Comments:**
> **username_7**: +1 for Jeff's killer notes. I always enjoy reading them. The Arabic calligraphy of the word Algorithm is very beautiful.  

---

