CS106B and aiclass

For the latter part of 2011, I decided to focus more on writing code and learning than writing about code.  I did this by taking two courses online, Programming Abstractions (CS106B) and Intro to AI, both from Stanford, online and free.

I started CS106B because while I had some familiarity with the concepts in the course, I didn’t have much experience implementing them.  The course covers a range of topics including: recursion, complexity analysis, search/sort, use and implementation of many standard containers (vector, queue, stack, map, etc.), pointers, linked lists… and more!  While the previous course (CS106A) is a great introduction to coding and software engineering, this course digs much deeper into more complicated abstractions for data structures and algorithms.

Although most of my code at work hasn’t required much of what I gained from this class, more coding is good and coding out of my comfort zone (which these topics definitely were) is better.

More importantly, the final assignment of CS106B ended up teaching me a valuable lesson about planning.  The first part of the assignment was to implement Dijkstra’s algorithm (which finds the shortest path through a series of connected points).  While this wasn’t trivial, the planning wasn’t very difficult and the debugging was standard.

The second part of the assignment was to implement Kruskal’s algorithm (create a minimal spanning tree from a graph. That is, create the minimum number of connections to connect all points on a graph).  I ran into some serious trouble here.

Part of the problem may have been the artificial deadline I set for myself.  In any case, when it came time to put this together, I read the assignment several times and just wasn’t getting it.  Instead of taking a break and getting a solid plan in place, I decided I had some ideas about parts of the algorithm, and I could eventually hack those pieces together and figure out the rest.  I’ve made a huge mistake.

Without understanding how to attack the problem, I started using the same data structures I had used for Dijkstra’s algorithm with some awful workarounds. After too many hours debugging this hack, I finally had the insight that I needed to make a simple change to the data structure I was previously using.  If I would have decided to take some time to do this before diving into the code, I would have saved myself a lot of frustration.  

There is a significant difference between debugging and reimplementing on the fly. It is not possible to successfully debug an incomplete solution.

Following CS106B I began taking Intro to AI, which taught me that AI requires a great deal of probability theory. And that probability theory is hard.  To be clear, the calculations aren’t very difficult per se.  In fact, most of the implementation only required arithmetic (some of the derivations required calculus).  However, knowing how to implement them was quite difficult.  I have saved the programming assignments from the lecture version of the course and began work on the first one, but haven’t decided if I am going to dive into those. haven’t done them a few months after finishing the course.

In fact, I’m in the middle of deciding what to do next.  The trouble with the AI assignments is that they are going to be quite time consuming, and while I don’t necessarily have a problem with doing difficult coding work just for the experience (see above), I am debating if maybe I should spend time on something I’m a bit more likely to use in the near future, or is at least a bit more universal in its application.

I was considering taking Stanford’s Algorithms course, (set to begin in January but only started recently),  Building a Search Engine, or Programming Paradigms (CS107, a followup to CS106B). After some serious soul searching and few coin flips, I’ve decided I want to finish the Stanford Engineering Everywhere Computer Science offerings and take CS107. I plan to start early next month.

I’m also hoping to post my completed graph assignment described above using Google Chrome’s Native Client.