Brain.Dump()

I've decided to add some accountability to my playing, put my newly acquired Zoom H4 to good use, and enable my friends and family to hear what I've been up to musically so I've started posting my live performances on my SkyDrive here (also linked to from the folder sharing module of this blog).  The plan is to post at least once a week or as often as I have new concert material.  If you're really care, are technically inclined, and want to be notified of any updates, then it might be easier just to subscribe to the RSS feed here.

 

 

As I said, this is for a few reasons.  The first is to track my growth as a musician by keeping an archive of past performances.  Growth in musicianship can be pretty slow going (at least, it is for me).  Sometimes the best way to hear any improvement is by listening to much older recordings and compare them with your current playing.  Plus, listening to your playing on a regular basis is a useful tool to identify bad habits and hone your sound.

 

In addition, I have a lot of friends and family that live out-of-town that have expressed interest in hearing what I've been doing with music lately.  So this is also a service to them so they can keep up with the latest.

 

Finally, it gives me an excuse to play with my H4.  The thing is bad-ass.  It even looks bad-ass:

 

 

And while it's a little too big to fit in your pocket for bootlegging concerts, it's an excellent Taser facsimile that works great at terrifying your friends.  Seriously though, if you want high-quality MP3 recordings on the fly, this is the device to use.  Bit of a learning curve, but well worth the money.

 

    

 

"These days, what with business and stuff, you gotta get your emails."  Wow.  I've since subscribed to their blog's RSS feed and the ha-ha's keep coming.

Did you get it?  No?  That's okay, here's the answer:

 

First let's note some properties of the array.  Obviously, from the definition, a cell's value is always greater than or equal to the cell to the left and the cell above.  Think about this for a minute...  Even with this restriction, a cell's value might also recur in a cell several columns to the left and several rows down - it all depends on the distribution of cell values (which you cannot make assumptions about).  You might have noticed that the minimum value will always be in the top-left corner and the maximum value will always be in the bottom-right corner.  This can easily be proved using mathematical induction starting with the top-left cell (at [0,0]).  Also, it may be interesting to note that any sub-array of any dimension (not necessarily square) also maintains the monotonically increasing row/column property.

 

Okay, let's talk algorithms!  Well obviously there's the brute-force approach.  That is: for each column, i, and for each row, j, test M[i,j] = K.  Of course, this solution hardly scales.  If our matrix is NxN, we've got a computational complexity of O(N²).  C'mon, we can do better!

 

One approach would be to try to limit the search area by exploiting the properties of the sorted array to eliminate cell candidates.  What if we made assumptions by only looking at the cells down the diagonal?  Let’s call the diagonal cell at the i^th column D_i.  If D_i=K, then we’re done; if D_i<K, then examine D_i+1; if D_i>K, then partition.  By partition, I mean that we exclude cells above and to the left of D_i (exclusive) and below and to the right of D_i (inclusive) from consideration.  This leaves us with 2 sub-arrays of cells each with a dimension of i x (N-i) for a total of 2*[i*(N-i)] cells that are still candidates.  Note that if we partition at M[0,0], then we can conclude that K doesn't exist in the array using the aforementioned fact that the top-left cell is he minimum value of the array.

 

A problem with this approach is that often times after a partition step, the remaining candidate cells are in non-square sub-arrays.  So without special logic, the algorithm cannot be purely recursive because it expects these sub-arrays to be square which they are often not and therefore we still don’t know how to optimally examine these.

 

Okay, so forget the "partition" algorithm for a moment - let's take another approach...  What if we started at the top-right corner (M[0,N-1])?  Now the algorithm is: if M[i,j] = K, then we're done as always; if M[i,j] < K, then we examine M[i,j+1] (move down since none of the cells above can be K); if M[i,j] > K, then we examine M[i-1,j] (move left since none of the cells to the right can be K).  This is called the "cursor" algorithm because our current cell of consideration moves like a cursor.  Since we can only move down and to the left, it's easy to prove that this algorithm will require 2N-1 steps in the worst case for a computational complexity of O(N) which is far better then our brute-force approach.  In addition, this technique has the nice property of being able to operate on non-square NxM arrays (which transforms the number of accesses required to N+M-1; a fact I'll use later).

 

Before I call it a day, what if we used a hybrid algorithm?  We could first use the partition approach to find the pivot at D_i and then apply the cursor algorithm on the two remaining clusters since it can operate on N x M arrays.  Well, it’s easy to see from the prior analysis that this doesn’t buy us anything: it’d require i accesses to find the D_i pivot and then 2 times i+(N-i)-1 accesses for the cursor algorithm.  That’s a grand total of 2N-1+i access which is obviously worse that a standalone cursor algorithm (2N-1).  So the cursor algorithm is indeed optimal.

 

As an exercise (and an opportunity to apply my Avalon WPF skills), I wrote a fun little demo program:

 

 

I've uploaded the VS2008 solution and the executable to my SkyDrive for your enjoyment/scrutiny.  Please note that the executable binary needs to be saved locally before it can be run due to .NET security protection.  Probably the most interesting part is the algorithm to generate a balanced, monotonically-increasing random number distribution for the 2D array custom UIElement that scales to any N.  Conceptually, it involves assigning each row cell a range of possible values random values and then analogously scaling these ranges by the vertical row position.  Playing with WPF animations was also fun.  It’s keyboard active, so you can just keep hitting the return key to step.  Enjoy!

 

Given an integer K and a NxN 2-dimensional array of integers with values that are monotonically increasing by both row and column (M[i+1,j] >= M[i,j] and M[i,j+1] >= M[i,j]), describe an algorithm that finds K in the array in as few accesses as possible.

 

 

For bonus points, list some other interesting properties of an array that is sorted this way.  Ready, set, GO!

It's one of those rare sunny days in Seattle so I decided to take a stroll around my neighborhood (I also wanted to play with my new digital camera I recently got for my birthday).  Having a reasonably-sized camera that easily fits in my pocket is a great asset.  I'm not much of a photographer, but I'm happy with this shot of Seattle's famous houseboats:

 

 

People are certainly feeling the pinch of high gas prices around here...  I snuck a shot of this local and her alternative means of transportation (yes, that's a surfboard):