Monthly Archives: April 2013

Review: Games without Chance: Combinatorial Game Theory — Coursera

One of the most engaging educational experiences I’ve had so far, not just on Coursera but in general, just ended: Tom Morley’s Games without Chance: Combinatorial Game Theory. If you’re like me two months ago, you now probably wonder what a mathematical game is. So, let’s start in medias res by showing you one of the mathematical games we’ve studied. Here’s a position of Hackenbush:

Hackenbush position

The players, called “Left” and “Right” respectively, move in turns. Left cuts the blue stalks, and Right the red ones. Cut stalks are removed from the game. In addition, any other stalk that has no connection to the ground anymore after a move is removed as well. The first player to not have a move left loses the game.

The entire course can be easily described just based on this one game. Of course, you can just look at one single Hackenbush tree and enumerate all possibilities, trying to mechanically figure out who has to win or lose given best play. There are four possible outcomes. The winner is either Left, Right, the first player to move, or the second player to move. This works well with a small tree, but if you start with a complicated enough tree, add more trees to the game, or even add different kinds of games, this procedure quickly becomes impractical. So what else can you do?

Well, you could represent the trees as numbers and figure out the result of the game based on that, and you can also simplify games to positions that are easier to reason about. Of course, if it’s possible to represent a game as a number, the simplification happens numerically. On the other hand, if the game is represented as a position, you can translate it into a simplified game position, e.g. a complex Hackenbush tree into one that has the same outcome but is easier to reason about.

Those were the main points of the course. Of course, the occasional proof was thrown in as well. Further, we studied more than just Hackenbush. Above, I alluded to other games, which you could add to a given Hackenbush formation. Those were Nim, Toads and Frogs, Cut Cake, and a few others. Feel free to look them up. However, you’ll notice that they are interesting due to their mathematical properties, but that they aren’t necessarily the kind of game you’d play with your friends to pass the time. After all, the essence of mathematical games is to study rules, strategies, and outcomes using the tools of mathematics, and only incidentally to play them.

There were no prerequisites for this course, but it was “highly recommended that students have taken rigorous college level Mathematics courses”. If you’ve been exposed to college-level mathematics, particularly discrete mathematics, you should find the course very accessible. Without this background, though, you may find it difficult to make the conceptual jump to abstract reasoning. I found the material quite easy to follow, but I’ll refrain from calling Games without Chance an easy course. In the forums there were complaints that the course didn’t “make any sense”, but such statements were rather rare, presumably because the crowd seemed highly self-selecting.

The course was small, and it felt small. In fact, for the first time when taking a Coursera course I thought that skimming the forums was worth my time. Tom Morley himself contributed quite a bit, too, often with his delightful and quirky sense of humor, for instance in this exchange:

Forum Discussion

Lastly, let me remark that the course was well-organized. The people at Georgia Tech seem to have put a lot of thought into it. While most courses on Coursera greet you on the announcement page, and from there on let you explore videos, quizzes, extra problems and so on, Games without Chance had, in addition, tabs that summarized the relevant content for each of the seven weeks. From one page you could access a summary of the relevant part of the syllabus, slides, videos, quizzes, and extra problems. At the very end they sneaked in a weekly survey asking for feedback regarding how you perceived the difficulty and how much time you’ve spent on the problems.

Overall, I found that Games without Chance was well worth my time. I’d highly recommend it to anyone who enjoys abstract reasoning. If you love puzzling over problems in, say, graph theory, or enjoy formal logic, then this is probably a course you might want to consider taking when (if?) it is offered again in the future.

Review: CS101: Introduction to Computer Science I — Saylor Foundation

With the current craze surrounding MOOCs, some of the players in the open courseware arena seem to get very little attention. One of the underdogs is the Saylor Foundation, which pursues a unique strategy by curating content from around the Internet, adding original content, bundling it all up into individual modules, and offering examinations. All this happens in collaboration with academics from a wide range of institutions. Currently, the Saylor Foundation offers virtual “degrees” in about a dozen academic disciplines.

