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.

The Difference between Sleep(), Wait(), and Pause()

I haven’t written in a while about the Stanford CS106B course I’ve been working through because I wanted to have some measurable progress behind me before discussing it again.  Recently, I completed the fourth asssignment, making a single player version of Boggle with a computer opponent.

Although the previous assignment also focused on recursion, this is the first assignment that requires creating recursive algorithms that piece together to form a useful program (read: not just data entry from the user to prove you have an algorithm).  After attacking the more difficult portion of the assignment (the recursive human turn), I decided to attack the easier task of highlighting and unhighlighting  the blocks of a word that is found.  I used the supplied HighlightCube function to, but I ran into trouble when I tried to remove the highlight.  The blocks would simply never highlight.  I tried using both the Windows Sleep() function and the following wait function from here:


void wait ( int seconds )
{
     clock_t endwait;
     endwait = clock () + seconds * CLOCKS_PER_SEC ;
     while (clock() < endwait) {}
}

When both of those produced the same problem, I began looking for a different solution and found someone who had already completed the project.  I tracked down the relevant code section and found the use of the function Pause().  This worked, but I wasn’t satisfied without knowing why it worked where the others didn’t.

The best place I could think of to ask was on Stack Overflow.  I got an answer, and even a bit of rep for asking.  It turns out the graphics buffer writing is a low priority message and the sleep/wait function pushes both the writing and clearing of the graphics to after the wait/sleep.  The difference between the sleep and the wait is that the sleep function halts a thread for a given time whereas the wait function checks the clock repeatedly until the time has elapsed (costing CPU cycles and power). So Stack Overflow taught me why the wait and sleep functions didn’t work, but I still wanted to know what the Pause function was doing to clear the highlights correctly (and so did a few of the commenters on SO).  After some searching through the CS106B supplied libraries, I found that the Pause function was simply a function to pause the graphics buffer (not the entire program).

In this instance, I found two functions that gave me obvious problems.  This made it easy for me to realize I needed another solution.  However, I found some more subtle bugs in my code that were a result of the same flaw I have in my coding style:  I tend to prefer to write code to perform a task without first considering what potential problems the function needs to avoid.

While debugging a separate issue, I noticed that the word SAGS was place vertically, in reverse, along the left hand side of the board, but my program would not recognize it as a valid word.  After tracing through my recursive algorithm (and realizing that it was correct), I found that the program was failing because it was only testing the first letter of the word the first time it found it.  Soon after solving this, I realized that my algorithm did not account for users entering words with a block used more than once.  Instantiating a second grid of bools to check if a letter was already used was easy enough, but seeing these three errors really drove home the need for a better approach to algorithm design.

Warning:  coding buzzwords

I’d like to think I’m using ‘best’ practices when it comes to coding, but I tend to err on the side of being a bit too Agile.  What I mean by this is that instead of writing specifications for a method/function/algorithm/etc., I tend to consider some aspects of it and get right into coding and compiling.  I love to see the result and have something to work with rather than planning for too long for the perfect function (that will likely need debugged anyway).  However, in cases such as those described above, not considering the possible weaknesses with an algorithm led me to overlook some fundamental problems that I may not have noticed if not for seeing the errors pop up by chance on the board.

This project has given me a practical example demonstrating why Test Driven Development is a widely used process.  It is much easier to ask hard questions of a function that doesn’t exist than one that is ‘working’.

CS106B and the Google AI Challenge

CS106B

Looking back on my latest blog posts, I realize that most are addressing flaws in software that I use regularly.  When I began this blog, I hoped to use it to focus my efforts in becoming a better software developer.  Analyzing design choices in software does that to some extent, but I need to be creating more in order to improve.

One problem I’ve had with creating software outside of work is a lack of focus.  By this, I mean I want to create a lot of software and learn many tools.  Examples:  Creating mods/new levels in new PC games with editors, creating Android apps, going through some of the most well recognized books in computer science, taking  free online courses in CS, and so on.  I have done each of these to some extent, but now I would like to focus solely on one (I have failed at this already, see Google AI, below).  I believe this will allow me to learn more in the span of a few months than trying to do all or some of these projects concurrently and not getting very far in any of them.

Before the end of the year, I intend to complete Stanford’s CS106B, a data structures and algorithms course from Stanford Engineering Everywhere.    My main focus will be on the seven major programming assignments.  I will likely be looking at the section assignments for a limited amount of time before looking at the answers in the interest of keeping progress moving.

I am hoping that by focusing on one project for programming outside of work, I will be able to delve deeper into that project and hopefully discuss it here to see how it impacts me as a developer.  Currently, I am finishing up the second major assignment.  While my progress is a bit behind where I would like, I am consistently working a bit each day on this.  So despite my progress not being outstanding, I am quite satisfied with my consistency.

Google AI

I can’t remember where I saw it but a couple of weeks ago I saw a link introducing Google’s AI Challenge for this year.  I haven’t done much yet, but I’m working with a colleague to come up with an entry for the contest.  Neither of us are particularly skilled in AI development, but we are both excited to see how we can do in this competition.  The competition lasts just a little over two months.

I won’t be able to discuss our top secret strategy until the competition ends, but the AI contest and CS106B should provide some interesting topics for the remainder of the year.