Aside

2 problems I’m working on right now:

1. Evaluate $latex\sum_{k=1}^{k=n}(n-k)2^{k-1}$ by somehow interpreting the term as a sum of disjoint sets.

2. Longest possible monotonic subsequence. Fun thinking about this in terms of directed graphs.

Advertisements

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.