...the 50 algorithms that every programmer should know.
Enough with the "everyone should know everything". I have had a fairly long and successful career as a software developer and I don't know half that stuff off the top of my head. I think it's important to know that they exist and where to look for them, but very few developers really need this on a day to day basis.
People in the education business have incentives to increase what we should learn from them, rather than learn by doing. :-) Education is very useful, but I scratch my head about the size of some of these lists.
Some of these algorithms (eg. Knuth Shuffle) are implemented using Java's Random, as is their StdRandom helper class. While they do state their assumptions, I think it's worth making the point that java.util.Random has traditionally been a pretty poor RNG (it was a simple 48 bit linear congruential generator with some appallingly non-random behaviour in the least significant bits). It might be better in Java 7 - I haven't looked. Anyone doing serious work with RNGs eg. for Monte Carlo sims would be advised to go elsewhere. I'm not talking about secure RNGs - that's a different ball game. Anyone doing crypto with java.util.Random has gone FAR beyond von Neumanns 'state of sin' ...
As the documentation for Random says: "Instances of java.util.Random are not cryptographically secure. Consider instead using java.security.SecureRandom to get a cryptographically secure pseudo-random number generator for use by security-sensitive applications."
I have always found it intriguing how Java has been the language of choice to teach Algorithms and Data Structures in many universities.
I thought it was important to understand how the computer perceives these algorithms and data structures, thus making C a much better language to learn these topics. I've found learning that way much more enlightening.
I took Data Structures in C, before Java became popular in colleges, and I personally felt like we got bogged down in the implementation. Most of the time was spent chasing down missing asterisks and debugging seg faults.
> I thought it was important to understand how the computer perceives these algorithms and data structures, thus making C a much better language
As for algorithms wouldn't Python, Ruby or Scheme be better?
I found that frustrating in my CS algorithms classes. I spent more time fighting with templates, pointers and segfaults than actually learning the algorithms. And no it didn't teach me to be a better C++ and Java programmers, as they didn't bother teaching design principles in those courses. All that was learnt in a separate course or an in labs.
Java, for better or worse, is also the language of choice for most developer jobs outside of the valley. Learning C is great for understanding how software operates, but doesn't add much value to your resume.
I think using C for everything is overkill. At some point keeping track of low level details stops being enlightening and just becomes a PITA.
I'm biased, but I think my university took a good approach. In one class sophomore year we had to implement Quicksort and some other algorithms in MIPS assembly language. The rest of our classes used Java or whatever else was installed on the Linux machines in the computer lab. It let us see what was going on under the hood without the tedium of having to do it for everything.
My intro course used Modula/2. (Many years ago) We were less focused on the computer interaction (memory) than algorithmic complexity (Big O notation). This doesn't mean one method is better or worse, just what we used. The advanced algorithm coursework was all about proofs, and and had no programming.
Well usually its either Algorithms course or Analysis of algorithms course. The latter, I presume is the one that you had to take, thus giving more importance to the computations over the implementation, I suppose.
MIX again is cool. The more lower level the language is, the better you understand the algorithm. Scheme maybe not so much. DS&Algo is one of the important things that need to be taught in low level languages.
I don't think that is what my experience taught me. Writing in Scheme got to the heart of the algorithms part much faster than MIX. With MIX I spent much more time trying to get syntax correctness than understanding what I was doing.
Further doing these things in Scheme has had long lasting benefits when I need to work in a functional programming space. In my experience, going from functional to imperative was easy, my colleagues that had to go the other way seem to struggle more.
That said, some data structures & some algos need to be written at a very low level to understand why standard Big O algo analysis can occasionally lead you astray. But I don't think they all need to be.
I disagree: the higher level the language, the better one can focus on the algorithm itself rather than getting bogged down in irrelevant details or language-specific details.
For example, being able to swap by doing "a, b = b, a" in python allows one to focus on the rest of the algorithm rather than getting bogged down in: "temp = a; a = b; b = temp". Generally speaking, the more lines of code the harder it is to see what the code is doing.
I would be more impressed if detailed pseudo code was published as that would help someone writing in a different language and would guarantee you actually learn the algorithms; now the code might as well be copy/pasted or blindly translated.
It's why I'm liking the Stanford Algorithms course[1] being taught by Tim Roughgarden: it's all pseudocode. I thought about taking the Princeton one being taught by Bob Sedgewick (author of the book you're linking to), but I don't really know Java very well and don't have a pressing need to learn it right away. The pseudocode approach has so far been great to get this self-taught programmer thinking at a higher level.
I preferred Bob Sedgewick's because of the emphasis on coding techniques which ultimately proved to be much useful for coding interviews. Having taken a course similar to Analysis of Algorithms, I felt the strong emphasis on the theoretical aspects of Big Oh to be cumbersome and did not contribute as directly to my ability to answer technical questions as compared to Sedgewick's approach which covers examples of sorting through animations and looking primarily at his Java code.
The Tim Roughgarden course is Analysis of Algorithms, and hence it deals a great deal with the complexity and mathematics with the algorithm and leaves implementation only to the pseudocode level while Bob Sedgewicks Algorithms course is more related to explanation and implementation of the algorithms, hence the dependency on language.
I've signed up for both and pretty fun both seem to me.
I think this will be a great resource for those participating in the ACM-ICPC competitions. A nice collection of all the standard algorithms and data structures that one should be able to implement in a heartbeat.
Can anyone recommend a good book for experienced developers to learn java from? I've done work in Obj C, JavaScript and Ruby. I initially had little interest in java but there are a lot of coursera classes that assume familiarity with it.
Basically, I'm looking for a book that doesn't spend chapters telling me what variables, loops and functions are.
If you're conversant in Javascript and Ruby, you know most of the hard parts of Java already. Find a normal Java book, read the chapter about generics, and you'll be fine.
I've read a number of algorithms books. CLRS, Skiena's Algorithm Design Manual, Algorithms and Data Structures in Python, and Sedgewicks' own Algos in C and Algos in Java.
This book (simply called "Algorithms") is the most lucid of them.
For someone learning today, I would recommend Algorithms and the Skiena book.
I'd love to know which of those algorithms still make sense in Python/Ruby/Javascript, or if their runtimes are slow that you would never, for example, implementing sorting in Python.
In other words: why do implement sorting in Java but not in Python/JS?
In Java, you should almost always use the standard sort, which I believe is Timsort these days. This book is written in Java mostly because that's what CS students know, not because it's uniquely well-suited to the material.
Enough with the "everyone should know everything". I have had a fairly long and successful career as a software developer and I don't know half that stuff off the top of my head. I think it's important to know that they exist and where to look for them, but very few developers really need this on a day to day basis.