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
Aside

Thinking about today: say we add a new set S to a $\sigma$-algebra , then the new $\sigma$-algebra with this set appended, has additional sets of the form $(A \cup S) \cap (B\cup (X/S))$

# 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.

# Limits & Indicator Functions

Proved a simple theorem today. Let ${A_n}$ be a sequence of subsets. Then, we have

$\limsup_{n->\infty } A_n = {w : \sum 1_{A}(w)=\infty }$
$\liminf_{n->\infty } A_n = {w : \sum 1_{A^{c}}(w)< \infty }$

Proofs use a tedious amount of notation manipulation, but thinking of it in terms of indicator functions is interesting.