CSC165 sLog: Week 8

Complexity. The week took to topic that has a vital role in a computer programmer's life. How different algorithms can do the same thing. Exactly same. But, still a lot different. It's not just about the expected outcome, but also the quickest and the least expensive method.

Problem Solving aspect mixed with a topic learnt in class:

I had watched a lecture of Harvard's CS50x course by David Malan which had something very intriguing to the same topic. I'll like to brief it out here, as it left a great impression on me about run-times.

He did a practical experiment in a class of 700-odd students. The aim was to calculate the number of students present in the class as quickly and efficiently as possible. So, one way was to go to each student one by one and count. Or, count taking two students at a time (2 + 2 + 2 + ...........).

Then, he proposed an algorithm. It showed up on the big screen and was the following:
1) Stand Up.
2) Think to yourself, 'I am #1'.
3) Pair up with someone; add your numbers together; take the sum as your new numbers.
4) One of you should sit down.
5) GOTO step 3 if still standing.

The video: https://www.youtube.com/watch?v=79gAss0K1TI&list=PLhQjrBD2T382Lqs7bsMl6WRDA9anaEzBe#t=1226

So, all the 700-odd students stood up. In first round, half of them sat down, with everybody standing with number 2 with them. This continued, and next half of remaining sat down. And it continued. Till only one student was left, with the number of students with him. The amazing thing was, it took less than 10 steps as from ~700 we had ~350, followed ~175 and so on. Rather than going through all the 700 students, it was done in just 10 steps. Isn't it awesome? It was to me when I first saw it for sure. From a linear counting, it showed an easy way to calculate it exponentially.

This is a great example that presents that there are various methods in which you can solve a problem, but it comes down to the fact that your solution must not only be efficient enough to give the desired results, but also fast enough to solve it. As I mentioned, the most simplistic idea that comes to the mind is to count the number of students one-by-one, but sadly it is one the most inefficient way to solve our problem. Dealing more into it, the method proposed by Prof. Malan opened a new thinking approach that the simplistic answer may not be the one you're looking for. Moreover, the perfect (or nearly perfect) answer must not be a very complicated or hard-to-grasp, as we see in this problem, the algorithm was fairly intuitive.