Almost Wave Subsequence Problem Overview

the longest almost wave subsequence problem n.w
1 / 19
Embed
Share

Explore the intricacies of the Longest Almost Wave Subsequence (LaWS) problem, combining the concepts of LaIS and LWS problems. Dive into the LaWSt and LaWSr subproblems, discover their complexities, and witness the application of algorithms in finding the optimal subsequences. Join the journey through sequences, trends, and alternating patterns to unlock the mysteries of wave subsequence optimization.

  • Subsequence Problem
  • Algorithm Complexity
  • Sequence Analysis
  • Optimization
  • Trend Matching
rayaanacharya
kmonc 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. The Longest Almost Wave Subsequence Problem Shin-Cheng Lin, Kuo-Si Huang and Chang-Biau Yang CMCT2023 Presenter: Wen-Yu Chang Date: Nov. 14, 2023

  2. Abstract(1/2) In this paper, we first define a new longest almost wave subsequence (LaWS) problem by combining the longest almost increasing subsequence (LaIS) problem (Elmasry, 2010) and the longest wave subsequence (LWS) problem (Chen and Yang, 2020). The three problems are all generalized variants of the longest increasing subsequence (LIS) problem. 2

  3. Abstract(2/2) The LaWS problem has two subproblems, LaWSt and LaWSr. Given a sequence A, a tolerance constant c, a trend sequence T and a constant r, the LaWSt problem aims to find the longest subsequence of A that matches the prefix of the trend sequence T. The LaWSr problem aims to find the longest subsequence of A within r segments, alternating between almost increasing and almost decreasing. The time and space complexities of our LaWSt algorithm are O(?log?) and O(? + ?), respectively, where ? denotes the length of the given sequence, and l denotes the answer length. Our algorithm solves the LaWSr problem in O(??log?) time and O(? + ??) space. 3

  4. Longest Almost Wave Subsequence with Trend (LaWSt) ? = 2,13,1,5,4,3,6,14,15,14,16,15,17 ? = 0,1,1,1,0,0,0,0,1,1,1,1,1 ? = 3 The LaWSt sequence is 2,1,5,14,15,14,16,15,17 4

  5. T 0 1 1 1 0 0 0 0 1 LaWSt l(length) 1 2 3 4 5 6 7 8 9 A 2 2 ?1 ?2 ?3 ?4 ?5 ?6 ?7 ?8 ?9 ?10 ?11 ?12 ?13 ? = 3 13 1 5 4 3 6 14 15 14 16 15 17 The current LaWSt: 2 5

  6. T 0 1 1 1 0 0 0 0 1 LaWSt l(length) 1 2 3 4 5 6 7 8 9 A 2 2 ?1 ?2 ?3 ?4 ?5 ?6 ?7 ?8 ?9 ?10 ?11 ?12 ?13 ? = 3 13 2 13 1 5 4 3 6 14 15 14 16 15 17 The current LaWSt: 2,13 6

  7. T 0 1 1 1 0 0 0 0 1 LaWSt l(length) 1 2 3 4 5 6 7 8 9 A 2 2 ?1 ?2 ?3 ?4 ?5 ?6 ?7 ?8 ?9 ?10 ?11 ?12 ?13 ? = 3 13 ? = 10 > 1 13 2 13 1 1 2 5 2 ? = 1 < 1 4 3 6 14 15 14 16 15 17 The current LaWSt: 2,1 7

  8. T 0 1 1 1 0 0 0 0 1 LaWSt l(length) 1 2 3 4 5 6 7 8 9 A 2 2 ?1 ?2 ?3 ?4 ?5 ?6 ?7 ?8 ?9 ?10 ?11 ?12 ?13 ? = 3 13 2 13 1 1 2 5 1 2 5 4 3 6 14 15 14 16 15 17 The current LaWSt: 2,1,5 8

  9. T 0 1 1 1 0 0 0 0 1 LaWSt l(length) 1 2 3 4 5 6 7 8 9 A 2 2 ?1 ?2 ?3 ?4 ?5 ?6 ?7 ?8 ?9 ?10 ?11 ?12 ?13 ? = 3 13 2 13 1 1 2 5 ? = 2 < 4 5 1 2 5 4 1 2 4 4 3 6 14 15 14 16 15 17 The current LaWSt: 2,1,5,4 9

  10. T 0 1 1 1 0 0 0 0 1 LaWSt l(length) 1 2 3 4 5 6 7 8 9 A 2 2 ?1 ?2 ?3 ?4 ?5 ?6 ?7 ?8 ?9 ?10 ?11 ?12 ?13 ? = 3 13 2 13 1 1 2 3 + ? = 6 = 6 5 1 2 5 4 + ? = 7 > 6 4 1 2 4 4 3 1 2 4 4 3 6 1 2 4 6 4 14 15 14 16 15 17 The current LaWSt: 2,1,5,4,6 10

  11. T 0 1 1 1 0 0 0 0 1 LaWSt l(length) 1 2 3 4 5 6 7 8 9 A 2 2 ?1 ?2 ?3 ?4 ?5 ?6 ?7 ?8 ?9 ?10 ?11 ?12 ?13 ? = 3 13 2 13 1 1 2 5 1 2 5 4 1 2 4 4 3 1 2 4 4 3 6 1 2 4 6 4 14 1 2 4 14 4 15 1 2 4 15 14 14 1 2 4 15 14 14 16 1 2 4 16 15 14 14 15 1 2 4 16 15 15 14 15 17 1 2 4 16 15 15 14 15 17 The LaWSt: 2,1,5,14,15,14,16,15,17 11

  12. Time and Space Complexity Implemented by a more efficient data structure (AVL tree or red-black tree) Time complexity: O ?log? Space complexity: O ? + ? 12

  13. Longest Almost Wave Subsequence with r Segments (LaWSr) ? = 9,12,11,17,10,12,9,5,11,16 ? = 3 ? = 3 The LaWSr sequence is 9,12,11,17,10,12,9,5,11,16 13

  14. LaWSr ? = 3 length 1 9 9 9 2 3 4 5 6 7 8 9 10 ?1 ?2 ?3 ?1= 9 9 14

  15. LaWSr ? = 3 length 1 9 9 9 2 3 4 5 6 7 8 9 10 12 12 12 ?1 ?2 ?3 ?2= 12 9,12 ?2: 9 + ? = 12 = 12 inheritance from Q1 15

  16. LaWSr ? = 3 length 1 9 2 11 12 12 - 3 4 5 6 7 8 9 10 12 11 11 ?1 ?2 ?3= 11 9 ?3 9,12,11 ?3: inheritance from Q2 16

  17. LaWSr ? = 3 length 1 9 2 11 12 - 3 4 5 6 7 8 9 10 12 11 11 17 17 17 ?1 ?2 ?3 ?4= 17 9 9,12,11,17 ?2: inheritance from Q1 17

  18. LaWSr ? = 3 length 1 5 2 9 3 4 11 17 5 6 7 8 9 10 10 12 12 - 12 11 - 16 10 16 ?1 9 ?10= 16 ?2 5 11 16 ?3 9, 12, 11, 17, 10, 12, 9, 5, 11, 16 18

  19. Time and Space Complexity Implemented by a more efficient data structure (enhanced AVL-tree) Time complexity: O ??log? Space complexity: O ? + ?? 19

Related


No related presentations.

More Related Content