An Algorithm to Discover Algorithms

In August 2013, I started working on my second research problem of my PhD — to develop an algorithm to automatically discover divide-and-conquer algorithms for a class of dynamic programming problems. Dynamic programming is a magical technique to design algorithms when used many problems can be solved very efficiently. Dynamic programming is used in computer science (compilers, computer graphics, computer vision, computational biology, databases, etc), mathematics, operations research, physics, astronomy, material science, agriculture, and so on. Divide-and-conquer is another sexy technique to design algorithms that are super-fast and highly portable across machines. The aim was to design a solid algorithm such that it can discover fast, portable, and robust algorithms automatically and anyone who has no expertise in computer science can also generate algorithms using our algorithm in their respective fields.

Divide-and-conquer algorithms
As my first research problem was totally different and unrelated to my second problem, I had to first understand how to manually discover divide-and-conquer algorithms one-by-one given a problem and then try to find a pattern so that a computer can discover them automatically. In a couple of months I understood deeper about the divide-and-conquer algorithms and fell in love with them more and more. I designed several divide-and-conquer algorithms for problems such as spoken-word recognition, function approximation, binomial coefficient, and so on. In the process, I understood my second problem a bit more. Given an iterative algorithm, our algorithm had to discover a divide-and-conquer algorithm. In around November 2013, I got a beautiful idea of breaking each for-loop of the input iterative algorithm into two parts to find a divide-and-conquer structure. My intuition was that the approach will lead to a recursive pattern from which we can find the recursive divide-and-conquer algorithm. I worked on it for a couple of days and it did not give me any result.

Algorithm to discover divide-and-conquer algorithms
Probably on December 14, 2013, my adviser Rezaul called me for a meeting. In 1-2 minutes he explained to me an idea to automatically discover algorithms. That instant I knew that it was one of the most amazing computer ideas I had seen. I told my adviser immediately that the idea was mind-blowing and I was too excited to work on it.

Rezaul and I both knew that the idea must work but for a quick confirmation he asked me to implement the algorithm. The problem was that it was just an idea and not a complete algorithm. An algorithm must be unambiguous. So, we had to formulate a mathematically precise algorithm from the idea. While implementing the algorithm, I had to formulate mathematics to fully describe the algorithm. Whenever I was stuck, I discussed with Rezaul and he helped me to get out of that stuck point. Within probably 2 months I was able to implement a prototype of the core algorithm and get results for several problems. Our algorithm was able to generate algorithms to at least 10 different problems. I was super happy.

Proof of correctness
I was majorly involved in developing the mathematics of the algorithm and in a couple more weeks, we had the algorithm formally defined. We had four steps in the algorithm and each step was extremely important. Here is a tip if anyone wants to design an algorithm: any idea that is not mathematically proved correct is worthless in mathematics and in theoretical computer science. So, we had to give a mathematically powerful proof to prove that the algorithm was correct and the algorithm was able to discover a correct divide-and-conquer algorithm given a problem. The difference between non-science (such as religion) and science is just this: proofs, evidences, and observations. Unless we prove that an algorithm is correct, it is almost worthless and any researcher will not use it. So, we had to come up with a proof of correctness for our algorithm.

Life is really simple. But it takes a genius to understand it. I will elucidate this point using two examples. When I was in college I used to discuss a lot of puzzles with my friend Jackson Menezes. He would give me tens of puzzles to solve and I would try to solve them. Once, I gave him a tough puzzle and he thought a lot on it and finally solved it in 35 minutes. I was surprised. I congratulated him and asked him how he was able to solve the problem. He told me that the puzzle was really a simple problem. I was confused. It was hard for me to solve and he took 35 minutes to solve and how could he possibly say that it was really simple. He told me that the puzzle was simple to solve and it took him only 5 minutes to solve the problem but it took him 30 minutes to understand that the puzzle was dead simple. This scenario repeated for me too. I had no shit idea what constitutes the proof of correctness for our algorithm and what does it mean to prove that our algorithm is correct. I did not have an answer to this question for over a month. One fine day I realized that to prove that the algorithm is correct, I need to prove that the output of the output algorithm must be exactly same as the output of the input algorithm. With that realization I could easily prove our algorithm in may be maximum 2 days. Then I realized that the solutions to several problems are really really simple. Just that we must have the patience and dedication to realize it.

Publishing in a conference
In several months, we developed several extensions to the algorithm and gave several improvisations. With more and more ideas the paper became stronger and stronger. My colleague worked on the implementation and optimization of the divide-and-conquer algorithms and these algorithms ran very fast compared to the state-of-the-art algorithms. We wrote a paper and submitted it to a conference. The paper got rejected. One of the very useful comments in the review was that if we can theoretically analyze the complexity of the automatically discovered algorithms that would be great. It was slightly complicated to analyze the complexity but I was able to get a general formula for the runtime complexities of the output algorithms and we added this to the paper. The paper got rejected three more times. With a total of four rejects, the paper got accepted to a top-level parallel algorithms conference called Principles and Practice of Parallel Programming (PPoPP). Several months of hard work finally paid off.

