outward not upward

I bill myself out as a “software developer.” This is fair, I think, since I’ve written a lot of software over the past ten years, and this combined with my college education has enabled me to develop solutions to rather large and difficult problems.

Sometimes, though, we all need to reminded of the basics. It’s been a couple of years since my basic data structures and algorithms class, and it’s now gotten to the point where the difference between a red-black tree and a leftist tree is pretty fuzzy. Fuzzy to the point that I’m not sure I ever really grokked the difference.

So, it’s time for a refresher. I don’t have a copy of Leiserson/Rivest/Cormen handy, so I’m just going to use what’s on the shelf. Here’s the rubric for each topic:

1) Do I know the basics of this topic? (i.e., in what situations is it applicable, what are the time and space complexities of the algorithm, does it scale, are there any situations in which it is especially undesirable?)

2) Can I implement this data structure or algorithm in C++? In C#? Could I implement it in Java? In PHP? Which of these already have equivalent or better facilities built in?

3) No, seriously, can I implement this? Working out one case on paper is never enough. It’s important to be able to start from scratch and produce a working implementation the first time, especially in cases where languages are unlikely to have native equivalents, since these are the instances where a professional would likely have to hand-code an efficient solution.

And here’s the hit list of topics I plan to (re)learn, in rough level of difficulty:

• Linked lists
• Stacks and queues
• Skip lists and hashing
• Binary and N-ary trees
• Union-find
• Heaps and heap sorting
• Merge sort and quicksort
• Priority queues
• Leftist trees, tournament trees
• Minimum cost spanning trees
• Binary search trees
• AVL trees
• Red-black trees
• Splay trees and B-Trees
• Tries
• Graph algorithms
• Greedy method and related techniques
• Divide-and-conquer
• Knapsack problems
• Dynamic programming and recurrences
• Backtracking
• Branch-and-bound methods

Pretty tall order. For some of these topics, I expect a very short review period, but some of them may take a few days’ dedicated study. I’ll post here as I progress down the list.