Longest Strictly Increasing Sequence
Name: Anan Tongprasith
compile: cc prog2.c
input file: randomnumber
random number generator: random.c
limitation: 8750 input maximum please

Result:
10 inputs
	Bruteforce	0.8 ms
	Bottomup DP	0.0 ms
	Memoizing DP	0.0 ms
100 inputs
	Bruteforce	>15 mins
	Bottomup DP	1.2 ms (average)
	Memoizing DP	3.2 ms (average)
1000 inputs
	Bruteforce	>15 mins
	Bottomup DP	90.4 ms (average)
	Memoizing DP	350.2 ms (average)
8750 inputs
	Bruteforce	>15 mins
	Bottomup DP	15.5 seconds (average)
	Memoizing DP	43.4 seconds (average)
	 

Analysis

Brute Force
Brute force technique solves this problem by testing every possible sequence.
In the program, I use recursive call to generate all sequences. The function
call needs two buffer. One is the original input and another one is null. It
will transfer item from input to another buffer one at a time and make a 
recursive call to itself. The call will occur until all items in the input
sequence have been moved to the buffer. The function then start testing if
that sequence is longest and strictly increasing. The following figure shows
a sample input with 3 items:

                                          null  null
                                        /
                               a2  null 
                              /         \
                             /            null  a2
                 a1a2   null
                /            \            null  a1
               /              \         /
              /                a2  a1 
             /                          \
            /                             null  a1a2
a0a1a2  null
            \                             null  a0
             \                          /
              \                a2  a0
               \              /         \ null  a0a2
                \            /
                 a1a2   a0
                             \            null  a0a1
                              \         /
                               a2  a0a1
                                        \
                                          null  a0a1a2



Original         1st call      2nd call    3rd call


Dynamic Programming

There are two general ways (that I can think of) to solve this problem. 
The first is a straight forward technique that works like brute force: 
find all possible sequences. We make use of dynamic programming by match
items in pairs, trinary tuples and so on and build the next layer base on
the previous one.
For example, input is a0a1a2:


pairs         a0a1     a0a2     a1a2
                  \            /
                   \          /
                    \        /
3-tuples              a0a1a2

First, we test pairs and keep the results. Then we test 3-tuples using results
from pairs and so on.
However, this method use memory of

                      nCn + nC(n-1) + . . . + nC2

where nCk = n!/k!(n-k)!
The memory used is more than that of the second technique that I use (when n is
large enough.)

The second technique makes use of LCS algorithm in Cormen's book. I build 
another sequence from input by sorting it and get rid of redundant numbers 
(strictly increasing). Then I find the longest common subsequence between the 
two. For example, let input be 10,2,1,2; the problem becomes finding the LCS 
between 10,2,1,2 and 1,2,10. The memory used is O(n^2).