I’m not so much interested in Communications or Art History, but I was curious about their offerings in computer science. The Saylor Foundation replicates a basic computer science degree on their website, drawing from a wide range of sources, including MIT OCW and Stanford, but also Khan Academy and, if needed, the occasional blog post or two. I decided to dip my toes into the water and went for their CS101: Introduction to Computer Science I. I have some background in this field, so it was a breeze to go through the material.

At first I was a skeptical about the general approach of the Saylor Foundation since they draw from many sources, seemingly of uneven quality, but I found the material surprisingly engaging. It’s certainly more motivating than going through some of the introductory college-level textbooks I have seen. The main source for CS101 was an interactive tutorial on computer science designed by Bradley Kjell of Central Connecticut State University. Given that many MOOCs are offered by elite universities, some readers may now want to dismiss Saylor, but this would be misguided. CS101 is an introductory class, and you don’t need an academic superstar to teach it.

Kjell’s tutorial is very well-laid out and gradually introduces concepts. Some textbooks have the audacity to tell you to just accept a concept or language feature as fact if you don’t understand it yet, and refer you to a future chapter in which everything would be cleared up. Didactically, I find this to be pretty questionable approach. On the other hand, Kjell does a very thorough job. The only legitimate complaint would be that he might move a bit too slow at times. Thankfully, he isn’t very verbose, so it is easy to skim parts. On the other hand, if you think the pacing is just right, then you can also listen to audio recordings of the material. I preferred reading, but he does have a voice that is very pleasant to listen to.

The presentation may have been a bit archaic, but the content is good. There were even some unexpected highlights like a digression on machine language where students were asked to construct a while loop using machine instructions. The toothbrush has to be instructed to move bristles until it is switched off:

Screen shot 2013-04-07 at 12.15.17 AM

Yes, this is artificial, but it’s a pretty neat exercise nonetheless.

Bradley Kjell’s material focussed on Java. However, Saylor’s CS101 introduces Python early-on to illustrate how concepts are implemented in a different language. I thought this was a very good idea as it broadens your horizon. Normally, introductory courses only focus on one language.

Overall, the content started from first principles, and programming language constructs were introduced very gently. Therefore, CS101 would be a good course for someone with little previous knowledge as some of the introductory CS MOOCs can move rather quickly. You won’t just be exposed to the basic building blocks of computer programs like data types, operators, control structures, or input/output mechanism. There is also the typical brief coverage of fundamental hardware and software concepts. Perhaps surprisingly, software engineering methodologies are very briefly discussed as well, with a brief overview of the waterfall model and its stages.

The only downside might be that there are no interactive programming exercises, and that the (static) programming exercises themselves are not very numerous. However, DrJava is your friend and will serve you well. You probably want to supplement this course with a few Java practice exercises on CodingBat, though.

The final exam is randomly generated. You have to answer 50 multiple-choice questions. If you get at least 70 % right you’ll earn a certificate. If you don’t pass, you can try again after two weeks. I thought that in the final exam the do/while loop and switch statements were too prominent. Sure, they might come in handy at times, but many programmers view them as superfluous language constructs and often ignore them altogether. This is just a minor quibble, though.

Overall, Saylor’s CS101 provides a gentle introduction to computer science. Even though the course doesn’t offer interactive exercises, the format worked surprisingly well. The final exam is a useful feature, too, and it helps distinguish Saylor from other OCW sites.

Review: Introduction to Databases — Stanford Class2Go

Jennifer Widom’s Introduction to Databases has an impressive pedigree, having been one of the three inaugural Stanford MOOCs that caused the avalanche of online courses we can all enjoy today. Furthermore, this course has had many homes, tracing part of the MOOC revolution. Originally, it was a stand-alone class offered by Stanford in autumn 2011. The content was later on added to Coursera and offered in self-service mode, i.e. without exam and involvement of TAs in the forums, before it was offered again this January on Stanford’s Class2Go platform. Less than a week ago, though, it was announced that Class2Go would be folded into MIT and Harvard’s EdX platform. On a side note, the other two inaugural Stanford MOOCs were Andrew Ng’s Machine Learning, and Introduction to Artificial Intelligence by Peter Norvig and Sebastian Thrun. Andrew Ng became co-founder of Coursera, and Sebastian Thrun launched Udacity. Looking back, it’s quite amazing how much has happened in the course of little more than a year.

