Show simple item record

dc.contributor.advisorLiu, Jiamou
dc.contributor.authorRoss, Kostya Kamalah
dc.date.accessioned2015-11-09T02:44:45Z
dc.date.available2015-11-09T02:44:45Z
dc.date.copyright2015
dc.date.created2015
dc.identifier.urihttp://hdl.handle.net/10292/9200
dc.description.abstractThe 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.language.isoenen_NZ
dc.publisherAuckland University of Technology
dc.subjectAlgorithmen_NZ
dc.subjectData structureen_NZ
dc.subjectComputer Scienceen_NZ
dc.subjectSortingen_NZ
dc.subjectDynamic algorithmsen_NZ
dc.subjectDynamic treeen_NZ
dc.titleDynamic algorithms for partially-sorted listsen_NZ
dc.typeThesis
thesis.degree.grantorAuckland University of Technology
thesis.degree.levelMasters Theses
thesis.degree.nameMaster of Philosophyen_NZ
thesis.degree.discipline
dc.rights.accessrightsOpenAccess
dc.date.updated2015-11-09T02:42:10Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record