Longest Common Subsequence - Revision history

Rice at 04:41, 11 March 2024

2024-03-11T04:41:15Z

← Older revision		Revision as of 04:41, 11 March 2024
Line 1:		Line 1:
	{{Infobox Algorithm\|runtime=O(mn)\|space=O(mn\|class=[[Dynamic Programming]]}}		{{Infobox Algorithm\|runtime=O(mn)\|space=O(mn)\|class=[[Dynamic Programming]]}}

	A sequence ''Z'' is a subsequence of another sequence ''X'' if all the elements in ''Z'' also appear in order in ''X''. Notably, the elements do ''not'' need to be consecutive.		A sequence ''Z'' is a subsequence of another sequence ''X'' if all the elements in ''Z'' also appear in order in ''X''. Notably, the elements do ''not'' need to be consecutive.

2024-03-11T04:40:56Z

← Older revision		Revision as of 04:40, 11 March 2024
Line 1:		Line 1:
	= ~~Problem description~~ =		{{Infobox Algorithm\|runtime=O(mn)\|space=O(mn\|class=[[Dynamic Programming]]}}

	A sequence ''Z'' is a subsequence of another sequence ''X'' if all the elements in ''Z'' also appear in order in ''X''. Notably, the elements do ''not'' need to be consecutive.		A sequence ''Z'' is a subsequence of another sequence ''X'' if all the elements in ''Z'' also appear in order in ''X''. Notably, the elements do ''not'' need to be consecutive.

2024-03-11T04:39:37Z

Subproblems

← Older revision		Revision as of 04:39, 11 March 2024
Line 46:		Line 46:
	0 & i = 0 or j = 0 \\		0 & i = 0 or j = 0 \\
	c[i-1, j-1] + 1 & x_i = y_i \\		c[i-1, j-1] + 1 & x_i = y_i \\
	max(c[i-1, j], c[i - 1~~, j~~]) & x_i \neq y_i		max(c[i-1, j], c[i, j - 1 ]) & x_i \neq y_i
	\end{cases}		\end{cases}
	</math>		</math>
Line 58:		Line 58:
	<math>X</math> and <math>Y_{n-1}</math>. We don't know which one it is,		<math>X</math> and <math>Y_{n-1}</math>. We don't know which one it is,
	so we simply compare them. Whichever is greater would be the LCS.		so we simply compare them. Whichever is greater would be the LCS.


	= Implementation =		= Implementation =

2024-03-05T03:37:41Z

← Older revision		Revision as of 03:37, 5 March 2024
Line 111:		Line 111:
	value is used for the <math>c</math> calculation. This halves the space		value is used for the <math>c</math> calculation. This halves the space
	requirement but doesn't change anything asymptotically.		requirement but doesn't change anything asymptotically.

			[[Category:Algorithms]]

2024-03-04T04:06:47Z

@@ Line 3: / Line 3: @@
 In the '''longest-common-subsequence problem (LCS)''', we wish to find a maximum-length common subsequence of ''X'' and ''Y''.
 = Approach: dynamic programming =
@@ Line 95: / Line 101: @@
 Printing shouldn't be that hard. You just trace back and record whenever
 they are the same value. I think.

2024-03-04T03:58:46Z

Property 1

← Older revision		Revision as of 03:58, 4 March 2024
Line 11:		Line 11:
	<math>X</math> and <math>Y</math>.		<math>X</math> and <math>Y</math>.

	~~====~~ Property 1 ~~====~~		'''Property 1'''

	If <math>x_m = y_n</math>, then <math>z_k = x_m = y_n</math> and		If <math>x_m = y_n</math>, then <math>z_k = x_m = y_n</math> and
	<math>Z_{k-1}</math> is an LCS of <math>X_{m-1}</math> and		<math>Z_{k-1}</math> is an LCS of <math>X_{m-1}</math> and
	<math>Y_{n-1}</math>.		<math>Y_{n-1}</math>.

	~~====~~ Property 2 ~~====~~		'''Property 2'''

	If <math>x_m \neq y_n</math> and <math>Z_k \neq x_m</math>, then		If <math>x_m \neq y_n</math> and <math>Z_k \neq x_m</math>, then
	<math>Z</math> is an LCS of <math>X_{m-1}</math> and		<math>Z</math> is an LCS of <math>X_{m-1}</math> and
	<math>Y</math>.		<math>Y</math>.

	~~====~~ Property 3 ~~====~~		'''Property 3'''

	If <math>x_m \neq y_n</math> and <math>Z_k \neq y_n</math>, then		If <math>x_m \neq y_n</math> and <math>Z_k \neq y_n</math>, then
	<math>Z</math> is an LCS of <math>X</math> and		<math>Z</math> is an LCS of <math>X</math> and
Line 31:		Line 34:
	<math>X_i</math> and <math>Y_j</math>. We have		<math>X_i</math> and <math>Y_j</math>. We have

	~~====~~ Property 4 ~~====~~		'''Property 4'''

	<math>		<math>

2024-03-04T03:55:56Z

← Older revision		Revision as of 03:55, 4 March 2024
Line 34:		Line 34:

	<math>		<math>
	c[i,j] = \begin{cases}		c[i,j] = \begin{cases}
	0 & i = 0 or j = 0 \\		0 & i = 0 or j = 0 \\
	c[i-1, j-1] + 1 & x_i = y_i \\		c[i-1, j-1] + 1 & x_i = y_i \\
Line 89:		Line 89:
	return (c, traceback)		return (c, traceback)
	</pre>		</pre>

			Printing shouldn't be that hard. You just trace back and record whenever
			they are the same value. I think.

2024-03-04T03:53:38Z

Property 4

2024-03-04T03:53:09Z

@@ Line 11: / Line 11: @@
 <math>X</math> and <math>Y</math>.
 If <math>x_m = y_n</math>, then <math>z_k = x_m = y_n</math> and
 <math>Z_{k-1}</math> is an LCS of <math>X_{m-1}</math> and
 <math>Y_{n-1}</math>.
 If <math>x_m \neq y_n</math> and <math>Z_k \neq x_m</math>, then
 <math>Z</math> is an LCS of <math>X_{m-1}</math> and
 <math>Y</math>.
 If <math>x_m \neq y_n</math> and <math>Z_k \neq y_n</math>, then
 <math>Z</math> is an LCS of <math>X</math> and
 <math>Y_{n-1}</math>.
-==== Subproblems ====
+=== Subproblems ===
 Let us have <math>c[i,j]</math> be the length of the LCS for
 <math>X_i</math> and <math>Y_j</math>. We have
 <math>
 c[i,j] = \begin{cases}
-& i = 0 and j = 0 \\
+& i = 0 or j = 0 \\
      c[i-1, j-1] + 1 & x_i = y_i \\
      max(c[i-1, j], c[i - 1, j]) & x_i \neq y_i
 \end{cases}
 </math>

2024-03-04T03:31:23Z

@@ Line 5: / Line 5: @@
 = Approach: dynamic programming =
 Consider <math>X = \langle x_1, x_2, \ldots, x_m \rangle</math> and
@@ Line 24: / Line 22: @@
 <math>Z</math> is an LCS of <math>X</math> and
 <math>Y_{n-1}</math>.