In January and February 2016, I worked on my documents to get a visa to Spain (or in general, visa to Schengen area which is 1 visa to enter any of the 26 nations in Europe). I booked my flight tickets, hotel, and registered for the conference. With all the relevant documents I got short visit Schengen visa in 15 minutes. The visa was valid for 18 days I believe.

Presenting the paper
After 2.5 years since we started working on our algorithm, in March 2016 I went to Barcelona, Spain to present our paper. I reached my hotel room in Barcelona on March 13, 3:30 pm. I prepared for my presentation. The next day, on March 24, 2016 I presented the paper. The time given to me was 25 min. It was an okay presentation. Several people liked and were interested in the work. They asked a lot of doubts as well. That day I did not see much of the city. I came home and watched a movie. I was happy that the presentation got over. The next day I tried to listen to the presentations carefully. I was not able to understand the presentations in all my previous conferences. But this time, I was able to grasp more because I had more experience in parallel algorithms. As a 5th year PhD student specializing in parallel algorithms I think I could understand between 1.5 to 2% of the total knowledge presented which was way more than my experience of previous conferences.

Excursion
On the second day of the conference (March 15), there was an excursion of Barcelona for the participants. They took us for almost 4 hour trip and showed us several places. Our guide was so sweet. She was beautiful and was able to answer any question. We saw from outside one gigantic structure of a church called La Sagrada Familia Church which was designed by a fucker architect Antoni Gaudi. It was one of the world’s top attractions. It was so huge that you need more than 30 minutes just to see it briefly from outside. We did not go inside as it takes more than 1 or 2 hours to stand in the ticket line itself. The details on the building were enormous. They say that the construction of the church which really started almost 100 years is still being constructed and supposed to end at 2026.

We visited the La Rambla street, Placa de Catalunya, and the Gothic Quarter which has the ancient Roman style forts and buildings. I loved the streets near the Gothic Quarter. Probably they are the best streets I have seen till now. The architectural beauty is laudable.

Banquet dinner
The trip team dropped us at a high level hotel where we had our banquet (formal evening meal) dinner. There was unlimited wine there. For me the place where there is unlimited alcohol is heaven. I am both alcoholic and algoholic. Alcohol brings me happiness.Even if I become a billionaire in the future I would find more happiness in the free stuff. And if the free alcohol is unlimited, one does not need heaven. I drank a lot of wine (they were just the starters). After then there was some food. It was ordinary. While eating I ordered for more glasses of wine and drank more. In the table I sat I met two undergrad Professors from teaching universities and one researcher (may be from a research university). I asked the Professor sitting beside many tips about how to teach better and what techniques / strategies he would use in teaching. We discussed a lot on teaching, teaching, and teaching. The Professor told me that generally people are not interested in teaching and they think undergrad Professors are not that important compared to grad Professors.

The researcher who was on my other side tried to kind-of ridicule the undergrad Professor saying indirectly that Professors from teaching universities do not do research which requires deeper thinking and it is very tough and teaching is not that important. I was listening to his arguments and I felt bad. My own infinitely deep and unparalleled respect for teaching and learning and the liquid God that was inside my divine body gave a tight response. I told the researcher that research is a very tiny component of teaching / learning. Research is nothing but deep understanding and that deep understanding majorly comes from learning. The learning is highest when it comes from teaching. A researcher reading a paper is really learning from the paper’s author and the author is really teaching. A great researcher solves may be 10 good problems in his life but a teacher produces 10s of researchers, doctors, engineers, etc. Teaching is undoubtedly a gigantic superset of research. I think I started shouting as well by getting deeply involved.:) I literally thought I was a security guard to defend the goodness of great teaching and great teachers. Any person in all Cosmos who had something bad to say against great teaching had to cross the mighty me. At the end I gave the undergrad Professors my own opinions and ideas to improvise teaching. While returning to my hotel which was approx 1.4 km from the conference venue, I spent more time to feel the beauty of the city.

Barcelona city
I loved Barcelona. It was one of the beautiful cities (“beauty” is relative) I had seen apart from New York City, Las Vegas, Mysore and a few others. It was highly developed, probably more developed than many of the cities I have seen in USA. The roads were very wide and I could see several double-decker buses and electric trains. Everything was expensive. People walking around looked like millionaires to me. They were so white and fair. The girls were so beautiful and gorgeous that I felt like I wanted to make love to each and every beautiful lady there. I thought I could go to a  prostitute to lose my virginity (I have lost my virginity virtually but not physically, unfortunately. :)) but then thought that it might be illegal and I did not have enough guts to do so either.:) I returned to room and was a bit tired. I went to take a bath at midnight. It was cold outside and I liked the hot water. I filled the tub with hot water and tried to sleep there imagining the hot water as my bed sheet. But after 20 minutes or so, the water would turn cold and I had to get some new hot water again.

