Ramesh's Bus Problem

I am reading a few interesting scriptures on Algorithms. As I come across many algorithms which solve spcific tasks related to various problems, I started wondering if there is any 'Best' way of solving my 'Bus traveling' problem.

This is the problem I face everyday and I follow a certain way to tackle this problem. It is actually somewhat interesting if you are a frequent traveller using public transports in India.

My mode of communication from my home to office is public transport buses (BMTC - Bangalore Metropolitan Transport Corporation). The frequency and timing of the buses are erratic which I will define as the 'Degree of erraticity'. I generally have to change buses at three different points. I begin from my house and the bus stop near my house is the first place. I have to go to Bangalore Central Bus Stand which is my second. From there I got to another place called Marathalli which is just 1.5 kms from my office and I board a bus from Marathalli and reach my destination. I stay nearly 22 kms from my office. The distance from my house to Central Bus Stand is nearly 4 kms. Distance from the central Bus Stand to Marathalli is 16.5 Kms.

Now regarding the frequency of the buses. The frequency of buses from the bus stop near my house to Central Bus Stand is atleast one every 5 mins. This is really erratic. Sometimes, more than one buses to the same Central Bus Stand come one behind another and there is a small war between the buses as to who reaches the destination first. Sometimes, I would have to wait for nearly 15 minutes at my bus stop to get a bus to Central Bus Stand. It takes 15-20 minutes to reach the central bus stand from the stop depending on the bus. I have observed that there is atleast one bus between 6:10am and 6:15 am for certain. Sometimes, there are two and one of these two is really fast and I can reach Central Bus Stand in 15 minutes.

Once, I reach the Central Bus Stand, I have two option. There is a bonus bus which takes me directly to the office from the central bus stand and the frequency is very low. The driver of this bus is drives at normal speed and I can reach office in 40 minutes. One every 40 minutes is the frequency. There is one of such buses which leaves Central Bus Stand between 6:25am and 6:30 am. Once every 3 days he is really late and leaves the Central Bus Stand at 6:40. The route number of the buses plying between the Central Bus Stand and My office is '333W'. While, there is another option, which is the more general. I will have to get into that bus ,get down at Marathalli and board another bus from Marathalli to reach my destination. The frequency of this bus is pretty high. 2 buses every 5 minutes. But, there is a catch. I have observed that a few bus drivers drive the bus fast and I can reach Marathalli quite quickly compared to other bus drivers who drive at the normal speed. The extra overhead time if I travel in the buses which are driven by slow drivers is around 5-15 minutes. If the bus is fast I can reach Marathalli in 30 minutes. The route number of the buses plying between Central Bus Stand and Marthalli is '335E'.

From Marathalli to my office, distance is around 1.5kms. I will have to board another bus from Marathalli. But, the frequency is really low. One bus every 10 mins. But, I have an option here where I can get into a private cabs and reach the office, but, this comes at an extra cost. The extra cost is negligible, provided I do not take this option everyday. It takes 5 minutes to reach my office from Marathalli. If I leave my home after 6:30am the time each stage takes gets increased by 10 minutes.

Provided these conditions only, what is the most efficient way of travelling to Office ?

This is the problem I face everyday and I follow the following method to reach the office:

I reach the bus stop no matter what, between 6:10 and 6:15. I reach Central Bus Stand. I start searching for 333W, the direct bus to my destination. If I do not find the bus, I get into 335E. I reach Marathalli. Once, every 2-3 days I wait for 10 minutes to get a bus to reach my destination. Once in a while, if I am lucky, I get the same 333W which would have left late. Once in a while I take the private cabs. Is this the best solution or do better ones exist ? Can it be proved mathematically ???

This problem becomes more interesting once we start thinking more about that. Answers anyone ?? :-)

My first course in Algorithms - (As an instructor)

Although I have given a few seminars and spoken to a large gathering quite a few times, teaching in class for one full hour is a a complete joy. I requested my professor to give me an opportunity to teach the students of electronics branch about algorithms. Algorithms as a core course is not present in the electronics branch and hence, my professor Mrs. Geetha Prakash was also willing to let me teach. Today was the first day of my teaching. A lot of the guys who were in the class seemed disinterested but, I knew that would be the case since I was also completely disinterested in a few classes when I was a student in PESIT. But, I was glad that the mojority of the class was interactive. I knew a monotonous kind of teaching would certainly put people to sleep (as it happens in most of the meetings in the companies). So, I decided to throw in a few puzzles to the class and tell them something interesting so that, they would keep thinking and their attention did not drift towards anything else.

One of the things that I told them was the history of the 'e'. I also told them how did the logarithm table work. It is interesting that most of the students do not know how the logarithms work. When we were in our High School, we were asked to work out everything using logarithms. Calculators were banned in classes and examination. Everyone in today's class knew how to use logarithm table but, interestingly very very few seemed to know how it worked.

A * B / C had to be calculated and A, B and C were large numbers. They know how to get the answer using the log tables. Use the log tables (to base 10 ... Which few seemed to know) and get the 'magic' logarithm values for A, B and C. Add the log values of A and B and subtract the log value of C. Then use the anti-logarithm table and get the final answer back ... ta daaaa ... Magic !!!!

Converting a complex multiplication and division to a very simple addition and subtraction seems to be a magic. But, behind the log tables is a very very simple technique which any High School student if given the task properly can accomplish. Yes ... A high school student can write a log table. It was 6 years ago that I was fascinated by the log tables and thought that the inventor of the log tables was a magician. When I expressed this to a very very good friend and a mentor of mine, he laughed and said, there is nothing great about it.

Any number can be expressed as a power of any other number. When we hear the base of the algorithm being 10, it means that the number A is expressed as another number 10 ^ x.

A = 10 ^ x
B = 10 ^ y
C = 10 ^ z

A * B / C = 10 ^ (x+y-z)

Hence, we add the log values of x,y and subtract z from it. When we have to find anti-log, we just raise 10 to the power of (x+y-z) and there comes the answer. Interestingly, everyone in the class was able to understand (if not appreciate because of its simplicity). Everyone knew what was happening in each step and everyone had done things like this before. Only thing that made the difference was the inability to link it and come up with a conclusion.

Similarly, when I explained insertion sort and asked them to write it in the form of algorithm, they seemed apprehencsive, but, when I started writing the steps they came up with the next step. I began to realize that, inspite of students being very intelligent and very smart, they were a bit apprehensive... May be due to lack of confidence. I am not sure. But, explaining insertion sort was fun. There are a lot of places where insertion sort is explanined with animations, so, I wont be writing about it ... I found the following like very useful and informative

 http://www.sorting-algorithms.com/


Most of the students knew that,
e = lim (1 + 1/n) ^ n as n tends to infinity

(value e = 2.71828182845904523536028747135266249775724709369995...)

It seemed to have weird resemblance with compound interest formula.

If the interest is compounded q times a year: A = P(1 + r/q) ^ nq


When I googled a bit for it ... Indeed ... I was correct... It did have it's root in bank. Jacob Bernoulli seems to have come up with this constant when he was calculating compound interest. He came up with the above number.

I will write a few more blogs on algorithms in the subsequent entries. Mathematics has always astonished me. It remains the best subject to study. When I get depressed or the day doesn't go fine ... I deal with them by reading up a few math stuff ... And it always works !!!