Unlike machine learning or artificial intelligence, knowledge in databases is likely to be relevant for a large part of software engineers since databases are ubiquitous. I think that a course on databases is one of the most “useful” courses one could take as part of a typical computer science degree. Such knowledge is presumably deemed too practical in some departments, which might explain why an intro to databases is often an elective instead of a mandatory course.

I took an introductory database course last semester at university, and frequently referred to some of the videos of Jennifer Widom’s class, which was offered in self-service mode on Coursera back then. I found her explanations very lucid. My lecturers were overly fond of theoretical explanations, without demonstrating how the concept are used in practice. In contrast, Jennifer Widom follows a didactically much more sensible approach by showing examples first and explaining various pros and cons before eventually covering theoretical definitions. Her explanations on referential integrity and the various so-called normal forms were all very clear. She even helped me understand multi-valued dependencies, which I initially found difficult to grasp. However, that kind of knowledge will presumably be less relevant in practice.

I originally didn’t intend to go through the entire course, since I have already taken a similar one at a brick-and-mortar institution, but shortly before the course started, I learnt that Introduction to Databases was moved to Stanford’s new platform Class2Go. I was simply curious how their platform worked and had a look around. What motivated me to work through the material was simply the great amount of flexibility it offered. Even though the content was spread over nine or ten weeks, everything was available from the very beginning. There were deadlines, but you had the option of working well-ahead of schedule. The only other fixed dates were two two-day periods for the mid-term and final exam.

I wasn’t going to invest a lot of time in this course, but wanted to explore areas I hadn’t been exposed to yet, or only cursory, such as JSON, and more advanced SQL topics like views or triggers. I was thus pleased to notice that the course had two different tracks. If you wanted to earn a statement of accomplishment, you had to score 75% from a weighted score of exams, interactive exercises and quizzes, in addition to scoring 75% of so-called challenge-level problems. I was content with the regular statement of completion that was awarded for a score of at least 50%. Thus, I skipped most of the challenge-level exercises. The course itself offers a smörgåsbord of database-related topics. The curriculum even encouraged designing your own learning path, and the conditions for the statement of completion were such that you could easily skip a few topics and still “pass” the course.

I very much enjoyed learning about JSON, which made me even more skeptical about XML. Another highlight was recursion in SQL, but this topic might see little application in the real world. I’ll just list all topics of the curriculum so that you’ll get an idea of the breadth and depth it offered:

– Relational Databases (relational model, querying)
– XML Data
– JSON Data
– Relational Algebra
– SQL (main commands)
– Relational Design Theory
– Querying XML
– UML
– SQL: Indexes
– SQL: Transactions
– SQL: Constraints and Triggers
– SQL: Views
– SQL: Authorization
– SQL: Recursion
– SQL: On-Line Analytical Processing
– NoSQL

Of course, SQL is the 800 pound gorilla you just won’t get around. However, the supplemental topics were well-selected. This course focussed more on practice than theory, which working professionals might appreciate. Still, you’ll be taught substantial amounts of database theory, meaning that this course is not lacking in that regard either. If you want to thoroughly go through each module, you should plan to invest a good five to eight hours a week.

Overall, Introduction to Databases truck me as well-designed. The quality of the teaching was top-notch, too, with Jennifer Widom taking great care to illustrate every concept, and spending copious amounts of time demonstrating them in practice. The course was surprisingly hands-on, and a significant part of the videos were screencasts showing the instructor querying a database, explaining peculiarities of SQL syntax along the way, or pointing out common mistakes.

The course is currently offered in self-service mode. If you want to learn about databases, it is an excellent starting point. Please note that even though this course does refer to three database textbooks, you won’t have to buy any of them since the teaching materials are of a very good quality. I own a copy of Jeffrey Ullman and Jennifer Widom’s A First Course in Database Systems, which complements this online course. However, it was merely in the “nice to have” category, meaning that I think it’s quite possible to make it through the course without a textbook.