Yuri Gurevich: “Introduction to Algorithms and Computational Complexity, Part 1 of n”

Get Microsoft Silverlight

Can’t see the video? You can download and install Silverlight or download the video in MP4, MP3, WMA, WMV, WMV (High) or Zune formats.

If you took computer science in university, you might remember a course or two with a title like “Algorithms and Data Structures”. Perhaps – and this is more likely – you might not. It’s understandable: as a student, you were probably bored by the course’s deep forays into theory-land and never cracked open Rivest and company’s Big Book of Algorithms, certain that you’d never end up using this stuff in real life (and admittedly, the only time I ever found the “Could P ever equal NP” problem useful was in an extremely unusual dating situation).

As a reader of this article, the chances are that you’re out of school and working either as a programmer or at least work with them. You might have come around to thinking that you wish you’d paid a little more attention in that Algorithms course, in that wistful, grown-up “Why did I quit piano lessons when I was young?” way. If you feel this way, here’s your second chance.

Microsoft’s Channel 9 is presenting a series of video lectures by computer scientist and big math brain Yuri Gurevich,, the guy behind the abstract state machine (an enhancement of the Church-Turing Thesis, which states that if it’s computable, it can be computed by a Turing machine). In this series, he’ll walk through all those algorithms that were covered in that course, provide plenty of historical context and explanations, and hopefully give you enough knowledge to help make you a better programmer. The first lectures in the series introduces algorithms by starting with Euclid’s “greatest common divisor” algorithm, explores the history of computation (including the Entscheidungsproblem), covers the difference between solvable and non-solvable and covers all those goodies you missed in Algorithms class.

This article also appears in Canadian Developer Connection.