Thursday, March 27, 2014

Gyro balls and yoga

The Powerball is a relatively new gyro-based exercise device intended for strength building in the wrists and fore-arms. I'm using it to help me in my yoga practice.
Aasanas that require wrist and forearm strength are greatly benefited by using the wrist exercising gyro for 3-5 minutes a day.

For example, using the gyro helped me get going with hamsasana (where your fingers are pointing towards your face)
which is a lot harder than mayurasana (where your fingers are pointing away from your face, and towards your feet).

You can immediately spot the difference between the final pose for each posture.
  1. In hamsasana, your body is bent at the buttocks, whereas in mayurasana, the body is mostly straight.
  2. In hamsasana, your face is closer to the ground than it is in mayurasana.
  3. In hamsasana, you are bent further forward (angle that the forearms make with the floor) than you are in mayurasana.
  4. In hamsasana, your back is slightly more bent compared to mayurasana, where you back is mostly straight.
  5. In hamsasana, your elbow is further down your abdomen compared to mayurasana, where it is tucked into your stomach.
  6. Hamsasana needs more wrist strength compared to mayurasana.

Tuesday, February 18, 2014

To Muir Woods and back

S, V, and D went decide to bike to Muir Woods from SF Caltrain. I have a sore index finger, so this will be brief. This is the path we took in the going direction, and this is the elevation profile. On the way back we took a slightly longer route.

6:30am: Wake up.

7:55am: Leave for Caltrain Station

9:36am: Reach San Francisco Caltrain Station

9:40am: Purchase fruits and food items for the trip from Safeway

Here are our bikes:

10:00am: Start biking on The Embarcadero towards the Golden Gate Bridge

The Bay Bridge is on the way:

Some other exhibit. Looks like an arrow facing the ground:

10:05am: Arrive at The Bike Hut since V forgot their helmet at home The guy at the bike hut too a while to inflate his shop, but once he was done, offered V a helmet gratis. Very kind man.

Don't remember when, but reached the Golden Gate Bridge (south side) and then biked across to the north side of the bridge. This was fun. Didn't take any photos since there was quite a bit of uphill and we didn't think of taking photos at that time.

We reach the north side of the bride and rest for a while. Then take the road on to Sausalito. This road is marginally uphill but mostly downhill. I don't enjoy the downhill as much in fear of having to bike back up :-p

Reach Sausalito and can't believe the breathtaking views from the place.

Someone is flying a Quadcopter here as well. The battery life on these seems to be ~20 minutes. The owner prefers to use it just for 15. That's 25% energy wasted. Greenpeace, are you listening??

We keep biking along the coast (Bridgeway) and eventually cross 101 at some point in time. Then on to Mill Valley-Sausalito Path, and then left on to Sycamore Ave. Nothing particularly interesting between Sausalito and now.

We have to constantly consult our maps because the road is no longer just a straight road. We're afraid of taking a wrong turn and biking in the wrong direction. The constant checks make biking frustrating and makes us uneasy. V suggests investing in a phone holder for bikes. I provide a node of approval.

Our first reality check is at Molino Park where we wonder how far we want to go since the uphill slopes have been tiring. V's determination and unwillingness to give up inspires me. We turn on to Edgewood Avenue with renewed energy and determination.

1:30pm: We reach the tip top of Sequoia Valley Road, and the views are just breathtaking. S reaches shortly after. I've dismounted and crossed the road and am already taking photos.

The road ahead is ~700ft of pure downhill pleasure (which means uphill on our way back). S asks if we want to continue on and whether we'll be able to make it back in time. I make some quick approximate calculations and boldly suggest that we should be back by 5:30pm. Sounds like an estimate for delivery on a software project. Read on to find out what happens next.

V arrives and we unanimously decide to continue (against my better judgment, but hey, I did want to visit Muir Woods too :-p). The next ~7 minutes is just pure downhill orgasmic thrill.

Muir Woods Visitor Center is here. We decide to stay till 2:30pm. We have a Bartlett Pear each. V needs caffine in their blood, so we stop for a coffee break.

There's a tiny bridge over a stream and a lot of visitors!

