Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 4 of 4 for “"comparison-based algorithm"”.
-
Efficient Algorithms for Sorting on GPUs
… vital problem. In particular, we develop a novel algorithm for sorting on Graphics Processing Units (GPUs). GPUs are multicore architectures that offer the potential of affordable parallelism. We present an efficient sorting algorithm called Fine Sample Sort (FSS). Our FSS algorithm extends and …
-
Self-stabilizing k-clustering in mobile ad hoc networks
… silent self-stabilizing asynchronous distributed algorithms are given for constructing a k-clustering of a connected network of processes. These are the first self-stabilizing solutions to this problem. One algorithm, FLOOD, takes O( k) time and uses O(k log n) space per process, while the second …
-
Adaptive Comparison-Based Algorithms for Evaluating Set Queries
… sets as operands. We explore properties of comparison-based algorithms for the problem. A <i>proof of a set expression</i> is the set of comparisons that a comparison-based algorithm performs before it can determine the result of the expression. We discuss the properties of the proofs of set …
-
Time-Space Tradeoffs and Query Complexity in Statistics, Coding Theory, and Quantum Computing
… studies the computational resources needed by algorithms to correctly solve computational problems. In this thesis, we derive lower bounds on the computational complexity of different problems for different classes of algorithms. The computational resources we consider are the running time, the …