The Bloom filter data structure tracks set-membership in a fast and space-efficient way. I first heard about Bloom filters when I saw them used in speeding up database search. Then, I heard about Microsoft using a stack of Bloom filters to speed up the Bing search engine’s keyword search.

In this project, I implemented a Bloom filter and a bit-sliced document signature in C. I also wrote unit tests and a collection of fun demos to show how Bloom filters and bit-sliced signatures can be used. This report gives an overview of the project, demos and results, and notable code design decisions.

• Read Report

Little Computer 3 (LC-3) is a reduced instruction set computer (RISC). This means that its architecture uses a limited set of optimized instructions to complete tasks. We implemented a virtual machine (VM) in C that can run compiled LC-3 assembly. Given program code in a compiled OBJ file, the VM can execute the instructions in the file.

In order to do this, it uses the memory structure defined in the LC-3 specification, including program memory, program registers, and condition flags. It reads and writes to these memory structures and manages I/O through the terminal. Our VM successfully plays game files!