Multiple Computer Science Projects by Ricson Cheng

I attended SR from 2012 to 2015. In the Fall of 2015, I entered the Carnegie Mellon University with major in Computer Science.

GPS Multi-agent Robotics Project. (Spring of 2015)

I have chosen to use a NXT controller for this project because my interest is in the focus of software development. In order not to be bogged by any mechanical or electronic issue, Mindstorms/NXT is a natural choice.

The NXT controller is connected to a bluetooth enabled GPS receiver and compass in order to navigate. This project was broken into the following  two phases:

1. Navigate from the source to the target along a predetermined series of waypoints.
2. Locate another NXT which is broadcasting its position with  Zigbee module called Xbee. The NXT may be stationary or moving.

In order to successfully accomplish these tasks, GPS data must be checked for integrity. In addition, positional data is also transformed from latitude-longitude form to a local cartesian grid on which localization of all points can be done with triangulation.

View the highlevel System Diagram.

Segmented Sieve of Eratosthenes. (2014)

•  The Eratosthenes' Sieve algorithm stores an array to represent the primality of each integer.  My project performs optimization via the following methods:
  1. Reusing a smaller array to represent segments of the numbers to be sieved reduces memory.
  2. Excluding even numbers except 2. Thus, the first item in the array represents 3, the second, 5 and the third, 7, etc. This reduces memory by a half.
  3. The primality of each integer is stored as a single bit.  Each byte is composed of eight bits. Typically, an integer takes 4 bytes, or 32 bits, and a char, 1 byte, or 8 bits. By storing a boolean value in each bit of an integer, we can use one integer to store whether 32 integers are prime or not prime.
• In order to handle large N, it may be impossible to fit the entire array into memory.  My segmented sieve allows for this. In the segmented sieve algorithm, the array of primes that serve as the sieve are created with the traditional sieve. Another integer array is created; this is used to represent each segment. Finally, since the prime 3 will sieve out elements 1, 4, 7, ... in the array [1, 3, 5, 7, 9, 11 … ] but the elements 2, 5, 8, ... in the array [101, 103, 105, 107, 109, 111 ... ], a third array is required to store the position of the first multiple of a given prime in the segment.
  
  

Read about my paper.
 

Quicksort with Tripartite Partitioning. (2013)

This implementation of quicksort avoids many common worst case sorting scenarios with a number of optimizations. Quicksort traditionally allocates numbers less than or equal to the pivot to left and numbers greater than the pivot to the right side of the array.

When numbers appear many times in the array to be sorted, this becomes inefficient because the partitions are lopsided. The partitioning method implemented in the code assigns values equal to the pivot on the leftmost and rightmost sides of the array in order to keep the partitions balanced.

The recur0sive nature of quicksort also lends itself to parallel processsing. Each sorted partition of the array is recursively sorted with OpenMP. Each subproblem is distributed to a separate processor until a certain number of processes have been assigned. After that point, any additional process decreases performance by introducing more overhead.

Further optimization is achieved by using both a random and a median of medians selection algorithm for the pivot, depending on the size of the input array. Although the median-of-medians algorithm guarentees a pivot between the 30th percentile and the 70th percentile, it is much slower and is only used for large inputs.

When sorting a small input, or a small sub-problem of a bigger input, the sorting function reverts to insertion sort instead of recursively calling iteslf in order to increase performance.

Click here to view a performance test result.