Optimal Parallel Algorithm for Longest Increasing Subsequence Problem
"Explore a divide and conquer approach for efficiently computing the longest increasing subsequence (LIS) problem with optimal time complexity. Learn how to achieve a work-optimal parallel algorithm for LIS. Presented by Muhammad Rashed Alam and M. Sohel Rahman in Information Processing Letters (2013)."
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.
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
A divide and conquer approach and a work-optimal parallel algorithm for the LIS problem Muhammad Rashed Alam, M. Sohel Rahman Information Processing Letters, 2013, vol. 113, no. 6, pp. 470-476, Presenter: Yu-Lin Chen Date: Mar. 18, 2025
Abstract In this paper, we present a divide and conquer approach to solve the problem of computing a longest increasing subsequence. Our approach runs in O(n log n) time and hence is optimal in the comparison model. In the sequel, we show how we can achieve a workoptimal parallel algorithm using our divide and conquer approach. 2
Divide S = (8, 9, 2, 6, 3, 7, 10, 4, 1, 5) two-tuple (value, pos) S1 = (2, 3), (3, 5), (4, 8), (1, 9), (5, 10) S2 = (8, 1), (9, 2), (6, 4), (7, 6), (10, 7) Divide S in two subsequences S1 and S2 Delete from S the elements that are greater than (less than or equal to) n/2 to get S1 (S2) 3
Conquer After computing the LIS of S1 and S2 recursively, we will have B1 = (1, 9), (3, 5), (4, 8), (5, 10) B2 = (6, 4), (7, 6), (10, 7) P = (0, 1, 0, 0, 3, 4, 6, 5, 0, 8) Perform the LIS computation for the two subsequences S1 and S2 recursively 4
Combine Case 1: x <= n/2 (i.e., x is in S1): If the parent of x, i.e., y = S[P[i]] is currently present in B, we execute Insert(x, y). If y = 0 then we execute Insert(x, 0) If y = 0 then y will always be present in B 5
Combine Case 2: x > n/2 (i.e., x is in S2): If the parent of x, i.e., y = S[P[i]] is present in B, then we execute Insert(x, y). If, however, y = 0 or y is not currently present in B, then we execute Insert(x, z) where z is the largest element of S1 currently in B. Additionally, we update parent of x, P[i] by setting it to the index of z. 6
Example S = (8, 9, 2, 6, 3, 7, 10, 4, 1, 5) P = (0, 1, 0, 0, 3, 4, 6, 5, 0, 8) S1 = (2, 3), (3, 5), (4, 8), (1, 9), (5, 10) S2 = (8, 1), (9, 2), (6, 4), (7, 6), (10, 7) B = {(8, 1)} 7
Example S = (8, 9, 2, 6, 3, 7, 10, 4, 1, 5) P = (0, 1, 0, 0, 3, 4, 6, 5, 0, 8) S1 = (2, 3), (3, 5), (4, 8), (1, 9), (5, 10) S2 = (9, 2), (6, 4), (7, 6), (10, 7) S[P[2]] = S[1] = 8 B = {(8, 1), (9, 2)} 8
Example S = (8, 9, 2, 6, 3, 7, 10, 4, 1, 5) P = (0, 1, 0, 0, 3, 4, 6, 5, 0, 8) S1 = (2, 3), (3, 5), (4, 8), (1, 9), (5, 10) S2 = (6, 4), (7, 6), (10, 7) B = {(2, 3), (9, 2)} 9
Example S = (8, 9, 2, 6, 3, 7, 10, 4, 1, 5) P = (0, 1, 0, 0, 3, 4, 6, 5, 0, 8) S1 = (3, 5), (4, 8), (1, 9), (5, 10) S2 = (6, 4), (7, 6), (10, 7) B = {(2, 3), (6, 4)} 10
Example S = (8, 9, 2, 6, 3, 7, 10, 4, 1, 5) P = (0, 1, 0, 3, 3, 4, 6, 5, 0, 8) S1 = (3, 5), (4, 8), (1, 9), (5, 10) S2 = (7, 6), (10, 7) S[P[5]] = S[3] = 2 B = {(2, 3), (3, 5)} 11
Example S = (8, 9, 2, 6, 3, 7, 10, 4, 1, 5) P = (0, 1, 0, 0, 3, 4, 6, 5, 0, 8) S1 = (4, 8), (1, 9), (5, 10) S2 = (7, 6), (10, 7) B = {(2, 3), (3, 5), (7, 6)} 12
Example S = (8, 9, 2, 6, 3, 7, 10, 4, 1, 5) P = (0, 1, 0, 0, 3, 5, 6, 5, 0, 8) S1 = (4, 8), (1, 9), (5, 10) S2 = (10, 7) B = {(2, 3), (3, 5), (7, 6), (10, 7)} 13
Example S = (8, 9, 2, 6, 3, 7, 10, 4, 1, 5) P = (0, 1, 0, 0, 3, 5, 6, 5, 0, 8) S1 = (4, 8), (1, 9), (5, 10) S2 = {} S[P[8]] = S[5] = 3 B = {(2, 3), (3, 5), (4, 8), (10, 7)} 14
Example S = (8, 9, 2, 6, 3, 7, 10, 4, 1, 5) P = (0, 1, 0, 0, 3, 5, 6, 5, 0, 8) S1 = (1, 9), (5, 10) S2 = {} S[P[9]] = S[0] = NULL B = {(1, 9), (3, 5), (4, 8), (10, 7)} 15
Example S = (8, 9, 2, 6, 3, 7, 10, 4, 1, 5) P = (0, 1, 0, 0, 3, 5, 6, 5, 0, 8) S1 = (5, 10) S2 = {} S[P[10]] = S[8] = 4 B = {(2, 3), (3, 5), (4, 8), (5, 10)} 16
