An Arbitrary CRCW PRAM Algorithm for Sorting Integers Into a LinkedList and Chaining on a Trie
Date
2020Metadata
[+] Show full item recordAbstract
The research work comprises of two parts. Part one is using an Arbitrary CRCW PRAM algorithm for sorting integers into a linked list. There are various algorithms and techniques to sort the integers in LinkedList. Arbitrary CRCW PRAM model, being the weakest model is able to sort n integers in a LinkedList in “constant time” using nlogm processors and if we use nt processors, then it can be sorted in O(loglogm/logt) time by converting Arbitrary CRCW PRAM model to Priority CRCW PRAM model.
Part two is Chaining on a Trie. This research paper solves the problem of chaining on a Trie by providing more efficient complexity. This Algorithm takes “constant time” using n(logm+1) processors to chain the nodes on a Trie for n input integers on the Arbitrary CRCW PRAM model.
Table of Contents
Introduction -- Sort integers into a linked list -- Chaining on a Trie --Conclusion
Degree
M.S. (Master of Science)