# 2012 Honors Theses

## computer science

Author: Tair Akhmejanov |
||

Title: Computational Complexity and Randomness |
||

Advisor: Howard Straubing |
||

The limit of efficient computation is an interesting topic both from the perspective of practical knowledge and pure mathematics. We examine the effect of randomness on efficiency. Does a machine with access to random coin flips provide a means for more efficient algorithms? Empirically, there are a number of problems that are solvable by randomized algorithms for which no equally efficient classical algorithm is known. Despite this observation, there are theoretical results in computational complexity theory suggesting that randomness can always be eliminated without much loss in efficiency. We explore both options by implementing a randomized algorithm, but also working through the theory of derandomization. We then explore methods for decreasing the amount of randomness needed in our algorithms by using expander graphs as “pseudorandom objects.” The ideas developed about expander graphs are then exploited to implement an algorithm solving graph connectivity in logarithmic space. |
||

Author: John Bacon |
||

Title: Relative Distributed Inertial Navigation Using Android Technology |
||

Advisor: Ed Sciore |
||

Sensors have been a part of computer science and human computer interaction for many years, with applications ranging from spaceship navigation systems, robotics, to gaming. In gaming specifically, the use of the accelerometer has been popularized by the Nintendo Wii, which uses an accelerometer and a gyroscope to allow the Wii controller to represent 3D objects in 3D environments, such as a golf club, tennis racket, or a sword. This thesis project investigates the ability to use Android technology in tandem with sensors on Android devices to be able to represent players themselves as objects in a 3D environment. By combining sensor principles with OpenGL ES, this thesis attempts to represent players themselves as objects in a 3D environment by implementing relative distributed inertial navigation. Inertial navigation investigates using the accelerometer, gyroscope, and various filtering techniques. This navigation is further specified to be relative and distributed, as the environment is an arbitrary 3D environment, positioning players relative to that environment, and is designed for multi-user interaction. The thesis combines techniques from inertial navigation, OpenGL ES, Android, and client-server interaction to implement a reasonable solution, and provides research alongside supporting design and implementation decisions, and ends by making conclusions about how to further the technology and possible real-world applications. |