Algorithms Design and Analysis Part I

∞

Tonight I started Coursera.org’s Algorithms: Design and Analysis Part I. This class should pick up right about where I left off my computer science education. I took CS15 as a sophomore in college but didn’t have the time to take CS16: Introduction to Algorithms and Data Structures. So, while it’s been almost 6 years since I have formally taken a computer science class, it is time to continue my education.

I plan to write about once a week about my experience. This will serve both as an opportunity to work out ideas spurred by the course as well as a review of the growing area of free, online courses that started way back in 2002 with MIT’s OpenCourseWare and continues today with upshots Udacity and Coursera, among other players. Given the emphasis being placed on the potential for technology as disruptive to classroom teaching over the last 50 years, the topic seems worthy of some experiential learning by a budding young education researcher/wonk.

The Introduction video was a bit scary. Although the content was simple, Professor Tim Roughgarden is a fast talker and he does seem to skip some of the small steps that really trip me up when learning math from lectures. For example, in discussing the first recursive method to $n$-digit multiplication, Professor Roughgarden suddenly throws in a $10^n$ and $10^{n/2}$ term that I just couldn’t trace. I kept watching the video waiting for an explanation and pondering it in my mind when a few minutes later it hit me; the two terms kept the place information lost when a number is split into its constituent digits 1.
1. The algorithm called to split an $n$ digit number $x$ into two, $n/2$ digit numbers. What was unstated, but of course true, is that this transformation must result in an expression that was equal to $x$. Of course, $x=10^n * a+10^\frac{n}{2} * b$ , because the leading digit of $a$ must be in the $n^{th}$ place and the leading digit of $b$ must be in the $\frac{n}{2}^{th}$ place. Nothing about this is complex to me, but it was not obvious at the speed of conversation. I think working out an actual example of a 4-digit number multiplication, as Professor Roughgarden had with the “primitive” multiplication algorithm, would have made this far clearer. [return]