Sunday, August 24, 2014

Accessing files on android via MTP on Linux

I recently purchased a Motorola MotoX from an AT&T store. Although it is a fabulous piece of hardware, the first trouble i encountered was getting access to files on my fedora 19. The internal memory was not being automatically mounted neither via MTP nor PTP. This was a bit frustrating.

However, the problem can be solved in 15-20 mins with a bunch of yum install commands. One needs to install gMTP and its dependencies which can be found here. Download the source code and extract it. Run ./configure, make and make install. If you encounter errors like 'Package somename was not found', you need to explicitly install it and re-run ./configure. I personally remember installing at least 5-7 dependencies before i got it working.

e.g. yum install fuse-devel libid3tag-devel libmtp-devel libmad-devel fuse fuse-libs libmtp simple-mtpfs glib2-devel

Once done, run gMTP and enable MTP mode on your android phone. You should now see the files listed in the gMTP window as shown below

Tuesday, February 11, 2014

Inmobi Hackathon 2014 : Experience and review

Last week, i attended Inmobi's hackathon organized at their Bangalore campus. It was dedicated to Aaron Swartz, a brilliant computer scientist who gave up his life while fighting surveillance and for a free and open internet world. Therefore, the hackathon was named as "FreedomHack". It all started the week before when one of my friends called up to discuss an idea which he thought was really worth implementing and wanted to know my opinion. Realizing that it was worth our time, i agreed and we formed a gang of 3 guys who registered to attend the 24 hour hackathon.

I reached at sharp 9am (yes, it was on Saturday and it is difficult for us engineers to get up early). However, i was excited about our idea and took all the required hardware with me in a back-pack. My team-mates also reached within 10-15 minutes. If i recall correctly, there were around 44-46 teams consisting of 3-4 members each. We were given our ID cards (labeled "Hackers"), were asked to give our notebook's serial number after which we were alloted a big space to work.

My ID Card

My Team(from left): Saurabh, Harshit & Me

We spent the first hour planning our hack on what we really wished to achieve and how we would divide the work among ourselves. Our app was called "Go Green". It had two use-cases:-

i) Given two points (a departing point and an arrival point, be it any city or location in the world), our application would mark those two points on a map and would display the best path to follow such that the carbon footprint is minimized.

ii) If one has already traveled in the past and his/her gmail account contains a copy of the ticket (the ticket maybe booked by famous travel websites like, the application would fetch all travel details from one's email and show them within a single page. Then, if the user selects any of those journeys, the application would again plot the starting and end point of the journey and show the carbon footprint of the trip.

The basic idea of creating this application was two-fold:-

i) To make the users more aware of the increasing carbon-dioxide in the atmosphere and how they contribute to it.

ii) Help users in planning their future trips smartly by suggesting the best path to travel to minimize carbon footprint.

Furthermore, the application could generate revenue by displaying advertisements suitable to the mode of travel. So for example, if air-travel is involved, advertisements related to offers by airlines can be published. If one travels by road, then bus travel agencies can post their ads and so on.

Central point for free beverages
Inmobi offered us a feast throughout the event. They served breakfast, lunch on both days and dinner on the first day. Beverages and snacks could be consumed anytime by us throughout the event. In the evening, they also served burgers from McDonalds. Plus, we also got free Tshirts. There were some talks by invited persons on how to create better hacks and how to take our ideas to the next level. I felt that there should be no interruptions between the hackathon as it breaks concentration and rhythm. Talks are good at the start and end of the hackathon, but not quite in the middle.

Workspace allocated to each team

Anyways, we completed 25% of our application by the first day's evening. The struggle started when we encountered issues during integration. We spent considerable time in optimizing code and how data from the lowest php based layer could be handed over to the upper layer which would ultimately be displayed in the User Interface. At around 2:30 am after several cups of tea/coffee, we started resolving our issues and by 6am, we had completed 90% of the application. It was the result of the good initial plan which we had laid down when we started. Demos started at 10:30 AM on sunday and the hackathon concluded by 2:30PM.

My teammate trying to get a nap (for hardly 5 mins)
It was a great experience. I learned a lot during a short time and saw some clever hacks by my peers. Thanks to everyone at Inmobi for organizing a wonderful event and giving us an opportunity to display our ideas. Lastly, thanks to my team-mates for staying up all night and helping each other in bug-fixing and even encouraging when one felt a little low.
Technorati Tags: inmobi, hackathon, experience, 2014, review

Sunday, January 26, 2014

Battle of sorting algorithms (Which sorting algorithm is the best?)

I was recently going through MIT Opencourseware's Algorithms course by professor Erik Demaine and Charles Leiserson (fantastic teaching by the way!). After finishing up the lectures on sorting and worse case linear order statistics, an innocent question to ask is "Which sorting algorithm is best?". Mind you, the lectures are exhaustive and walk you through the running time of almost all discussed algorithms. But there are constraints and involvement of constants which hinder the practical applicability of these algorithms. In this post, i wish to delineate the algorithm selection mystery assuming you are sorting numbers. (You can extend the below mentioned analysis for floating points, strings and so on).

Algorithms based on comparing a pair of numbers and minimizing the number of comparisons have a tight lower bound of (n log n). This means that nlogn is the worst case runtime of the best comparison based sorting algorithm. And the best algorithm, in practice, is randomized quick sort.The advantage of randomized quick sort is that it avoids the worst case of quick sort (which might take upto O(n^2) time for selected inputs such as sorted or a reverse sorted array).

So, is randomized quick sort the answer to all problems?

As the lecture demonstrates, we can sort in linear time too. With algorithms such as counting sort and radix sort, it is quite possible to get a upper bound of O(n), where n is the number of elements to be sorted. These algorithms do not fall under the comparison based model.

So, are counting sort and radix sort the answer to all problems?

Not quite. Each of them is useful in their own way. For example, after going through the rigorous analysis presented in the lecture, i've come up with a criteria of when to use each of them:

1) Counting sort (Stable): Use it when

     i) You know the maximum number in the elements to be sorted.
     ii) All numbers are integers
     iii) You can afford to allocate two auxiliary storages of size equal to the number of elements.
     iv) The numbers themselves are not very large (perhaps less than 10,000). This limit can be increased if you can write a multi-threaded version of counting sort where you sort the numbers in parallel.

2) Radix sort (MSD implementations can be stable): Use it when

     i)  You know the range of numbers to be sorted
     ii) Elements to be sorted consists of only integers, fixed size strings or anything which can be converted to a fixed size integer.
     iii) The number of digits in each integer is less than log n where base of the log is the base of the number to be sorted. For example, if we desire to sort 10^6 integers which are all in base 10, then we'll check if log 10^6 base 10 is less than the number of digits in each integer. If yes, we'll go ahead with the sort. The logic of this check is explained in the lecture found here.

3) Randomized quick sort: Use it when

     i) When 1) and 2) cannot be applied.
     ii) You want to your algorithm to work well with cache.
Technorati Tags: MIT, algorithms, sorting, counting-sort, radix-sort, best-sorting-algorithm, quick-sort, randomized-quick-sort