My Stories: Personal Writing

The Collapsing Pyramid Algorithm
by
Vasudev Seeram

"Wrap up what you're doing and log out. The Centre is closing now." The operator exited the room and proceeded to the North Room where he would echo his command.

It was half past nine at the Computer Centre. I went over to PC 22 and checked my program. I had started the program at seven o'clock and it was still running. "Why was it taking so long?" I silently asked myself. I was certain that the computer had not crashed. I sat, staring at the flashing cursor, my mind whizzing away at the question just like the CPU of the computer was processing the program's data. And like the CPU, I was getting nowhere fast.

The operator returned and began switching off the computers. I reluctantly turned off my computer, packed my bag, and left.

The campus was dark, dismal and deserted. I felt depressed as I walked. Their were rumours that campus was a high crime region in the night. I began to wish I hadn't gone to the Centre. So why did I really come? I had to prove that I could solve this problem. Another guy had gotten his program to work fast. Why couldn't I? Sure, he was bright, but he wasn't Pentium-driven. And that was about all the edge I needed.

I started to have that crazy dream about my program again. The data for the program was arranged as follows:

It was a triangle filled with numbers, each layer of numbers containing one more number than the previous layer. From a number, you could traverse down the triangle left or right to the last layer. The object was to find the path with the largest sum of numbers.

As I lay pondering it, the triangle started to rotate. Then, as if unable to bear its own weight, the top layer collapsed onto the second layer, which collapsed onto the third, which collapsed onto the fourth and so on, until their was only one line of numbers. At each level, the numbers at that level increased in magnitude by that of the number that fell on it.

That was it! I could cumulate the result at every level of the triangle so when I was finished, I could just read off the largest at the bottom. But wait! When the largest was found at a level, the level was not referred to again. So there wasn't even need for a triangle, just a list of the largest numbers cumulated and the new data read. But how could I convert the new data read to the last data cumulated?

If I had a box labelled "Oranges" that was filled with apples and a box labelled "Apples" that was filled with oranges, how could I fix this situation? I could exchange all the oranges and apples. Or I could simply change the labels of the boxes, which was faster and easier to do.

I was at the Centre again the following night. Fully optimised, this new program was a mere fifty-seven lines and was executing at blazing speed. I also optimised my old program. My optimised old program took about ten seconds to execute for one hundred layers while the new one took less that one second. They both gave the same result so I assumed that they were both correct. I decided to give up the program, not wanting to come back the next day to print it. I left contented, at least having completed one item on my 'to do' list.

I had completely forgotten about the program in computer class the next day. As I was leaving, I heard a voice boom, "Seeram!" It was my lecturer, Mr. Kalicharan. "I got your program this morning, the one with the pointer to the array. It is the correct answer."

I felt elated. It wasn't just correct. It was the correct answer. I beamed like the morning sun as I walked home. All of the sacrifice actually paid off. And I heard a little voice say, "Great work, champ! I knew you could do it! Remember the old saying: Winners are willing to do what the majority of the population aren't." And life was great.