Skip to main content

Posts

Showing posts from May, 2012

Alogorithm: Finding Longest Increasing Subsequence using Patience Sort in C#

Finding the Longest Increasing Sequence is an interesting problem and there are multiple solutions available with varying time complexity. The solution that i plan to share today is the uses of Patience Sort  to find such a sequence. The solution finds a particular longest increasing sub-sequence as the original sequence may contain more than one such sequence.

In 1999 The Bulletin of the American Mathematical Society published a paper by David Aldous and Persi Diaconis entitled: “Longest Increasing Subsequences: From Patience Sorting to the Baik-Deift-Johansson Theorem”.

I have implemented this solution in C# and derived it from this excellent article which provides a Python implementation for the same.

This is how patience sort works

Take a deck of cards labeled 1, 2, 3, … , n. The deck is shuffled, cards are turned up one at a time and dealt into piles on the table, according to the ruleA low card may be placed on a higher card (e.g. 2 may be placed on 7), or may be put into a …

Caching Images downloaded from web on Windows Phone Isolated storage

I was helping on a Windows Phone application where the requirement was to cache the images the phone downloads on the isolated storage for offline viewing.
I wanted a solution which was simple and as transparent as possible. While researching I found  someone wrote a Silverlight converter for loading images from isolated storage. Taking that as a base I created a converted which can
Load image from web (http + https), and persist it to isolated storage.In case of network connectivity issues can load the same image from isolated storage. It does that by mapping the http url to a isolated storage location.In case the network is down and the image is neither there in cache, loads a default image, passed as parameter to converter.Here is the gist for the implementation.


To use the converter
Import the name space.Declare the converter as resource.Set the Image Source Property to use this converter like this