Archives


« Prev:

» Next:


Longest Increasing Subsequence

April 18th, 2006 at 9:16 am

I’ve posted a new code snippet to the programs and code page – an implementation of 3 different algorithms for solving the Longest Increasing Subsequence problem.

The implementations are:

  1. Using the the Longest Common Subsequence algorithm on a sequence with its sorted self: O(n^2)
  2. Using a dynamic programming algorithm described here . It is also O(n^2), but faster than (1) because of better constants and less generality.
  3. Using a greedy algorithm described here, that runs in O(n*log(n))

Related posts:

  1. regex gotcha in P::RD

This entry was posted on Tuesday, April 18th, 2006 at 09:16 and is filed under Math, Ruby. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

2 Responses to “Longest Increasing Subsequence”

  1. SimenNo Gravatar Says:
    April 18th, 2006 at 15:00

    Just a little pointer: the usual way to sort an Array randomly in Ruby is simply sorting by rand. Example:


    def shuffle_sequence!( a )
    a.sort! { rand }
    end

    sequence = (0..10).to_a
    shuffle_sequence! sequence # => randomized array

  2. elibenNo Gravatar Says:
    April 18th, 2006 at 16:05

    My implementation follows the Fisher Yates shuffle algorithm. See:
    http://pleac.sourceforge.net/pleac_ruby/arrays.html

    Also, yours is O(n*logn) which is an overkill for an obviously linear task.