Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01w6634593x
Title: A Dynamic Algorithm for the Longest Increasing Subsequence
Authors: Kufera, Gregory Andrew
Advisors: Tarjan, Robert
Contributors: Dvir, Zeev
Department: Mathematics
Class Year: 2015
Abstract: We present a dynamic algorithm for the longest monotonically increasing subsequence of a finite set N ⊂ R 2 with unique x -values and with |N | = n, supporting insertions and deletions in O(n). Queries for the minimal partition into strictly decreasing subsequences are supported in O(1), queries for the maximal length L of a monotonically increasing subsequence are supported in O(1), and queries for a longest monotonically increasing subsequence are supported output-sensitively in O(L).
Extent: 30 pages
URI: http://arks.princeton.edu/ark:/88435/dsp01w6634593x
Type of Material: Princeton University Senior Theses
Language: en_US
Appears in Collections:Mathematics, 1934-2023

Files in This Item:
File SizeFormat 
PUTheses2015-Kufera_Gregory_Andrew.pdf467.64 kBAdobe PDF    Request a copy


Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.