Longest Subsequence

The problem of finding the longest monotonically decreasing subsequence has an O(n log n) solution. My soln is O(n^2).

Absolutely fascinating that a sequence can be represented as a permutation graph, which means that the problem of finding the longest subsequence morphs into the problem of finding the largest clique!

Thus, essentially, the question which I was trying to solve – prove that a sequence from 1…101, will contain a increasing or decreasing sub-seq of length 10, morphs into a problem of proving that the ramsey number is 10.

Longest Subsequence Algorithm

An algorithm that has O(n^2) time complexity & O(n) space complexity to find the longest monotonically decreasing subsequence:

  1. Define new arrays. Length & pointer – length contains the length of the longest subsequence starting with a[i], and pointer points to the next element of that particular subsequence.
  2. (for i = lastElementIndex -1 ; i >= 0 ; i–)
  1. If (i is last element index)

i. Length[i] = 1, pointer[i] = null

  1. Else

i. Go through all elements from j = i to j = lastElement, appropriately setting pointer & length – i.e. if a[i] > a[j], then clearly no sequence possible. Else, just choose the one with the longest length.

Constructing the sequence from the length/pointer arrays is a straightforward task then.

2 good resources

[tag Resources]

An intuitive feeler to Algebraic Geometry: http://rigtriv.wordpress.com/ag-from-the-beginning/

A nice introduction to what Algebraic Topology actually does: http://blog.mikael.johanssons.org/archive/2006/01/introduction-to-algebraic-topology-and-related-topics-i/

This is something that I never really understood well until actually working out copious amounts of basic topology.

Longest Subsequence

Problem is to find the longest monotonically increasing/decreasing subsequence.

1st approach was to try out a recursive algorithm, starting with {a_n-1,a_n} in {a_1…a_n}, and build up the sequence from there.

However, this doesn’t always work. Take for example if a_n-1 = a high number forwhen we want a monotonically decreasing subsequence.

Then that number ends up blocking out other numbers that come later but could be part of the subsequence.

Take for example the sequens {8,6,12,4,2}. Here, the algorithm yields {12,4,2}, which is clearly suboptimal.