And some #firstworldproblems:
2:45pm: And we're back on the road. This is an ~700ft ascent, and we do it fairly slowly.

3:15pm: The view at this time of the day on the tip top of Muir Woods Road is breathtaking.

V's bike:

3:30pm: There is a slight hiccup when we don't know which road we are on. We think that gmaps is showing us the right road, but the road sign seems to be wrong. We ask a tired runner, and he guides us. We later realize that the road name changes, and gmaps doesn't show where this transition happens. This can get confusing.

4:05pm: We stop at a place where we see a sea-plane and contemplate taking it :-p We also see a helicopter landing there. We all unanimously decide to take the ferry back from Sausalito to Pier39. S is the only one with power in their cell phone. The next ferry is at 5:35pm, and it will take us ~30 minutes to get there according to gmaps. We amble our way to the ferry terminal.

4:45pm: We;re almost at the ferry terminal when S spots R and family. We're pleasantly surprised by the meeting and exchange pleasantries and indulge in small talk.

5:00pm: We head to the ferry terminal and stand in line with the rest of the bikers. S determines the status of tickets and gets a Clipper Card. S tells V that tickets cost $4.25, but the clipper card needs $10.25 balance. I am unsure if I have that sort of cash, but I assume that I can refill my card. I ask S some more questions since I am confused about what is going on. S is searching for their Caltrain ticket. S and I need to communicate more. I have a hard time understanding things and S thinks I am smarter than I am.

5:20pm: The line moves forward, but the ferry is filling up fast. I see a ticket window and wonder why we aren't buying tickets. Everything seems bizarre to me. S then explains that we can clip on on the ferry and that $10.25 is the cost of the ferry and $4.25 is the minimum balance required. I really need to find a good way to communicate with S. We casually joke that we shouldn't be the first ones in line for the next ferry.

We are the first ones in line for the next ferry. Never has a STOP sign hurt so much.

5:45pm: We wait for the ferry to leave (since it isn't over till it's over), and start biking back. I am somewhat pleased that we aren't waiting for the next ferry, which is at 6:45pm.

Sausalito uphill seems easier than the one on Muir Woods Road. We are all pretty tired.

6:00pm: We've reached a point in the road where we need to decide whether we should turn right or go straight. I remember turning left after emerging from a tunnel on our way here, so I suggest turning right. I check the map for good measure, and it looks okay. The is my first blunder. We turn right into a tunnel that's longer than any other tunnel we've taken so far and find ourselves on Bunker Road. Phone doesn't have data, but the GPS is able to tell us where we are. We can't route back so we decide to retreat back into the tunnel we came from.

6:05pm: We;re back at the mouth of the tunnel, and we decide to route back to SF Caltrain. gmaps will suggest a path that doesn't exist. We don't know this, so we take the path. On the way down (which is a steep downhill), S suggests that they don't remember gaining so much altitude on the way up. We're halfway down. I completely agree with S, but don't have a better idea, so I don't stop. This is my second blunder. We find ourselves at the bottom of the Golden Gate Bridge. The view is majestic.

We crawl back up to the Golden Gate Bridge and realize that we have to cross since the west side of the pedestrian/bike path is now closed and we need to go over to the east side. My 5:30pm estimate has been blown to bits.

7:05pm: We take a short break to determine when we'll reach Cafe Chaat (dinner!!). I speculate another 20-25 minutes to reach Cafe Chaat.

7:55pm: We reach Cafe Chaat. Dinner is on the menu :-p

9:15pm: Take the last Caltrain back (it's Sunday).

Friday, January 31, 2014

Making soft chapatis that balloon

I've been making chapatis for a while now, and conventional wisdom says that getting the dough well knead is the key to soft chapatis since it forms the gluten strands in the dough and makes it tough. I very recently chanced upon the real method to make soft pliable dough that also results in chapatis that balloon even under sub-optimal rolling.

The key is to knead the dough in salty water. Take some salt (to taste) and mix it in some water (at room temperature). When the salt has completely dissolved in the water, use that water to knead your dough. You will find it much easier to knead your dough, and it will result in a soft pliable dough that is somewhat forgiving of mistakes (or chapati got stuck to the rolling pin and folded over itself) while rolling.

I additionally add some turmeric and red chilli powder to my dough for enhanced taste and colour! :)

