LIS - Revision history

Admin: /* Solution Algorithm */

2017-08-09T21:07:29Z

Solution Algorithm

← Older revision		Revision as of 21:07, 9 August 2017
Line 123:		Line 123:
	However, we also want to know the length of the longest sequence that <math>S_n</math> will extend		However, we also want to know the length of the longest sequence that <math>S_n</math> will extend

	Let ~~L_i~~ be length of the longest subsequence that ends with ~~S_i~~		Let <math>L_j</math> be length of the longest subsequence that ends with <math>S_j</math>

	Base case: <math>L_0 = 0</math>		Base case: <math>L_0 = 0</math>

	Now the quantity <math>~~L_i~~</math> is given by:		Now the quantity <math>L_j</math> is given by:

	<math>		<math>
	~~L_i~~ = \max_{0 < j ~~< i~~} L_j + 1 \qquad S_j ~~< S_i~~		L_j = \max_{0 < i < j} L_j + 1 \qquad S_i < S_j
	</math>		</math>

	~~(Skiena does not explain this very clearly, in particular~~ the ~~case~~ where i ~~= 1, so~~... ~~not sure what's going on there~~.)		This utilizes the fact that any subsequence ending at j must pick up where a prior sequence left off - at a prior position i < j. We also require that <math>S_i < S_j</math> because otherwise we aren't continuing an increasing subsequence.

			Then we just take the maximum of <math>L_i</math>, the longest subsequence ending at position i. Then add one to it, to extend the subsequence by one.

	=Flags=		=Flags=

Admin: /* Solution */

2017-08-09T20:56:36Z

Solution

← Older revision		Revision as of 20:56, 9 August 2017
Line 103:		Line 103:
	</pre>		</pre>

	===Solution===		===Solution Procedure===

	~~Three~~ dynamic programming steps:		To solve dynamic programming problems, apply these three steps:

	1. Formulate answer as recurrence relation/recursive algorithm		1. Formulate answer as recurrence relation/recursive algorithm
Line 112:		Line 112:

	3. Specify the order of evaluation for the recurrence so that partial results that are needed are always available		3. Specify the order of evaluation for the recurrence so that partial results that are needed are always available

			===Solution Algorithm===

	Longest increasing (non-contiguous) subsequence:		Longest increasing (non-contiguous) subsequence:

	Step 1 - formulate answer as recurrence relation		Step 1 - formulate answer as recurrence relation
	* We want to know the longest subsequence in the ''preceding'' numbers - if we are considering <math>S_n</math>, we want to know the longest increasing subsequence in <math>S_1, S_2, \dots, S_{n-1}</math>
	* However, we also want to know the length of the longest sequence that <math>S_n</math> will extend

	~~Step 2~~ - ~~To formulate the recurrence relation:~~		We want to know the longest subsequence in the ''preceding'' numbers - if we are considering <math>S_n</math>, we want to know the longest increasing subsequence in <math>S_1, S_2, \dots, S_{n-1}</math>
	* Let L_i be length of the longest subsequence ~~that ends with S_i~~
	* Base case: L_0 = 0
	* L_i given by:

	<~~Math~~>		However, we also want to know the length of the longest sequence that <math>S_n</math> will extend
	~~L_i = \max_{0 < j < i} L_j + 1 \qquad S_j < S_i~~
	</math>

	~~Skiena does not explain this very clearly, in particular~~ the ~~case where i = 1, so... not sure what's going on there.~~		Let L_i be length of the longest subsequence that ends with S_i

			Base case: <math>L_0 = 0</math>

			Now the quantity <math>L_i</math> is given by:

			<math>
			L_i = \max_{0 < j < i} L_j + 1 \qquad S_j < S_i
			</math>

			(Skiena does not explain this very clearly, in particular the case where i = 1, so... not sure what's going on there.)

	=Flags=		=Flags=

Admin: /* Dynamic Program */

2017-08-09T20:55:01Z

Dynamic Program

← Older revision		Revision as of 20:55, 9 August 2017
Line 131:		Line 131:





			=Flags=

			{{CombinatoricsFlag}}

			{{AlgorithmsFlag}}

			[[Category:Permutations]]
			[[Category:Combinatorics]]
			[[Category:Dynamic Programming]]

	=References=		=References=

	1. Romik, Dan. The Surprising Mathematics of Longest Increasing Subsequences. Manuscript, 20 August 2014. [https://www.math.ucdavis.edu/~romik/download-book.php]		1. Romik, Dan. The Surprising Mathematics of Longest Increasing Subsequences. Manuscript, 20 August 2014. [https://www.math.ucdavis.edu/~romik/download-book.php]

Admin: /* Patience Sorting */

2017-08-09T20:10:41Z

Patience Sorting

← Older revision		Revision as of 20:10, 9 August 2017
Line 62:		Line 62:

	Once you are given a permutation <math>\sigma</math>, how do you actually compute <math>L(\sigma)</math>?		Once you are given a permutation <math>\sigma</math>, how do you actually compute <math>L(\sigma)</math>?

			Consider the following algorithm: '''patience sorting'''

	Technique was invented by ASC Ross in 1960, named by Colin Mallows.		Technique was invented by ASC Ross in 1960, named by Colin Mallows.
Line 74:		Line 76:

	If there are no piles whose top number is greater than the current card, start a new pile.		If there are no piles whose top number is greater than the current card, start a new pile.

			When patience sorting is applied to a permutation <math>\sigma \in S_n</math>, the number of stacks at the end is equal to <math>L(\sigma)</math>.

	=Longest Increasing (Non-Contiguous) Subsequence=		=Longest Increasing (Non-Contiguous) Subsequence=

Admin: /* Bounds on Average Length */

2017-08-09T20:05:17Z

Bounds on Average Length

@@ Line 56: / Line 56: @@
 \lim_{n \rightarrow \infty} \sup \dfrac{l_n}{\sqrt{n}} \leq e
 </math>
 =Longest Increasing (Non-Contiguous) Subsequence=

Admin: /* Average Length */

2017-08-09T19:57:20Z

Average Length

← Older revision		Revision as of 19:57, 9 August 2017
Line 40:		Line 40:

	where c is -1.77108... and has a complicated definition given by a Painlevé differential equation of type 2.		where c is -1.77108... and has a complicated definition given by a Painlevé differential equation of type 2.

			===Bounds on Average Length===

			Bounds can be placed on the average value of <math>L(\sigma_n)</math>.

			Lower bounds are given by:

			<math>
			E( l_n ) \geq \sqrt{n}
			</math>

			An upper bound for <math>n \rightarrow \infty</math> can be given by

			<math>
			\lim_{n \rightarrow \infty} \sup \dfrac{l_n}{\sqrt{n}} \leq e
			</math>

	=Longest Increasing (Non-Contiguous) Subsequence=		=Longest Increasing (Non-Contiguous) Subsequence=

Admin: /* References */

2017-08-09T19:42:53Z

References

← Older revision		Revision as of 19:42, 9 August 2017
Line 96:		Line 96:
	=References=		=References=

	1. Romik, Dan. The Surprising Mathematics of Longest Increasing Subsequences. Manuscript, 20 August 2014.		1. Romik, Dan. The Surprising Mathematics of Longest Increasing Subsequences. Manuscript, 20 August 2014. [https://www.math.ucdavis.edu/~romik/download-book.php]

Admin: /* Solution */

2017-08-09T19:42:43Z

Solution

← Older revision		Revision as of 19:42, 9 August 2017
Line 91:		Line 91:

	Skiena does not explain this very clearly, in particular the case where i = 1, so... not sure what's going on there.		Skiena does not explain this very clearly, in particular the case where i = 1, so... not sure what's going on there.



			=References=

			1. Romik, Dan. The Surprising Mathematics of Longest Increasing Subsequences. Manuscript, 20 August 2014.

Admin: /* Average Length */

2017-08-09T19:41:30Z

Average Length

← Older revision		Revision as of 19:41, 9 August 2017
Line 39:		Line 39:
	</math>		</math>

	where ~~the constant~~ c is -1.77108... and has a complicated definition given by a Painlevé differential equation of type 2.		where c is -1.77108... and has a complicated definition given by a Painlevé differential equation of type 2.

	=Longest Increasing (Non-Contiguous) Subsequence=		=Longest Increasing (Non-Contiguous) Subsequence=

Admin: /* Average Length */

2017-08-09T19:41:10Z

Average Length

← Older revision		Revision as of 19:41, 9 August 2017
Line 39:		Line 39:
	</math>		</math>

	where the constant c is -1.77108... and has a complicated definition given by a Painlevé equation of type 2.		where the constant c is -1.77108... and has a complicated definition given by a Painlevé differential equation of type 2.

	=Longest Increasing (Non-Contiguous) Subsequence=		=Longest Increasing (Non-Contiguous) Subsequence=