Algorithms Presentation @ General Hackers, 11 Oct 2013

Shortly before the end of my internship at BillPin, I was introduced to Calvin Cheng. I was told that Calvin is a founder of several successful startups, which is a pretty amazing thing. I had a great chat with Calvin, and it’s really nice to see that there are people in Singapore who are passionate about up and coming technologies (some would say it’s already proven, depending on who you ask) such as Scala. I also found out that he organizes weekly sharing sessions on Fridays, inviting speakers to give a talk on their own expertise, mostly to do with an area in computer technology.

With some of my colleagues, I sat in for a sharing session on AngularJS; it was ok, most of the things I’ve learnt from my work. So it was then that I discovered that Calvin is really technical, discussing some AngularJS details with the speakers, and editing some code for one of his products to use better AngularJS practices, kind of like a mini code review session. I was like, wow. It’s quite rare to see someone in a leadership position care about all these nitty gritty details and understand that such details are one of the key difference makers.

Somehow, one thing led to another, and I was invited to be the speaker for a sharing session on algorithms. I gladly accepted this opportunity, seeing how I’ve enjoyed some really good algorithms modules taught by Steven Halim, one of my mentors at NUS. (Side note: If you are a CS student at NUS, I highly recommend you take his modules)

So the sharing session happened on a sunny 11 October afternoon. The slides can be found here:

http://yanhan.github.io/algo_ghackers/#/

It was really challenging to prepare for this. But the main challenges are as follows:

• The audience may or may not have a formal Computer Science background. In fact, this is the main challenge.
• Algorithms is commonly viewed as a very dry topic. And truthfully, it can be, and very commonly, is the case, depending on the way one presents it.
• Most of the people attending the talk are probably very experienced software engineers with an eye on practicality. Truth to be told, learning about computer algorithms may not be the most immediately rewarding endeavour.

To address these challenges, I decided to focus on a few things:

• Cut down on unnecessary theory, and focus on the important ideas. Only as much theory should be presented to sufficiently get ideas across.
• Present some interesting applications. I find Steven’s use of algorithmic problems in his various algorithms modules quite interesting and effective, so I took that approach.
• Give an overview of some areas that are very often too deeply wound up in theory in a formal Computer Science course, such as NP-Completeness, and show their practical importance.

As with a lot of things in life go, you may start out thinking like this:

“Hey, I’m on a beach, the ocean seems pretty nice… how nice would it be if I could just go into the ocean…”

But for all you know, when you do actually go in, you may be heading straight into this:

And that was exactly what happened to me. I still feel quite apologetic to those who attended the session and expected something more.

First, let us take a look at an overview of what I decided to cover:

• A crash course on Big O notation
• Algorithms - some practical motivations
• Graphs - Terminology
• Graph Algorithm I - Breadth First Search
• Graph Algorithm II - Dijkstra’s Algorithm
• NP-Completeness - on the Travelling Salesman Problem
• Undecidability

You can probably tell that I didn’t finish on time, given this long list of topics. In fact, I greatly exceeded the time allocated and I stopped at the end of the NP-Completeness portion. So it is to my horror that I discovered that I was already 45 min into the session when I reached the section on Breadth First Search… Soon, I started seeing people leaving (due to time constraints), and everything just went downhill. Thanks for those who stayed till the end.

Some key mistakes:

• Trying to cover too many topics
• Slides are too wordy and probably not too good for a presentation
• Too many details in going through the 4 algorithmic problems in the BFS and SSSP sections, unable to cover them thoroughly

So if you are a really smart CS student and wondering why your lecturer cannot go faster, it’s really not that your lecturer doesn’t want to go faster, but that he/she cannot go any faster. You can only cover 1 or maybe just 2 topics in detail within a span of 1 to 2 hours. Trying to do more will be suicide. This is speaking from my very disastrous experience.

Some reasons for the choices of topics:

• Big O notation and algorithm analysis - needed to have some common ground for discussion.
• Practical motivations - hopefully get the audience interested. Admittedly, a good portion of this can be omitted.
• Graphs - I didn’t want to cover the usual things in a first algorithms course, such as classic sorting and searching algorithms. Graphs are very pervasive and appear in day to day software engineering work, and as such, may be more immediately applicable.
• NP-Completeness - Something I think didn’t get covered too well in school, or maybe I’m just a bad student. In particular, I find that the practical aspects are often left out, and CS students have to learn some examples of pretty difficult reductions, and do some even more complicated ones as part of a homework assignment. All the while, they may not know the practical importance of such problems, yet they have to stare at complicated reduction proofs. Not exactly a good motivation recipe.
• Undecidability - These days, totally not covered unless you take a theory of computation class or something similar at upper undergraduate or graduate level. I do not know too much about this, but then, I do not think that one can call himself a CS graduate without knowing a bit about this; in particular, that there are some things which we can never compute. Yes, maybe not very directly useful to your day to day work, but some of the stuff I’ve read on this topic is simply mind blowing. The fact that there are things that we can never compute should set you thinking. Oh and, by the way, that was discovered by Alan Turing in 1936, before the first electronic computer was invented. You can read more about it here.

I promised to upload the slides somewhere, so here’s the link again:

http://yanhan.github.io/algo_ghackers/#/

which is, kind of abusing Github. Actually, nah. That is to be followed up in the next post.

On a serious note, I think the slides may make for some ok reading. Come to think of it, I was reading through it all the while I was preparing them, so maybe it seemed natural to me that I wouldn’t exceed the time limit. Ah well. Verdict: TLE. Time to think of better algorithms to get AC.

On closing, if you do know of good talks on algorithms that take up 1 hour or less, preferrably not in some really specialized area, I will be interested to know more.

Credits

Big thanks to Calvin for giving me this opportunity. I sure hope I didn’t decrease everyone’s interest in algorithms.

Big thanks to Steven for sharing his knowledge with the world, and kindling my interest in algorithms.

And to those who came down for the session; I truly appreciate it.