Friday, January 10, 2014

Merging AVL Trees

Problem Statement: Given two AVL trees T1 and T2, where the largest key in T1 is less than the smallest key in T2, Join(T1, T2) returns an AVL tree containing the union of the elements in T1 and T2. Give an algorithm (in pseudocode) for Join() that runs in time O(log n), where n is the size of the resulting AVL tree. Justify the correctness and efficiency of your algorithm.

Problem statement and solution stolen from these assignment solutions.

Solution: Begin by computing the heights h1 of T1 and h2 of T2. This takes time O(h1 + h2). You simply traverse a path from the root, going to left child if the balance factor is -1, to the right child if it is positive, and to any of the children if the balance factor is 0, until you reach a leaf. Assume that h1 > h2; the other case is symmetric.

Next, DELETE the smallest element x from T2, leaving T'2 of height h. This takes O(h2) time.

Find a node v on the rightmost path from the root of T1, whose height is either h or h + 1, as follows:

v = root(T1)
h' = h1
while h' > h + 1 do
  if balance factor(v) = -1
  then h' = h' - 2
  else h' = h' - 1
  v = right-child(v)

This takes O(h1) time.

The reason we choose a node with height h or h + 1 is because if we are at a node of height h, and we move to its parent node, then the height of the new (parent) node might increase by 2 (to h + 1), since the sibling of node from which we moved up might have a height greater (by 1) than its sibling.

Let u denote the parent of v.

Form a new tree whose root contains the key x, whose left sub-tree is the sub-tree rooted at v and whose right sub-tree is T'2.

Note that this is a valid binary search tree, since all the keys in the sub-tree rooted at v are in T1 and, hence, smaller than x, and, by construction, x is smaller than or equal to all elements in T'2. The balance factor of the root of this new tree is h - h' which is either -1 or 0, so this new tree is a valid AVL tree. The height of this new tree is h' + 1, which is 1 bigger than v's height. Let the root of this new tree be the right child of u, in place of v. Again, since all keys in this new tree are at least as big as u, this results in a valid binary search tree. This part of the construction takes constant time.

Now, as in the INSERT algorithm, we go up the tree, starting at u, fixing balance factors and perhaps doing a rotation. This takes O(h1) time. Note that the correctness follows from the condition at u before this process is begun is a condition that can arise during the INSERT algorithm.

Since h1, h2 ∈ O(log n), the total time taken by this algorithm is in O(log n).

Saturday, December 07, 2013

Better algorithms v/s micro-optimization

As a kid, I participated in a game that involved bouncing a tennis ball on the ground using your hands. The winner was the one who was able to bounce the ball the most number of times in 60 second.

All the little ones (including me) went first (since the game was primarily meant to keep us busy). I was top scoring with a little over 70 bounces in 60 second. What I did to get there was try and go as fast as I possibly could without losing control of the ball, and focusing heavily on where the ball was at all times.

Then the grown-ups started and for a while no one was able to beat that score. Then one smart dude knelt down when the signal to start was given. Everyone else had already started bouncing there balls and were in to their second bounce, and this guy was taking his own time getting settled in his squatting position. When he was ready, he started bouncing the ball, and boy did he go fast! He had just out-smarted everyone else with a better algorithm for getting more bounces in the same time duration.

Better algorithms are like bicycles for the mind.

Before we had sorting algorithms that ran efficiently [O(n log n)], we had micro-optimizations applied to every known O(n2) sorting algorithm in an attempt to make it perform fewer comparisons, or exit early, and hence run faster. Fixing the algorithm, however, was the real game changer.

Saturday, October 26, 2013

Javascript as a language is really darn good

