Skip to main content

Secondary navigation:

2012 Bachelors Theses

computer science

Author: Tair Akhmejanov
 
download pdf
Title: Computational Complexity and Randomness
Advisor: Howard Straubing

Abstract

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
 
download pdf
Title: Relative Distributed Inertial Navigation Using Android Technology
Advisor: Ed Sciore

Abstract

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.