Algorithms are everywhere. They help us travel efficiently, retrieve information from huge data sets, secure money transactions, recommend movies, books, videos, predict stock market etc. It is very tough to think about a daily task that does not benefit from efficient algorithms. Often the algorithms behind most of these tasks are very simple, yet their impact is tremendous. When I say “simple”, they are simple to people who know them. Most common people consider algorithms too mathematical. They assume that it is beyond their capability to understand algorithms. What they do not realize is that algorithms are often simple extensions of our daily rational thinking process.
For example, almost everybody considers it stupid to buy an item for $24 and pay $6 shipping, if there is free shipping for orders of more than $25. If you add one more item of cost $1, you saved $5. Also, when we pack our bags for travel, most of us try to do it as “efficiently” as possible, trying to carry as many “valuable” things as possible while trying to avoid paying for extra luggage on airlines. We consider these rational choices. Algorithms are simply “step-by-step procedures to achieve these rational objectives“.
If you are an instructor (like me), teaching Algorithms, you might have noticed that most students (around 70%) are intimidated when they take a basic algorithms course. Most of them DO end up doing well in the course, but they consider the process painful. If they reflect on the course, most often they say “that course was a nightmare, I don’t remember what I learnt in that course”. They do not seem to have enjoyed the course. Probably they might remember 30% of the material. This is definitely not acceptable for such a fundamental course.
Often, when I comeback to my office after teaching, I say to myself “I should have given them one more example, to help them get better intuition”. You can always do better job if you are given more time. Alas, we have time-bounded classes and almost infinite details to cover. We expect students to learn some concepts on their own and develop their own intuitions. We want to give “good” reading material. So, their understanding depends on how well these readings are written.
Today’s post is about “How to teach Algorithms ?” Here is one of my experiences, while I was teaching an undergrad algorithms course at GeorgiaTech. I was teaching dynamic programming. I gave several examples to make sure that they understand the paradigm. At the end of the class, almost 50% of class had questions, because this is the first time they saw dynamic programming. I told them to see me in my office hours. I quickly implemented a java applet to show how the matrix entries are filled by the algorithm, step by step. When I showed them this applet and a pseudo-code side-by-side (highlighting every current line of code being executed), almost all of the students understood the main idea behind dynamic programming. Some of them also said “it is easy”. I was glad and wanted to add more algorithms in my code.
The Kintali Language
The goal is to have a very simple to understand “executable pseudo-code” along with an animation framework that “understands” this language. So I started designing a new language and called it Kintali language, for lack of a better word 🙂 . I borrowed syntax from several pseudo-codes. It took me almost two years to implement all the necessary features keeping in mind a broad range of algorithms. I developed an interpreter to translate this language into an intermediate representation with callbacks to an animation library. This summer, I finally implemented the animation library and the front-end in Objective-C. The result is the Algorithms App for iPad, released on Sep 20, 2012. This is my attempt to teach as many algorithms as possible by intuitive visualization and friendly exercises.
Features
Current version has Sorting algorithms (Insertion Sort, Bubble Sort, Quick Sort and MergeSort). The main advantage of my framework will be demonstrated once I add graph algorithms. I will add some “adaptive” exercises and games too. For example, one of the games is to predict what is the next matrix entry that will be filled next by an algorithm.
Also, I have the necessary framework to visually demonstrate recursion (by showing the recursion tree), dynamic programming (by showing the status (filled or waiting to be filled) of matrix entries), divide and conquer (by splitting the data) etc. Since the framework is ready, adding new algorithms will not take much time.
Here is a screenshot of Quick Sort in action.
Platforms
After I developed the interpreter, I was wondering what platforms to support first. I went ahead with iPad because I developed the interpreter in C. Objective-C is a superset of C. The Mac desktop version should be available in couple of weeks. In the long run I will implement the Android, Linux and Windows 8 versions too.
Goal
The big goal here is to “almost” replace an algorithms textbook. I added a button to access relevant wikipedia articles (within the app) describing the corresponding algorithms. With simple pseudo-code, intuitive animations, adaptive exercises and easy access to online articles, I think this goal is definitely achievable.
Questions
I have some quick questions to all the instructors and students of Algorithms.
- What algorithms do you want to see soon i.e., what algorithms did you have most difficulty learning/teaching ?
- What are some current methods you use to overcome the limitations of “static” textbooks ?
- Any more ideas to make algorithms more fun and cool to learn/teach ?
I wanted to write this post after achieving at least 100 downloads. I assumed this will take a month. To my surprise, there were 100 downloads from 15 countries, in the first 40 hours. I guess I have to add new features faster than I planned.
TrueShelf and Algorithms App are new additions to my hobbies. The others being Painting, BoardGames and Biking. Man’s got to have some hobbies. 🙂
Follow Algorithms App on Facebook, Twitter and Google+.
Download Algorithms App for iPad
——————————————————————————————————————————————————
My Brain is Open 