The third day of the conference (March 16, 2016) did not have many talks. All talks ended at around 12:30 pm. I had to search for some good place to eat. I struggled to get good food that would fill my stomach. Europe is a hardcore consumer of meat. Europeans, like Chinese, I think eat almost every living thing that moves apart from humans. I struggled to get any vegetarian food. Once, when I did not get any vegetarian food I ordered for a sandwich with salmon. I ate some part of salmon but could not eat it anymore. Hence, removed it and ate the rest. Most of the times I ate either pizza, bananas, bread, something like this. And none of the food I got filled my stomach. Bad experience with food. I returned to the room and slept in the bath tub again with hot water. When I woke up in the evening I checked a few places at Barcelona to roam around for the next day.

Park Guell
The fourth day (March 17, 2016) was a roller coaster. I woke up in the early morning and left room. The first place I visited via public bus was Park Guell, a public park consisting of beautiful architectural buildings and park. This park was designed by Antoni Goudi, one of the greatest architects of the world and the park was built before 1915. The park can only be described precisely by experiencing it. There is one major building in the park and several other smaller ones. The boundary of the terrace of the major building is filled with colored stones that look so beautiful. Standing on the terrace of the building we can see hundreds of houses and the coastline of Barcelona. If we enter the inside of the major building we can see probably 60+ big pillars and a roof. In several places of the roof, we see colored gem stores forming sexy patterns (like that of Taj Mahal). The architectural styles beside the steps that lead to the major building and small hanging gardens with colorful flowers look as if we are in a dreamland. It is such a romantic place. There were also several books on Antoni Gaudi, Barcelona, and Park Guell that were for sale. I checked out some of the pics of architectural designs from Gaudi’s books. They were fucking awesome. There I decided that I will learn the fundamentals of architecture from books. At that moment, my love towards art was more than that of science.

I think I stayed in the park till around 1:30 pm. And then I headed to Gothic Quarter. I could have taken buses but I preferred to walk. I had to walk for at least an hour. I love walking as with walking we can really connect to the city and people. This connection won’t happen when we travel on bus, train, flight, and any vehicle that was / will be invented. Every street I went through was architecturally breath-taking and I took time to appreciate and digest the beauty and life I saw in those non-living things. The sides of the streets had gigantic pots with big plants. I wondered who planted those and who would water them and maintain those. In India, people do not give a shit for plants and trees. In fact, they do not give a shit for people too.:) Anyway, the Barcelonian streets were sexy. I could see some drinking systems at some places and they were also built with architectural wisdom.

Placa de Catalunya and Gothic Quarter
After sometime I reached Placa de Catalunya. That is the place where people usually meet or hang around. There were a few fountains and large marble flooring where tens of people were feeding rice to hundreds of pigeons. There was a fucker idiot who was scaring the pigeons when they came to him for rice. Some college girls were getting pics taken when pigeons fed on rice on their palms. There were loads of such scenes for practicing photography. After spending a good amount of time with the pigeons I headed to the Gothic Quarter. Gothic Quarter was probably a few kilometers from Placa de Catalunya and I walked towards it. Those streets were the most beautiful streets I had seen in my life. Reaching the destination I could see big forts and walls of Roman time. The walls were very wide and looked powerful. The color of the forts and walls was light brown. The doors were very tall and big. The winding and curves around the doors and windows were extremely complicated to design and create. The places in and around Gothic Quarter takes a lot of time to see. From there I went to Barcelona Cathedral.

Barcelona Cathedral
Among the places I have seen in Barcelona, the Barcelona Cathedral is my favorite. Any person who is a hardcore fan of beauty will be fucked if he/she sees this place. Such greatness is shown in creating this structure. The pillars are so huge. They do not just end at the room. They branch out into several parts and different parts from different pillars will combine into one and forms the ceiling. I wondered if there was some mathematical equation that governed such merging of different parts that the designer used. Hanging royal lamps, colored glass on the windows, a big musical instrument made out using extensive wood, and people silently praying — seeing all these was a festival for eyes. I also went to the top level of the cathedral to get the 360 degree view of the city.

From a nearby kind-of fair, I bought a souvenir. The items were really expensive. I wanted to buy a very tiny and sexy jewelry box for a gift, but it costed 180 euro. Hence, got something cheaper that I could afford. At that time I was too tired to stand or walk. I walked for 1 hour 30 minutes and reached my room. Took bath and slept. Next day I flew on top of Atlantic ocean where Titanic sank and returned to my place, Stony Brook.

In this way, the journey of developing one high-impact algorithm, publishing one paper in a top conference, and experiencing one beautiful place became a reality and now it seeks existence only in my memories.

This slideshow requires JavaScript.

« Older entries

Follow

Get every new post delivered to your Inbox.

Join 61 other followers

%d bloggers like this: