Algorithm Design Workshop: Day 2 (April 2nd 2017)

images (6)

How would you feel if you were to work on one single Math problem for two hours at a stretch? Most people would never even dare to think about it. The second session of Algorithm Design Workshop saw 9-13 year old kids working on an algorithm and turning it into a flow chart for two hours. I have to admit that what they have discussed and discovered would seem to be a very challenging task for most students of Computer Science. The whole session was about the following (in the order in which the questions were discussed)
1. Why do we have leap years?
2. Why are years like 1700, 1800, 1900 not leap years but 1600 and 2000 are leap years?
3. What is the condition for a year to be a leap year?
4. Write an algorithm (for the computer) to check if the given year is a leap year or not.
5. Among the different possible Algorithms, how do we compare and decide a better Algorithm? (In the terms of Computer Science, how do we calculate the running time of the Algorithm).
6. How can we find an Optimal Algorithm (the best Algorithm)? And why is it the Optimal Algorithm?
7. How do we prove that there cannot be a better Algorithm than the Optimal Algorithm that we have got?

Any Computer Science student from India would agree that in the college curriculum, if a question on writing an algorithm is asked, they would cover at the most points 1-4 where the concept and figuring out an Algorithm would be discussed, but not points 5-7. Whereas, points 5-7 are the most important points a programmer would be (rather, should be) concerned about. It is the speed (running time) of a program that makes a program efficient. And if someone has to check if his Algorithm is the best, he needs tools from Mathematics to prove that there cannot be a better Algorithm than his.

For the readers who are not familiar with Algorithms, here’s what Algorithms are about. It is a step-by-step procedure for executing any task. When a programmer has to write a computer program, he needs to know a programming language and the logical process that will have to be taken into consideration for writing the program. This logical process is the Algorithm which turns into a Computer Program with the help of a Programming Language. Most students are taught programming languages, but rarely are they taught How to Program (how to develop the Algorithm/thought-process behind the program).

Coming back to the class. In one of two batches where we did the above topic, we completed upto point #6 and some students started to come up with answers for point #7. In the other batch, it was almost the same scenario and we discussed another question of finding day of the week for any given date. The objective was not to give out the solution for the problem but to make them think, strive and try to develop an algorithm for getting the result. Some of them got it at the first go while some struggled and still didn’t get it 100% correct. But what they learnt cannot be measured in quantifiable terms. They learnt that learning is not about getting the answer, but the attempt to arrive at getting the answer. They learnt that in the times when everyone wants a quick solution, real learning requires Time, Effort, Patience and Perseverance. And most of all, they learnt to Think.

As they finished one attempt for an Algorithm, they came up to me to check if it is correct. The others patiently waited in a line behind them. For them, the most challenging task was to understand what was wrong in their Algorithm. In fact, when it comes to questions on logic, many a times it is difficult to explain why is a process/solution wrong. But they were willing to think and make corrections in their Algorithm and come back again. This might have gone for about 3-4 times with each student in one of the batches. In the other batch, some students worked in groups and tried to solve the problem.

The​ most difficult task (and the most important one) was to compare two correct Algorithms and decide which one is a better choice. And the question that would concern a Computer Scientist was How to find the best Algorithm and prove that it is the best? To give you a taste, here are a couple of Algorithms that you might want to consider comparing.

Algorithm #1:

Enter a year
Ask the question – Is the year an odd number?
If Yes, then print – Not a Leap Year
Else (if No, then), , ask the question – Is the year divisible by 400?
If Yes, then print – It is a Leap Year
Else, ask the question – Is the year divisible by 4?
If No, then print – Not a Leap Year
If Yes, then ask the question – Is the year a multiple of 100?
If Yes, then print – Not a Leap Year
Else, print – It is a Leap Year

Algorithm #2:
Enter a year
Ask the question – Is the year a multiple of 100?
If Yes, then ask the question – Is the year a multiple of 400?
If Yes, then print – It is a Leap Year
Else, print – Not a Leap Year
If No, then ask the question – Is the year a multiple of 4?
If Yes, then print – It is a Leap Year
Else, print – Not a Leap Year

The running time of an Algorithm can be said to be the number of questions that one needs to attempt ‘at the most’ to arrive at the answer. In the first Algorithm, you can see that if the year is an odd number, we get the result in just one step. But if the year is an even number, it might take three steps (because one might have to go through three questions). So the running time of the Algorithm is 3. Let’s say that the Algorithm is 1-3 where 1 refers to the minimum number of steps and 3 refers to the maximum number of steps. In the second Algorithm, it is 2-2. There were other Algorithms which were 2-3, 3-3, etc. So when it came to the question of choosing a better Algorithm, everyone unanimously agreed that 2-3 and 3-3 are poor choices. But selecting between 2-2 and 1-3 was a tough choice. How do we find out, which one is better? How do we know if there could be a better one? The participants said that an ideal scenario would be 1-1. But there cannot be one single question which can determine if the year is a Leap Year or not (they didn’t get time to prove it in the class though). Using such logic, how do we arrive at the optimal solution and how do we prove that it is the optimal solution? I leave that to you.

For me, the greatest joy was seeing their perseverance in solving one single problem for two hours and the different learning outcomes mentioned above.

Life is about making choices. If this activity might have helped them in a subtle way to decide which is a better choice, I think the objective is fulfilled.