If you look at computer languages as tools to help you convert thought to code (ignoring other real-world practical considerations such as efficiency, developer availability, platform pervasiveness, library availability, etc...) then my opinion is that Javascript (in the form of node.js as we know it today) really stands out. Let me explain why I feel so.
  1. Javascript is a small and minimal language with few (redundant) constructs and can be taught and remembered easily. This is useful for someone who is trying to use javascript to write code as well as someone who is trying to read javascript code. When you are expressing your ideas, you want to know what tools you have and want to be able to fit them in your head. At the same time, when you (or someone else) (re)visit(s) your code, you want the reverse transfer of information (i.e. code to idea) to be quick and unambiguous and the reader shouldn't get confused trying to figure out the language syntax and semantics. To explain,

    • The fact that functions are first-class objects and that the lambda syntax isn't different (or otherwise special) compared to the standard function definition syntax helps.
    • As does the fact that objects/maps (hashes), arrays, etc... all have the same get/set syntax.

  2. There's very little fluff in the language. Most keywords don't feel like they're useless. The only ones I find excessive are 'new', 'prototype', and 'function'. Coffeescript solves this to some extent.
What this means is that it's very easy to get started with your first program once you have an idea of what it is that you want to express in code. Javascript lends itself well to elegant code.

Since there is no main() function in a node.js script, you don't need to encode all your executable code in a main() function. You won't believe how incredibly useful I find this even though I have programmed in C and am used to that style of programming. This also means that each file can have its own test() function that is run by just invoking:
$ node file_name.js.

Declaring arrays and objects (maps) in javascript is really easy, and anything that can be reasonable done in 1 line is done in one line. For example, declaring an array a that has 4 elements, 44, 31, 21, and 23 is:
var a = [ 44, 31, 21, 23 ];

Declaring an object o that maps key 'name' to 'blogger', key 'url' to '', and key 'age' to 5 is as simple as:
var o = {
  'name': 'blogger',
  'url': '',
  'age': 5

Notice how values in maps can be of different types. This is also true of elements in an array.

Converting a string (or any other type) to a string isn't rocket science either.
var sint = String(89);

To test my belief, I've started writing a toy regular expression parser and evaluation engine in javascript that will have some intentional holes (un-impelemented features) that you can fill up later so that you can get a feel for both how regular expressions work, as well as how javascript as a language handles.

Sunday, April 21, 2013

Inside the guts of Kadane's algorithm OR Understanding the Maximum Sum Subarray Problem

Kadane's algorithm is used to solve the 1 dimensional Maximum Sum Sub-array Problem in computer science.

Let's try to understand how it really works. If we are given the problem of finding the maximum sum sub-array of a given array, the first native approach we can try is the O(n2) algorithm of starting at every array index and computing the sum from that index to every index after it. This works, and gives us the correct answer, but we should ask ourselves if we can exploit certain properties that the problem might have to try and speed up the solution.

Let's try and dig deeper into an example.

Consider the following array & its corresponding cumulative sum subarray:

Cumulative Sum105310116359612-9-4-6-5

Some observations:
  1. A maximum sum sub-array can never have a negative number as one of the elements at the end-points, except of course if every element in the array is a negative number. If a maximum sum sub-array had a negative number on one of its end-points, we could remove that element and increase the value of the sum, thus getting a sub-array with a larger sum. Conversely, a maximum sum sub-array always starts and ends with a non-negative number, unless of course all the numbers in the array are negative.

  2. We can always clump all negative and non-negative numbers together since once we encounter a negative number, the sum always drops and once we encounter a non-negative number, the sum never drops.

  3. If the running sum of a sub-array array ever falls below zero, no solution will ever include the negative number that caused this sum to fall below zero since it over-powers the positive sum accumulated before it. Note: We only speak of 1 negative number because of the clumping point above.

  4. An extension of the point above implies that the new running sum that begins once a cumulative sum falls below zero always starts from the immediately following non-negative number.
Applying the rules above, we get the following recurrence:

MaxSum[i] is the Maximum Sum ending at index i.

MaxSum[i] = Array[i]                if i = 0
MaxSum[i] = MaxSum[i-1] + Array[i]  if MaxSum[i-1] + Array[i] >= 0
MaxSum[i] = 0                       if MaxSum[i-1] + Array[i] < 0

The re-written array (which now consists strictly of alternating negative and non-negative numbers) and the new cumulative sum sub-array are (the row "Cumulative Sum" below represents the MaxSum variable above):

Cumulative Sum10311396120534