Longest Common Almost Increasing Subsequence Algorithm

computing a longest common subsequence that n.w
1 / 13
Embed
Share

Explore the algorithm for computing the Longest Common Almost Increasing Subsequence (LCAIS) on sequences with no repeated elements. This study introduces a method for finding the LCAIS of permutations by allowing the addition of a value up to a specified constant to each element, resulting in an increasing subsequence. Dive into the process of solving the LCAIS problem and understand the complexities involved in this computational task.

  • Algorithm
  • Subsequence
  • Permutations
  • Sequences
  • Increasing
rayaanacharya
neathery_b Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. Computing a longest common subsequence that is almost increasing on sequences having no repeated elements Johra Muhammad Moosa, M. Sohel Rahman, Fatema Tuz Zohora Journal of Discrete Algorithms 20 (2013) 12 20 Speaker: Kuan-Chih Chen Date: 2018.01.02

  2. Abstract Given two permutations A and B of [1..n] and a fixed constant c, we introduce the notion of a longest common almost increasing subsequence (LCAIS) as a longest common subsequence that can be converted to an increasing subsequence by possibly adding a value, that is at most c, to each of the elements. We present an algorithm for computing LCAIS in O(?2) space, O(n(n + ?2)) time.

  3. Sequence/permutation A (1, 2, 3, 5, 13, 11, 9) Longest increasing subequence B (1, 2, 3, 5, 13) Longest almost increasing subequence (c = 3) ? 1 ?? ? yi> ????=1 C (1, 2, 3, 5, 13, 11)

  4. Solving a longest common almost increasing subsequence(LCAIS) problem Given two permutations A (20, 7, 15, 1, 14, 3, 6, 13, 11, 18, 10, 9), m = 12 B (7, 12, 15, 14, 21, 13, 6, 11, 10, 9), n = 10 and a constant c = 3, find the LCAIS of A & B

  5. 1 2 3 4 5 6 7 8 9 10 A(i) B(j) 7 12 15 14 21 13 6 11 10 9 1 20 2 7 3 15 4 1 5 14 6 3 7 6 8 13 9 11 10 18 11 10 12 9

  6. 1 2 3 4 5 6 7 8 9 10 ??[?] A(i) B(j) k j 1 7 12 15 14 21 13 6 11 10 9 1 20 1 2 3 4 5 6 7 8 9 10 2 7 * 7 7 7 7 7 7 7 7 7 7 CAIS: 7 3 15 2 4 1 3 5 14 4 6 3 5 7 6 6 8 13 7 9 11 8 10 18 9 11 10 10 12 9

  7. ???(15) = (7) 1 2 3 4 5 6 7 8 9 10 ??[?] ??[?] A(i) B(j) k j 1 1 7 12 15 14 21 13 6 11 10 9 20 k j 1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 2 7 * 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 3 15 * 15 2 2 15 15 15 15 15 15 15 4 1 CAIS: 7, 15 3 3 5 14 4 4 6 3 5 5 7 6 6 6 8 13 7 7 9 11 8 8 10 18 9 9 11 10 10 10 12 9

  8. ???(15) = (7) 1 2 3 4 5 6 7 8 9 10 ??[?] ??[?] A(i) B(j) k j 1 1 ???(14) = (7,15) 7 12 15 14 21 13 6 11 10 9 20 k j 1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 2 7 * 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 3 15 * 15 15 2 2 15 15 15 15 15 15 15 15 15 15 15 15 15 15 4 1 3 3 14 14 14 14 14 14 14 5 14 * 4 4 CAIS: 7, 15, 14 6 3 5 5 7 6 6 6 8 13 7 7 9 11 8 8 10 18 9 9 11 10 10 10 12 9

  9. ???(15) = (7) ???(6) = (7) 1 2 3 4 5 6 7 8 9 10 A(i) B(j) k j 1 1 ??[?] ??[?] ???(14) = (7,15) 7 12 15 14 21 13 6 11 10 9 20 k j 1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 2 7 * 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 3 15 * 15 15 2 2 15 15 15 15 15 15 15 6 15 6 15 6 15 6 CAIS: 7, 15, 14 14 14 4 1 3 3 14 14 14 14 14 14 14 14 14 14 14 14 5 14 * 4 4 CAIS: 7, 6 6 3 5 5 7 6 * 6 6 8 13 7 7 9 11 8 8 10 18 9 9 11 10 10 10 12 9

  10. 1 2 3 4 5 6 7 8 9 10 A(i) B(j) 7 12 15 14 21 13 6 11 10 9 1 20 2 7 * 3 15 * CAIS: 7, 15, 14 4 1 5 14 * CAIS: 7, 6 6 3 7 6 * 8 13 9 11 10 18 11 10 12 9

  11. ???(15) = (7) ???(6) = (7) 1 2 3 4 5 6 7 8 9 10 ??[?] A(i) B(j) k j 1 ???(14) = (7,15) ???(13) = (7,15,14) 7 12 15 14 21 13 6 11 10 9 1 20 1 2 3 4 5 6 7 8 9 10 2 7 * 7 7 7 7 7 7 7 7 7 7 3 15 * 15 2 15 15 15 6 6 6 6 CAIS: 7, 15, 14 14 4 1 3 14 14 14 14 14 14 5 14 * 4 13 13 13 13 13 CAIS: 7, 6 6 3 5 7 6 * 6 8 13 * 7 9 11 CAIS: 7, 15, 14, 13 8 10 18 9 11 10 10 12 9

  12. ???(6) = (7) ???(11) = (7,6) ???(15) = (7) 1 ???(14) = (7,15) 2 3 4 5 6 7 8 9 10 ??[?] A(i) B(j) k j 1 ???(13) = (7,15,14) 7 12 15 14 21 13 6 11 10 9 1 20 1 2 3 4 5 6 7 8 9 10 2 7 * 7 7 7 7 7 7 7 7 7 7 3 15 * 15 2 15 15 15 6 6 6 6 4 1 3 14 14 14 14 11 11 11 5 14 * 4 13 13 13 13 13 CAIS: 7, 6 6 3 CAIS: 7, 6, 11 5 7 6 * 6 8 13 * 7 9 11 * CAIS: 7, 15, 14, 13 8 10 18 9 11 10 10 12 9

  13. ???(10) = (7,6,11) ???(11) = (7,6) 1 2 3 4 5 6 7 8 9 10 ??[?] A(i) B(j) k j 1 ???(9) = (7,6,11,10) 7 12 15 14 21 13 6 11 10 9 1 20 1 2 3 4 5 6 7 8 9 10 2 7 * 7 7 7 7 7 7 7 7 7 7 3 15 * 15 2 15 15 15 6 6 6 6 4 1 3 14 14 14 14 11 11 11 5 14 * 4 13 13 13 10 10 6 3 CAIS: 7, 6, 11 5 9 7 6 * 6 8 13 * 7 9 11 * CAIS: 7, 15, 14, 13 8 10 18 9 11 10 * 10 CAIS: 7, 6, 11, 10, 9 12 9 *

Related


No related presentations.

More Related Content