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.

#Mathematics
#AlgorithmDesign
#ComputationalThinking
#FlowChart
#Education
#LeapYear

Advertisements

Algorithm Design Workshop: Day 1 (April 1st 2017)

Algorithm Design Workshop: Day 1 (April 1st 2017)
 
It was a session for 10-13 year old kids that we did in two places – Thane and Borivali. Below is a gist of the experiences of the first day.
 
Since the objective was to get them introduced to Algorithms and Flow Charts, I asked them to make a flow chart where a robot has to check why the baby in the cradle is crying. I said, it could be crying for three reasons:
1. It is hungry
2. It has passed urine or poop
3. It is bored and wants to be taken out of the cradle.
 
The task was to write a flow chart that will enable the robot execute the task if these were the only three reasons that a baby would cry for.
 
The initial challenge was ‘how will the robot check if the baby is hungry’. On that one boy said that if a feeding bottle is kept in its mouth, it will drink from it. Another boy said that the robot will see if the stomach is full or flat.
 
Next task was to know if the baby has passed urine or poop. One participant said that the robot can touch it. I said that the robot doesn’t have a perception of touch. Someone said that the colour of the dress would have changed if urine or poop is passed. I said that that would be one way the robot would know. On that, one fellow jumped and said, the robot cannot touch and know but it can see? How could it hear the baby’s cry in the first place? Why is it that only one sensory perception isn’t working and others are working?
 
I gave some reasons for that but i was amazed by the thinking by the children.
 
In one of the batches, a participant said that the robot can find out if the child has passed or not by checking the weight of the diaper. (This was my favourite answer because weighing is something that can be practically done and checked).
 
The question that i loved the most was…’Sir, you said Computers are dumb because they cannot think on their own and that they need to be taught. So does humans because we also need to be taught. So how are we different from computers?’ I think this was a brilliant question for a 9-year old. In my reply I asked him, ‘Who taught you to talk, walk, cycle, swim?’ Promptly he replied, ‘My mother’. I asked, ‘Did you learn to talk by listening to her or was it like a classroom teaching? How did you get the ability to walk? Who gave you the cycle balance? Was it a discovery by you or were all these taught to you?’ I could see the bewilderment in his eyes and he nodded his head saying he got the answer for this question.
 
Another task was to explain to a person over the phone ‘How to draw a 5-pointed, 7-pointed and 8-pointed star? And this person who is listening doesn’t know what a star is.’ Basically, it was to write an algorithm which can be made into a program to make a star.
 
In the exercises, the children also learn to define concepts. E.g. In one of the tasks was to construct a star. While doing so, some constructed a 5-point star, some 6-pointed and some constructed very different stars which normally we do not think of. Most of them rejected that these different-looking stars to be called as stars. Thus we came to a point where one had to define what is a star. If a 6-pointed star can be constructed using two overlapping triangles, why don’t they accept two overlapping squares as a star? Once a common consensus happened on definition of a star, we came to algorithm to construct a star. Some of the started saying…Join point A to point B …but later realised that we haven’t defined the positions of points A and B. Some said, draw a line diagonally a bit longer …but then they realised that they have not defined what is a ‘diagonal’ and to which direction are they refering to and how long is ‘a bit long’? Through all this, they kept aside all their pre-conceived notion of a star and started defining terms and processes without taking anything for granted.
 
Another example that we discussed was – how to return the discounted amount when we buy something in a combo-offer? The best thing was the students themselves discovered each and everything. All i had to do was to introduce them to how a flow chart is drawn. Rest of the things followed on its own. In fact, a lot of exploration was done on star shapes and Algorithms to draw those stars. I was quite amazed to see three 9-year olds working with full enthusiasm and rigour on the problems. So was on 6-year old (a guinea pig) who was an experimental piece in the workshop.
 
My learning: No topic is boring. It is the examples that can make a topic interesting or boring.
 
While everyone celebrated the FOOL’s Day, we did something more MeaningFUL!
 
#AlgorithmDesign
#Algorithms
#Mathematics
#Education
#SummerCamps
#FlowChart17546775_1462448087119675_3769436404707352928_o