Dynamic algorithms for partially-sorted lists
| aut.embargo | No | en_NZ |
| aut.thirdpc.contains | No | en_NZ |
| aut.thirdpc.permission | No | en_NZ |
| aut.thirdpc.removed | No | en_NZ |
| dc.contributor.advisor | Liu, Jiamou | |
| dc.contributor.author | Ross, Kostya Kamalah | |
| dc.date.accessioned | 2015-11-09T02:44:45Z | |
| dc.date.available | 2015-11-09T02:44:45Z | |
| dc.date.copyright | 2015 | |
| dc.date.created | 2015 | |
| dc.date.issued | 2015 | |
| dc.date.updated | 2015-11-09T02:42:10Z | |
| dc.description.abstract | The dynamic partial sorting problem asks for an algorithm that maintains lists of numbers under the link, cut and change value operations, and queries the sorted sequence of the k least numbers in one of the lists. We examine naive solutions to the problem and demonstrate why they are not adequate. Then, we solve the problem in O(k log(n)) time for queries and O(log(n)) time for updates using the tournament tree data structure, where n is the number of elements in the lists. We then introduce a layered tournament tree data structure and solve the same problem in O(log '(n) k log(k)) time for queries and O(log2(n)) for updates, where ' is the golden ratio and log '(n) is the iterated logarithmic function with base '. We then perform experiments to test the performance of both structures, and discover that the tournament tree has better practical performance than the layered tournament tree. We discuss the probable causes of this. Lastly, we suggest further work that can be undertaken in this area. | en_NZ |
| dc.identifier.uri | https://hdl.handle.net/10292/9200 | |
| dc.language.iso | en | en_NZ |
| dc.publisher | Auckland University of Technology | |
| dc.rights.accessrights | OpenAccess | |
| dc.subject | Algorithm | en_NZ |
| dc.subject | Data structure | en_NZ |
| dc.subject | Computer Science | en_NZ |
| dc.subject | Sorting | en_NZ |
| dc.subject | Dynamic algorithms | en_NZ |
| dc.subject | Dynamic tree | en_NZ |
| dc.title | Dynamic algorithms for partially-sorted lists | en_NZ |
| dc.type | Thesis | |
| thesis.degree.discipline | ||
| thesis.degree.grantor | Auckland University of Technology | |
| thesis.degree.level | Masters Theses | |
| thesis.degree.name | Master of Philosophy | en_NZ |