Complexity of union-split-find problems
Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2009
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/45638 |
| _version_ | 1826213412924817408 |
|---|---|
| author | Lai, Katherine Jane |
| author2 | Erik D. Demaine. |
| author_facet | Erik D. Demaine. Lai, Katherine Jane |
| author_sort | Lai, Katherine Jane |
| collection | MIT |
| description | Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008. |
| first_indexed | 2024-09-23T15:48:41Z |
| format | Thesis |
| id | mit-1721.1/45638 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T15:48:41Z |
| publishDate | 2009 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/456382019-04-12T16:00:38Z Complexity of union-split-find problems Lai, Katherine Jane Erik D. Demaine. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Includes bibliographical references (p. 45-46). In this thesis, we investigate various interpretations of the Union-Split-Find problem, an extension of the classic Union-Find problem. In the Union-Split Find problem, we maintain disjoint sets of ordered elements subject to the operations of constructing singleton sets, merging two sets together, splitting a set by partitioning it around a specified value, and finding the set that contains a given element. The different interpretations of this problem arise from the different assumptions made regarding when sets can be merged and any special properties the sets may have. We define and analyze the Interval, Cyclic, Ordered, and General Union-Split-Find problems. Previous work implies optimal solutions to the Interval and Ordered Union-Split-Find problems and an (log n/ log log n) lower bound for the Cyclic Union-Split-Find problem in the cell-probe model. We present a new data structure that achieves a matching upper bound of (log n/ log log n) for Cyclic Union-Split Find in the word RAM model. For General Union-Split-Find, no o(n) bound is known. We present a data structure which has an [Omega](log2 n) amortized lower bound in the worst case that we conjecture has polylogarithmic amortized performance. This thesis is the product of joint work with Erik Demaine. by Katherine Jane Lai. M.Eng. 2009-06-25T20:37:07Z 2009-06-25T20:37:07Z 2008 2008 Thesis http://hdl.handle.net/1721.1/45638 367592391 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 46 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Lai, Katherine Jane Complexity of union-split-find problems |
| title | Complexity of union-split-find problems |
| title_full | Complexity of union-split-find problems |
| title_fullStr | Complexity of union-split-find problems |
| title_full_unstemmed | Complexity of union-split-find problems |
| title_short | Complexity of union-split-find problems |
| title_sort | complexity of union split find problems |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/45638 |
| work_keys_str_mv | AT laikatherinejane complexityofunionsplitfindproblems |