Back To Basics: Algorithms and Going Back To Virtual School
Before I graduated from College/University I was convinced that school was for lamers. Then I graduated from school and decided that NOT going to school was for lamers. That shows you what a wishy-washy person *I* am. ;) School is for some folks and not for others. Wear the shoe that fits you best.
Totally random retrospective self-focused aside: I graduated from OIT with a BS in Software Engineering in 2003. Yes, that's 2003. It took me only 11 years to get a 4-year degree. ;)
I've been a programmer since 1992, so about 16 years, but 11 of those I was going to school at night. Basically I worked 9a-5p and went to school 6p-10p. For the first few years I took a lot of courses, but then work happened and I tapered off to one course a term. This was fine for a long time but then credits started falling off the other side. Basically courses I took 7+ years before became obsolete. I actually lived through four Deans while I was there. I made a deal with one of them that if I taught .NET I could keep my credits longer. That let me keep taking courses while working the whole time. The result took 11 years and two schools. But now I can just say, "I've got my degree and just not mention that I got it 5 years ago. Don't tell. Lots of experience sounds better than "slow learner at school."
Whether you went to school or are self-taught, even though the Internet was originally more a place to put academic papers than a place to meet "friends", there's a LOT more really good academic information on the web than I remember. It also takes more interesting forms than just pages of class syllabi. Here's the syllabus for the CST407 class I taught in Fall of 2003.
You can learn via Googling, you can learn via Book Readin' but you can also setup a more focused "curriculum" for yourself. I know a lot of devs that I admire that do this. They'll pick a discipline, area, language, whatever, and create a mini-class for themselves. Actually that much-teased "Learn Whatever in 24 Hours" books have more structure in this way than most programming books.
These days there's all the good content at iTunesU from colleges that didn't return my calls back in my High School years. There's even 1986 video of the legendary MIT lectures "Structure and Interpretation of Computer Programs" with Hal Abelson and Gerald Jay Sussman. There's MIT's excellent OpenCourseWare Videos of the Introduction to Algorithms class up on Google Video.
I recently stumbled on Massimo Di Pierro's site and his code. He's got a CSC309/321 class that he teaches at DePaul University and has a great Python application called "Algorithms Animator." His slides on basic OOP in C++ are excellent but the Algorithms Animator is really cool. There's a video of Algorithms Animator running over at Vimeo.
He's got all sorts of common algorithms, sorts, traversals, searches, etc. The algorithms are all in src/csc321algorithms.py, like this simple binary tree example.
if tree is None: return true
if len(tree)==0: return true
if not isNullTree(left):
if not isNullTree(right):
There's also more complex ones like a Huffman encoding example. But it's not the source code that interesting, although it is. The syllabus is really detailed, with the kind of detail you really only see in academia:
Huffman Encoding Definition: A minimal variable-length character encoding based on the frequency of each character. First, each character becomes a trivial tree, with the character as the only node. The character's frequency is the tree's frequency. The two trees with the least frequencies are joined with a new root which is assigned the sum of their frequencies. This is repeated until all characters are in one tree. One code bit represents each level. Thus more frequent characters are near the root and are encoded with few bits, and rare characters are far from the root and are encoded with many bits.
The Program accepts the text to be compresses as input and produces a text report showing compression rules and compressed text. The Program also shows in an animation how the Huffman tree is built.
Huffman encoding provides an example of Greedy strategy.
What's cool about this guy's way of teaching algorithms is that his app uses animation to show the algorithm happening step by step.
For example, if I use Huffman Encoding on the string "Scott Hanselman," here's Frame 0 of the animation.
"First, each character becomes a trivial tree, with the character as the only node."
Here's Frame 15 as the the character's frequencies are counted and the tree is in the process of being built.
"One code bit represents each level. Thus more frequent characters are near the root and are encoded with few bits, and rare characters are far from the root and are encoded with many bits."
Here's Frame 22 as the tree has been built out and the bit values are applied.
...and the result is in the image below showing the compression rules/map and the final bits.
I'm not sure about you, but I'm not able to bust out a QuickSort on a whiteboard under pressure anymore (I'm old). I found this guy's stuff to be a great algorithms refresher, and using the little Python app to explore them made it very enjoyable. I wish we had this kind of stuff when I was in school. It's kind of nice to pretend I'm back in an Algorithms class and tickle the neurons that haven't fired in a while.
- Three Things I Learned About Software WHILE NOT in College
- 2003 - Leaning at the Tape...a B.S. in Software Engineering squeezed into 11 short years...
- A College Project: Rescuing the Tiny OS in C#
- Six Essential Language Agnostic Programming Books
- Books: We need more So What, Now What and What For? and less just What
- Article about me on OIT's Alumni Site