Suggested Final Project Topics

Why they're worth studying:  In trying to convert from a black-box sorting algorithm to a priority

queue, it's often important to reason about the specific model of computation being used. Depending on

whether randomization is permitted or what restrictions there are on the sorts of bitwise operations can be

performed by the machine in constant time, the slowdown introduced in the construction can vary widely.

If you're interested in both seeing a cool construction and learning about models of computation in the

context of data structure design, this would be a great place to start.

Signature Sort

It's possible to sort in time o(n log n) if the items to sort are integers (for example, using radix sort). What

are the limits of our ability to sort integers? Using advanced techniques, signature sort can sort integers in

time O(n) – assuming that the machine word size is Ω((log n)

2+ε

).