edX 6.00x week 4 – word games, debugging and complexity

John Spurling in his introduction to J.G. Farrell’s unfinished novel The Hill Station, reflects that the feelings of sadness and disappointment he felt when he first read the incomplete manuscript were inevitable, and that:

The only antidote is to be warned in advance and to enjoy what there is of the journey without expecting any proper destination

This week on edX 6.00x has been a little like that I suppose. The problems with PSET4 (the edX word game – similar to Scrabble or the popular Channel 4 TV show “Countdown”) I mentioned in my earlier post were eventually partially resolved, but it meant that the final two parts were left ungraded as (quite rightly) the course team decided that too much time had elapsed this week to give everyone a fair chance at solving them in a way acceptable to the automated grader. However, the final two parts of the problem set were posted and I did complete them.

While I’ve been developing my solutions using my laptop (as that’s what I have with me during the week), I’ve also been running them on my Raspberry Pi at the weekends – as I’m determined to get my £30’s worth out of the device! While it’s not exactly the same distribution of Python (I think), the version number is the same (2.7.3) and everything that I’ve developed on my Windows laptop has worked properly so far – as you’d expect.

If I have chance tonight, the one niggling end left undone is the algorithm I used for compChooseWord. It’s very definitely a ‘brute force’ version, with complexity O(len(wordList)), which I know I can improve dramatically!

Which leads neatly into the topics of this week’s lectures – debugging and computational complexity. There was nothing in the content that was unfamiliar to me, but both topics have provoked some interesting discussion in the forums. The definitions of algorithmic complexity have produced some good observations on both facilities within Python for looking at the cost of running particular sections of code (“import time” seems like a good starting point to me) and whether or not specific operations (such as addition, multiplication, assignment and comparisons) really do all cost the same (they don’t, but for the purposes of analysing the general complexity characteristics of algorithms it is of course possible to ignore such minutiae).

Week 5 is due to cover memory storage, sorting algorithms and hashing. With midterm 1 also due to be completed during this week, some careful time management will be needed.

 

Posts Tagged with…

Your thoughts?