Hi everyone. I know this should be posted on a forum devoted to Algorithms, but it seems like there aren't many of them out there. Anyhow, here are my questions. I am taking a graduate level course in Design and Analysis of Algorithms this semester and I pulled a real hard ass of a professor, the kind you pray you don’t get for a class like Algorithms but which if you are unlucky enough to get it will be in just such a course. The good thing is that, unlike one of the first professors I tried taking my undergraduate level course in Algorithms with, who was also a real hard ass and I had to drop the class with in favor of another professor teaching the course, this guy has been teaching for quite sometime and knows how to lecture effectively and keep it as simple as possible while still getting the idea across to students. The guy I tried taking that undergraduate level Algorithms class with was like 27 and already teaching at a major university as a Computer Science professor with a PhD, but had like 1 year of experience teaching so he really hadn’t figured out by that time how best to teach students and the book he chose for the course absolutely bit ass. Hasn’t “Introduction to Algorithms” by Cormen, Leiserson, Rivest, and Stein been like the defacto text to teach out of for both undergraduate and graduate level Algorithms courses at universities for some time now? Anyhow, I was wondering if some of you guys could direct me to some really good resources when it comes to learning not only how best to studying algorithms that are already out there, but how best to approach the problem of coming up with algorithms of your own, showing with a iron clad proof that they will work in all cases, and showing that they will work optimally in every case as well. I am fairly good at studying and learning algorithms that are already out there but I am very much lacking when it comes to taking one I have come up with for solving some problem and showing that will work in all cases and do so optimally every time as well. I know this forum is a good place to come for help with things like this, and there are other forums I plan on going to online as well asking the same questions about how best to approach this stuff in general. I am also going to read various articles online and text written by computer scientists, my books of course such as the text for this class and Knuth’s books, and I will even get on youtube as you can actually find some fairly good videos tutoring people in all kinds of things which had never occurred to me until recently. I even found some videos on there not too long ago showing how to derive Maxwell’s Equations for Electromagnetism. Pretty cool in fact. But, anyhow, if some of you could help me out with advice from your own experience on how best to approach learning how to prove out your own algorithms and how best to better learn ones currently in use that you may not understand 100% and direct me to some other really good resources both on and offline for that kind of stuff I would appreciate it. Thanks in advance for all of your help.
6 Replies  1319 Views  Last Post: 19 September 2013  09:37 AM
#1
How Best To Learn How To Develop Algorithms In General
Posted 18 September 2013  11:59 AM
Replies To: How Best To Learn How To Develop Algorithms In General
#2
Re: How Best To Learn How To Develop Algorithms In General
Posted 18 September 2013  12:33 PM
Care to use paragraphs, or just list out what questions you have?
#3
Re: How Best To Learn How To Develop Algorithms In General
Posted 18 September 2013  06:59 PM
The whole point of taking an Algorithm Analysis class is to learn about things like this. There isn't a magic formula for just plopping and proving algorithms. If so, we all would be out of a job pretty quickly.
We do have pinned resource threads you should look at:
CS Book Suggestions
Strategies for Proof Writing
We do have pinned resource threads you should look at:
CS Book Suggestions
Strategies for Proof Writing
#4
Re: How Best To Learn How To Develop Algorithms In General
Posted 18 September 2013  08:57 PM
There is no algorithm for writing algorithms. Coming up with new algorithms requires practice, and practice will develop your intuition to help you tackle new unfamiliar problems. Same thing goes for writing proofs. As for learning and practice, of course Introduction to algorithms is a must. You can use it to learn new concepts and solve the exercises in every chapter. For more practice, you can check out online judges like spoj, topcoder and codefores. There are many more online judges, and you can google them.
#5
Re: How Best To Learn How To Develop Algorithms In General
Posted 19 September 2013  07:15 AM
I also highly, highly, highly recommend getting yourself a copy of The Algorithm Design Manual. It's starting to get a bit dated, but the core concepts about how to examine, think, and then extrapolate your own algorithms if existing ones don't exist are timeless. The latter half of the book is a survey of problem spaces and algorithms typically applied to them.
#6
Re: How Best To Learn How To Develop Algorithms In General
Posted 19 September 2013  08:49 AM
I second Skiena's Algorithm Design Manual. The first half is general information about algorithms with how to think about them and how to apply them. The second half is a reference manual for common problems. War stories are scattered throughout which put it all in perspective. Utterly brilliant. At one point, there were three copies floating around our office.
#7
Re: How Best To Learn How To Develop Algorithms In General
Posted 19 September 2013  09:37 AM
Developing algorithms is sort of what programming is, informally at least. At some point, you are confronted with a problem you haven't solved before, and you develop a solution for it that you hope is correct and complete, and you do your best to reassure yourself that it is both. On the other hand, most programmers don't actually do formal algorithm design, in terms of solving globally novel problems and producing a paper formally proving the solution to be correct  if for no other reason than that can take years, and generally the time frame for realworld problems is "yesterday". So I'm not sure which of these is closer to what you're interested in  do you want to have a procedure with your name on it, or are you thinking more about writing guaranteed errorfree code?
That being said, it sounds to me like there are a few things you could usefully do:
 review existing algorithms. Go through CLRS and Sedgewick and implement everything, do all the exercises, suck every drop out of those books that you can. There's probably stuff you missed the first time through. You might also think about running through Roughgarden's course on Coursera  he seems to have an interesting approach, at least it's quite different to the one I got when I took DS&A. Having done that, there's a bit of material in Knuth that might be interesting.
 review the math. Presumably you've got the basics. So go deeper  go back to your discrete math textbook and find some results that grabbed you the first time around, and see if you can dig into them a bit further. Number theory, combinatorics, set theory  all of these provide a lot of mathematical background for algorithmic proofs. Go play, see what you can learn. That will give you some stuff to work with. Two books that might be fun: "Proofs From the Book" and "Algorithmic Number Theory, vol. 1" (there is no vol. 2)
 exercise your knowledge. Obviously, you should be working through the euler project and rosalind.info problem sets.
 teach someone what you know. You don't have to go out and become a professor, but explaining stuff like this really helps to cement your understanding of it, and also tends to reveal interesting areas of ignorance that you can remedy. You can hire out as a tutor, or just help out your fellow students, or hang out on DIC and jump in on any algorithms questions that come up.
 practice. Find problems and solve them, and prove your solutions correct. Post them here and ask for feedback  there are a few folks here who would probably jump on a chance to tear your algorithm apart, and they can help you make it a little more bulletproof.
