CMCT 2025

楊昌彪教授/ Prof.Chang-Biau Yang江振瑞教授/ Prof.Jehn-Ruey Jiang阮夙姿教授/ Prof.Justie Su- Tzu Juan

Keynote Speaker

楊昌彪教授/ Prof. Chang-Biau Yang
Distinguished Processor
National Sun Yat-sen University (國立中山大學)
cbyang@cse.nsysu.edu.tw

Short Bio

Chang-Biau Yang received his B.S. degree in Electronic Engineering from National Chiao Tung University, Hsinchu, Taiwan, in 1982, and his M.S. and Ph.D. degrees in Computer Science from National Tsing Hua University, Hsinchu, Taiwan, in 1984 and 1988, respectively. In 1990, he joined National Sun Yat-sen University as a faculty member. He has been the chairman of the Department of Computer Science and Engineering from 2001 to 2004, the deputy dean of Academic Affairs from 2007 to 2008, and the Director of Office of Library and Information Services from 2009 to 2011. From 2011 to 2023, he served as the Chairman of the Collegiate Programming Examination (CPE) Committee under the Association of Taiwan Computer Programming Contest (TCPC), and from 2019 to 2022, as the Chairman of the Association of Taiwan Computer Programming Contest (TCPC). Through his dedicated efforts in CPE, he significantly contributed to enhancing the programming skills of computer science students across Taiwanese universities. He got the Best Service Award from the IEEE Tainan Section in 2014, and the Outstanding Professor Award from the Chinese Institute of Engineers in 2019. He is currently a distinguished professor in the Department of Computer Science and Engineering at National Sun Yat-sen University in Taiwan since 2019. His research interests include computer algorithms, bioinformatics and parallel processing. Especially, he was devoted to the study of the sequence-related problems with wide applications on bioinformatics.

Title of the speech

The Longest Increasing Subsequence Problem and Its Variants

Abstract

In this talk, we explore a rich spectrum of sequence analysis problems that extend and generalize the classic Longest Increasing Subsequence (LIS) problem. Given a sequence of distinct numerical elements, the LIS problem aims to find a subsequence that is strictly increasing and has the maximum possible length. For example, given the sequence (3, 5, 2, 1, 9, 7), one LIS answer is (3, 5, 9), another is (3, 5, 7), both of which have a length of 3. This problem was first introduced by Schensted in 1961 and has since been widely studied. Recently, various extensions of the LIS problem have been proposed to better reflect real-world scenarios. For instance, in stock market analysis, the overall trend may be upward, but occasional small declines are common. To model such behavior, the longest almost increasing subsequence (LaIS) was proposed, which allows small decreases in an increasing sequence. In agriculture or climate analysis, crop yields or temperature may exhibit periodic trends. To capture this, variants such as LIS/LaIS with sliding windows have been introduced. In stock market analysis, one might also be interested in identifying multiple segments of rising and falling trends. Thus, the longest wave subsequence (LWS) has been proposed. For more detailed stock price behavior, one may consider both the lowest and highest prices in each day, treating each data point as an interval instead of a single value. This leads to the longest increasing interval subsequence problem (LIIS). We will introduce the following problems: Longest Increasing Subsequence (LIS) Longest Almost Increasing Subsequence (LaIS) Almost Order Preserving Matching Longest Wave Subsequence Longest Almost Wave Subsequence Longest Increasing Interval Subsequence LIS with Sliding Windows LaIS with Sliding Windows In addition, we will also explore two-sequence problems, where the goal is not only to satisfy the above structural constraints but also to ensure that corresponding elements from both sequences match. Examples include longest common increasing subsequence (LCIS), longest common wave subsequence (LCWS), and etc.