Change search
ReferencesLink to record
Permanent link

Direct link
Evaluation of different solutions to the left-right-neighbour and priority queue problems
1998 (English)Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

In this thesis we study two problems defined on elements drawn from a bounded universe of size M. The problems are: the problem of maintaining a dynamic set of elments, in order to answer queries about the left and right neighbour of an arbitrary element from the universe and the related Priority Queue problem. Several different solutions, such as Split-Tagged- Tree, vEB Stratifed Tree and heap, are compared, implemented and tested. We also introduce a simplification of the Split-Tagged-Tree and use it to solve the Priority Queue problem. In some of our solutions we use a model of computation called RAMBO which extends the RAM model with a special memory block. Under this model the simplifed Split-Tagged-Tree uses 3 M + O (lg M ) bits and permits constant time operations on the Priority Queue. In comparison, under the same model the general Split-Tagged-Tree uses 5 M + O (lg M ) bits and per- mits queries of the Left-Right-Neighbour problem to be answered in constant time. The test results show that we can solve the Priority Queue problem efficiently using the simplifed Split-Tagged-Tree and a special hardware im- plementing the RAMBO.

Place, publisher, year, edition, pages
Keyword [en]
Technology, Computer Science, Priority Queue problem, Split-Tagged-Tree
Keyword [sv]
URN: urn:nbn:se:ltu:diva-53558ISRN: LTU-EX--98/173--SELocal ID: a91d0fda-e0e4-4284-ab50-262ccb7c1a4eOAI: diva2:1026933
Subject / course
Student thesis, at least 30 credits
Educational program
Civil Engineering programmes 1997-2000, master's level
Validerat; 20101217 (root)Available from: 2016-10-04 Created: 2016-10-04Bibliographically approved

Open Access in DiVA

No full text

Search outside of DiVA

GoogleGoogle Scholar

Total: 1 hits
ReferencesLink to record
Permanent link

Direct link