That being said, it sounds to me like there are a few things you could usefully do:
 review existing algorithms. Go through CLRS and Sedgewick and implement everything, do all the exercises, suck every drop out of those books that you can. There's probably stuff you missed the first time through. You might also think about running through Roughgarden's course on Coursera  he seems to have an interesting approach, at least it's quite different to the one I got when I took DS&A. Having done that, there's a bit of material in Knuth that might be interesting.
 review the math. Presumably you've got the basics. So go deeper  go back to your discrete math textbook and find some results that grabbed you the first time around, and see if you can dig into them a bit further. Number theory, combinatorics, set theory  all of these provide a lot of mathematical background for algorithmic proofs. Go play, see what you can learn. That will give you some stuff to work with. Two books that might be fun: "Proofs From the Book" and "Algorithmic Number Theory, vol. 1" (there is no vol. 2)
 exercise your knowledge. Obviously, you should be working through the euler project and rosalind.info problem sets.
 teach someone what you know. You don't have to go out and become a professor, but explaining stuff like this really helps to cement your understanding of it, and also tends to reveal interesting areas of ignorance that you can remedy. You can hire out as a tutor, or just help out your fellow students, or hang out on DIC and jump in on any algorithms questions that come up.
 practice. Find problems and solve them, and prove your solutions correct. Post them here and ask for feedback  there are a few folks here who would probably jump on a chance to tear your algorithm apart, and they can help you make it a little more bulletproof.
Page 1 of 1
