How can I rebuild my base of algorithms/data structures knowledge?

Question

I recently graduated from UMass Amherst with a B.S. in Computer Science. I maintained a 4.00 GPA, and I feel like I received a very solid education in most areas of the discipline.

In my junior year, I took the Data Structures and Algorithms course. I feel that it was poorly taught. I breezed through it and understood the majority of the material. When my younger friends took the class in later semesters, they told me it was brutal, and mentioned all sorts of things that I never encountered in my class. This made me somewhat worried about the education I'd received in that class.

This worry was confirmed later on. I participated in a few algorithm competitions (TopCoder, Google Code Jam, Facebook Puzzles, and a couple others). I struggled on all but the simplest of problems. Other people seemed to be able to boil down problems and identify base algorithms and data structures very quickly. I was rarely able to pick out a base algorithm, usually trying to roll my own solution and occasionally noticing a familiar algorithm halfway through (at which point, everyone else has the problem and moved on).

Does anyone have any advice for how to rebuild my base of knowledge in this area? I know I am a strong computer scientist and have the ability to be proficient here, so I don't want to spend the rest of my career lacking in this area because of a subpar course. I know the very basic stuff (big-O, how different sorting algorithms work and their complexities, etc.), but I feel like I can't do anything practical with my knowledge.

Answer 1

Keep competing in competitions and seek out answers to the problems you can't solve on your own. There are tons of books that can help. A few that I can recommend are:

• Algorithms in a Nutshell
• Introduction to Algorithms
• The Algorithm Design Manual

There are also good online resources like The Stony Brook Algorithm Repository and the NIST Dictionary of Algorithms and Data Structures.

Answer 2

I recommend:

• Data Structures and Algorithms - Aho, Hopcroft, Ullman
• The Design and Analysis of Computer Algorithms - Aho, Hopcroft, Ullman
• Compared to what? - an introduction to the analysis of algorithms - Rawlins
• Introduction to Algorithms - Cormen, Leiserson, Rivest

If you have the time, read these. I recommend the above order. Aho is the 'a' in 'awk' and Rivest is the 'R' in 'RSA', so these authors have had some broad influence on other authors in the field.

Some might suggest the Knuth volumes but if you are going to be reading Knuth, a more recent and interesting tome of his would be Concrete Mathematics.

To develop intuition in the field, I recommend Programming on Purpose series by Plaugher.

How do you learn the application of data structures, though? I think you could have a lot of fun writing a little virtual machine. Some garbage-collected mini-language of your own design, or perhaps your own implementation of, e.g., JavaScript. By the time you implement this, you will have had to make a lot of trade-off choices between algorithms and this might help you see the considerations which come to bear.

How much time do you have?

Answer 3

It's important to realize that there's not an out-of-the-box algorithm for every problem on the planet. Some CompSci instructors create test questions that have an obvious correlation with an algorithm that was taught, but in real life the diversity of problems is much bigger than the diversity of algorithms. 10 or at most 20 algorithms will take you through much of any professional programming career (I think), given that you can always reach behind you and flip through a book if you encounter a problem that may require a new one.

It's not very hard to memorize such a set of algorithms. It's much harder to turn a word problem into a practical solution; very often the algorithm you need to develop isn't one of those found in any book. If you're struggling with this, then you may not be as strong a programmer as you claim.

The good news is: The ability to do this well and quickly improves with practice, so all you need to do is follow Bill the Lizard's advice and get out there and do more of it.

Answer 4

One of the best way is to read the book Introduction to Algorithms by Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

There is also a MIT OpenCourseWare lecture on this that even includes lecture videos:

http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/CourseHome/

Answer 5

Like I said before, see Knuth.

Answer 6

Sorry if this sounds harsh, but how can you consider yourself to be a 'strong computer scientist' and still only 'know the very basic stuff (big-O, how different sorting algorithms work and their complexities, etc.)'?

I think what you are missing here is the fact simply knowing about algorithms/data structures isn't enough. IMHO, the basic skill to be developed is being able to come up with solutions to problems. Simply knowing stuff is not enough. Most problems don't map directly to a well-known algorithm from a textbook. What one needs is the ability to break down a problem and logically arrive at a solution. Of course, knowing well known algorithms and understanding how and why they work is essential. But programming problems are rarely as simple as "find the shortest path from A to B in the given network". And the way to develop your mind for that is by actually working on problems.

I would suggest an equal measure of study and practice. Lots of good books have already been suggested. My personal favorite is CLRS. As for practice, you are already familiar with TopCoder, Google Code Jam and Facebook Puzzles. They are all good places for practice. The TopCoder Algorithm Tutorial section is a very good resource. There are other sites like SPOJ, Project Euler and Uva Online Judge that are also popular.

Answer 7

I think Bill's recommended list of three books are a great start. My preference is for Introduction to Algorithms, but go check them out at a library and see which one you would like best to start with. Then read and do the exercises and submit any questions here in Stack Overflow (tag the questions with "algorithm"). There are plenty of computer scientists here who would be happy to help and taking the time to formulate a good question can help you understand the problem better (sometimes even to the point of helping you see the solution).

Answer 8

I was not terribly fond of my algorithms class until it was over and I realized just how much I learned. I had a fantastic professor, which doesn't help you much, but the book we used was also quite good. It was Algorithm Design by Jon Kleinberg and Eva Tardos.

http://www.amazon.com/Algorithm-Design-Jon-Kleinberg/dp/0321295358

Answer 9

Donald Kuth.........