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). (
geocities.com/Vienna/7079/src) (
geocities.com/Vienna/7079) (
geocities.com/Vienna)