3
$\begingroup$

Using the answer provided here, I am now trying to find the longest increasing subset in two different sequences of numbers defined by location1 and location2.

enter image description here

For each location there are 16 readings. Each reading has its own position. I have sorted both lists by the Reading column.

Using a Scatter-Plot graph for each location, I am trying to find the longest increasing subset

Location 1

enter image description here

Location 2

enter image description here

Based on the two graphs; for location 1 the length of the longest increasing subset is 7 (7 positions) and for location 2 it is 5.

I highlighted the longest subsequence I found using the graph in blue and Itzik's subsequence in red.

The problem is that the book that I took these two lists from TSQL Querying (Itzik Ben-Gan) indicates that the longest increasing subset for Location2 has 6 points and using the graph, I only found 5 points that make up the longest subset.

Here is the longest subset according to the book

enter image description here

As you can see the readingNum column is out of order. My assumption was that to find the longest increasing subset, the position in the array had to increase as well as the value of that position.

Questions:

What is the longest increasing subsequence for both locations?

What is the formula, algorithm or method used?

Thanks

$\endgroup$
3
  • $\begingroup$ Usually we don't need our subsets to be an ordered list of things. $\endgroup$ – J126 Nov 20 '13 at 13:35
  • $\begingroup$ @TonyK - Itzik said he found it below in his answer. I'd still like to figure out how to do this step by step without using a graph. $\endgroup$ – Craig Efrein Nov 25 '13 at 10:10
  • $\begingroup$ I explained it in the other thread. (And I deleted my erroneous comment about a sub-sequence of length 6.) $\endgroup$ – TonyK Nov 25 '13 at 10:38
2
$\begingroup$

First, to give proper credit, Chapter 5: Algorithms and Complexity, was written by Steve Kass. Regarding your question about the Length of the Longest Increasing Subsequence; note that the algorithm described in the book does not attempt to find the longest increasing subsequence but rather its length. Don't be confused by the specific values that the solution stores in the table variable. For example, here's a 6-point subsequence of increasing values for location 2:

1 - 3.894 3 - 3.939 5 - 3.940 10 - 4.035 12 - 4.086 13 - 4.093

Again, the values stored in the table variable are different, but their count is 6--the length of the longest increasing subsequence.

Cheers, Itzik

$\endgroup$
1
  • $\begingroup$ Hello Itzik, thank you for the answer. I looked again at my graph and saw the line you indicated above. $\endgroup$ – Craig Efrein Nov 25 '13 at 8:53
0
$\begingroup$

Itzik just emailed me to let me know you'd asked this question. As he points out, the algorithm in T-SQL Querying doesn't reveal the subsequence itself. It only reveals its length. The intermediate values appearing during the calculation don't necessarily help you find the actual sequence. (The algorithmic complexity of finding an actual longest subsequence is greater than for finding the length.)

If you want to learn a bit more about the algorithm than what's in T-SQL Querying, see my 2002 article from SQL Server Magazine, available online here.

Relational algebra isn't central to this interesting mathematical problem (finding the length of the longest increasing subsequence), but it turned out to be useful in the real world, and a SQL solution turned out to be valuable.

$\endgroup$
1
  • $\begingroup$ thank you for writing back. I'm watching a video on how to solve these problems. I will definitely check out the link you've sent. I've been stuck on this subject for about a week now :) $\endgroup$ – Craig Efrein Nov 25 '13 at 15:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.