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:
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
View the highlevel System Diagram.
- Navigate from the source to the target along a predetermined series of waypoints.
- Locate another NXT which is broadcasting its
position with Zigbee module called Xbee. The
NXT may be stationary or moving.
Segmented Sieve of Eratosthenes. (2014)
Read about my paper.
- The Eratosthenes' Sieve algorithm stores an array to represent the
primality of each integer. My project performs
optimization via the following methods:
- Reusing a smaller array to represent segments of the numbers to be sieved reduces memory.
- 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.
- 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.
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
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
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.