Projects, By Area of Expertise |
|||
| Basic Programming | Machine Learning | Engineering | |
| Systems | Robotics | Personal Interest | |
Or see some project highlights!
Basic Programming
Graph Implementations*
Tools: C++, Matrix Class, Vector Class
Implemented in: 15-113
Using an adjacency matrix implementation of a graph, output the input and output degrees of a directed graph. Next, reimplement the graph using an adjacency list consisting of a vector of structs. (Specification)
Templated Priority Queue*
Tools: C++, Templates, Linked List
Implemented in: 15-113
Implement a priority queue class using a linked list. (Specification) Update implementation of a priority queue to use templates and support arbitrary data types or classes. (Specification)
Map Implementation with Binary Search Trees*
Tools: C++, Binary Trees
Implemented in: 15-113
Implement a map between login id and student information struct. The map must support an indexing operator, key removal, and stream output. (Specification)
Postfix Calculator*
Tools: Java, Expression Trees, Inheritance
Implemented in: 15-211
Create an expression tree where each node is an operator and each leaf is a value. Support the output of the expression in prefix, infix or postfix.
File Compression*
Tools: Java, Tries
Implemented in: 15-211
Implement different methods of file compression such as Huffman Compression (uses a frequency-based prefix code), Lempel-Ziv (dictionary-based fixed-length compression), and lossy image compression (discrete cosine transform).
Graph Implementation*
Tools: Java, Iterators
Implemented in: 15-211
Implement a graph through edge and vertex classes, and provide iterators for accessing these data structures.
Basic Functional Programming Exercises*
Tools: SML, mutual recursion
Implemented in: 15-212
Perform a variety of tasks using a functional programming language such as the the composition of two real valued functions, exponentiation using function composition, odd/even functions using mutual recursion, and approximation of infinite continued fractions. Emphasis is placed on inductively proving the validity of algorithms.
Advanced Functional Programming Exercises*
Tools: SML, Binomial Trees
Implemented in: 15-212
Perform a variety of tasks using a functional programming language. Create an implementation of Binomial Trees. Given a square space, tile all but 1 square of that space using Trominos (L-shaped Dominos). Create an abstract set data type and provide functions for intersection, union, and complement.
Dictionary*
Tools: SML
Implemented in: 15-212
Create a sorted dictionary that holds records of arbitrary types. Support insertion, removal, production of a filtered tree based on some boolean function, support for transforming the tree into a new data type given a conversion function.
Polynomial Representation*
Tools: SML
Implemented in: 15-212
Create a symbolic representation for polynomial expressions, with support for transforming the polynomial into a normalized form of a series of coefficients listed by power
Regular Expressions*
Tools: SML
Implemented in: 15-212
Create a representation for regular expressions and check arbitrary strings to see if they conform to the expression.
Red Black Tree Dictionary*
Tools: SML
Implemented in: 15-212
Create a dictionary based on Red-Black Trees
Binary Decision Diagrams*
Tools: SML
Implemented in: 15-212
Given an arbitrary boolean expression composed of and, or, not, and implication, parse into normal form. Offer the ability to check for equivalence.
Turtle Compiler*
Tools: SML
Implemented in: 15-212
Wrote a simple compiler that accepted a drawing language with variables and compiled it into a postscript file.
World Exploration*
Tools: SML, channels
Implemented in: 15-212
Using SML channels, create a robot process and a control center process with task division for exploration process. The robot process reports observations of the environment to the control center which incorporates this information into an atlas and sends the next move to the robot
Quines
Tools: C
Implemented in: 15-251
Given a program in C as input, the quine function will produce a file containing the original source and an additional function, quine, which will print the program's source code, including the function quine.
Rubiks Cube Solver
Tools: C
Implemented in: 15-251
Write a program which will solve an arbitrary Rubiks cube.
Building a Computer out of NAND Gates
Tools:
Implemented in: 15-251
Define all basic gates in terms of NAND gates and then build a processor with functional units like an adder and registers, and implement basic functions such as add and jump-if-zero. (Specification)
Systems
Bit Manipulation Puzzles*
Tools: C, basic logical operators
Implemented in: 15-213
Using basic logical and arithmetic operators write a number of bit manipulations such as finding the smallest bit position, determining the greater of two numbers, or computing the absolute value. (Specification)
Binary Bomb
Tools: C, gdb
Implemented in: 15-213
Students are given an executable known as a "binary bomb" consisting of a number of "stages" where the program accepts input, performs some unknown functions, and "explodes" if the input does not satisfy necessary properties. Students are challenged to diassemble the executable, use the assembly code to understand the functions, and "defuse" the bomb by providing the correct inputs. The debugger 'gdb' is used to assist students in understanding how the program operates. (Specification)
Buffer Bomb
Tools: C, asm
Implemented in: 15-213
Given the extreme danger of buffer overrun exploits in modern programs, students are given an executable that uses unsafe buffer storage techniques and challenged to overrun the buffer to execute specific commands. (Specification)
Systems-level code optimization
Tools: C
Implemented in: 15-213
Students attempt to optimize code that rotates and smooths images to obtain better cache performance. Strategies such as decomposing large matrix multiplications into a series of smaller "blocks" of multiplication are highlighted. (Specification)
Basic Shell*
Tools: C
Implemented in: 15-213
The focus of this project is to implement a shell that performs basic functions such as foreground and background execution, job control, and signal handling. (Specification)
Malloc package*
Tools: C
Implemented in: 15-213
This project requires students to create a competitive malloc package that supports malloc, free, and realloc. Solutions are benchmarked against a standard malloc implementation and judged on the basis of space utilization and throughput. Emphasis is placed on design decisions such as free-list format and coalescing strategy. (Specification)
Multi-threaded, logging Web Proxy*
Tools: C, sockets, threads
Implemented in: 15-213
Have a web proxy which spawns worker threads to handle web requests on a given socket. Using thread-safe routines, log all requests made through the proxy, block requests based on a filter list and serve requests for valid web pages. (Specification)
Rudimentary File Encryption*
Tools: C
Implemented in: 18-347
Use a simple file encryption method to encode and decode text
Cache Simulator
Tools: C
Implemented in: 18-347
Write a simulator that tracks the addresses stored in a cache with varying line sizes, associativity, and replacement policies. Map the performance space of the cache using different memory trace files to choose an optimal design.
Retargeting a Solaris Compiler to x86*
Tools: SML, asm
Implemented in: 15-411
Modify the appropriate portions of a compiler supporting basic arithmetic to produce x86 GAS instructions instead of Solaris instructions
Compiler with data types and control structures*
Tools: SML, flex, bison
Implemented in: 15-411
Modify the grammar of the compiler's parser to accept data types and modify the symbol table accordingly. Add support for control structures such as if-else, while, and for loops.
Compiler with functions*
Tools: SML
Implemented in: 15-411
Added the ability to create and call functions, as well as variable scoping.
Advanced Shell
Tools: C
Implemented in: 15-412
Created a shell that supported job control, background and foreground execution, input and output redirection and arbitrary piping. (Specification)
Terminal Driver*
Tools: C, semaphores, monitors
Implemented in: 15-412
Wrote two versions (one using semaphores, the other using monitors) of a terminal driver with a hardware layer with system-level calls to the operating system and a software layer with support for functions such as reading, writing, and multicast. (Specification)
Kernel with demand paging*
Tools: C, ddd
Implemented in: 15-412
Created a kernel from scratch including the implementation of modules such as a virtual memory system, register-level hardware interactions, a context-switch handler, an interrupt/trap handler, support for basic system calls, process scheduling, and a demand paging system with a realistic disk simulation. (Specification)
File System*
Tools: C, ddd
Implemented in: 15-412
Implementation of a file system that features control of low-level disk scheduling and buffering, as well as data storage using custom designed inode structures that support hierarchical file structures with hard/symbolic links. (Specification)
Travelling Salesperson using Shared Memory
Tools: C, ANL macros
Implemented in: 15-495
Using supercomputers at the Pittsburgh Supercomputing Center, implement a solution to the travelling salesperson problem that examines all possible routes using static and dynamic task partitioning. Emphasis is placed on minimizing overhead and producing good scale-up and speed-up.(Specification)
Travelling Salesperson using Branch-and-Bound
Tools: C
Implemented in: 15-495
Improve the solution to the Travelling Salesperson problem using a best-yet route as an upper bound to new routes.(Specification)
Travelling Salesperson using Message Passing
Tools: C, MPI
Implemented in: 15-495
Re-implement the Travelling Salesperson problem using a message-passing framework(Specification)
Parallel Data Compression
Tools: C, pthreads
Implemented in: 15-495
Adapt a standard gzip implementation to parallel computation using parallel threading and shared memory.(Project Writeup)
Optimizing Queries for a Scientific Database
Tools: Postgres, SQL
Implemented in: 15-721
Using a scientific database of data from an earthquake simulation, attempt to optimize queries without nominal increases in storage space through different partitioning schemes and indices. (Project Proposal)
Clustering of Router Configuration Files*
Tools: Perl, Matlab
Implemented in: 15-744
The goal of this project was to create a tool to help network administrators understand the topology of a network without examining each router file, this was accomplished through clustering similar configurations together to provide basic categories of configuration files.(Project Writeup)
Machine Learning and Artificial Intelligence
Computer Othello Player*
Tools: Java, Game Trees
Implemented in: 15-211
Create a board represenation and computerized player for the game Othello. Project details included the exploration of position evaluation functions as well as an implementation of a variety of different strategies including greedy placement, and a game tree with fixed-depth minimax evaluation and Alpha-Beta pruning.
Auto Associators, Backpropagation
Tools: C
Implemented in: 85-419
Using provided tools, design the topology of neural networks and examine the learning performance of these networks.
Demonstration of Chunking in Working Memory using Elman Networks *
Tools: Matlab
Implemented in: 85-419
Using Elman Networks, which retain some activation from prior inputs, demonstrate the phenomenon of chunking where multiple inputs are grouped into a single unit to enhance memory (e.g. remembering phone numbers). (Project Writeup)
Decision Trees*
Tools: C
Implemented in: 15-681
Given a basic decision tree code base, implement entropy calculations and tree pruning and report results. (Specification)
DNA analysis with Neural Networks*
Tools: Matlab
Implemented in: 15-681
Complete the implementation of a neural network used to classify splice-junction sequences in DNA, deciding upon an input modality for DNA and a stopping criterion for completion.(Specification)
Spam Filtering using Bayesian Classification*
Tools: Matlab
Implemented in: 15-681
Create a spam filter that uses a small training set to develop a model of useful and junk mail, and implement several modes of classification to filter mail.(Specification)
Unsupervised Clustering of Router Configurations*
Tools: Perl, Matlab
Implemented in: 15-781
The goal of this project was to apply feature selection techniques using information gain to find salient features in router configuration files, and use these features in different unsupervised clustering algorithms (K-Means and Hierarchical Clustering) to discover similar categories of routers on a computer network. (Project Writeup)
Robotics
Clap Detection
Tools:C++
Implemented in: 16-199
Create a program capable of detecting claps.
IR Sensors
Tools:C++
Implemented in: 16-199
Wire an IR sensor to a parallel port connector, and use low-level C++ code to access IR pulses.
Servos
Tools:C++
Implemented in: 16-199
Wire a servo to the parallel port and write pulse functions to have the servo move around.
P, PD, PI, and PID controllers
Tools:C++
Implemented in: 16-299
Implement P, PI, PD, and PID controllers for a force feedback robot.
Rube Goldberg Soda Dispenser
Tools:
Implemented in: 24-354
Create a machine with at least five energy transfers that dispenses a can of soda.
Precise motion, Sensor-based locomotion
Tools:C, Legos
Implemented in: 24-354
Build a robot capable of accurately moving inches with centimeter precision and turning with 5 degree precision. Use IR sensors to detect obstacles and navigate a course.
Known and Unknown Maze Navigation
Tools:C, Legos
Implemented in: 24-354
Have a robot navigate both known and unknown mazes using information from IR sensors.
Robotic Arm Sketching
Tools:C, Legos
Implemented in: 24-354
Build a robotic arm and write a planner that uses information about obstacles in state space to reach goals safely.
Urban Search and Rescue
Tools:C, Legos
Implemented in: 24-354
Build a robot capable of performing remotely-operated search and rescue in a dangerous environment. The robot must fulfil a number of requirements such as climbing a 45-degree slope, driving over large bumps and turning in place.
Real-Time Robotic Timekeeping*
Tools:Denso Robotic Arm
Implemented in: 15-384
Use a Denso robotic arm and lucite pegs as well as a representation of time with second precision to build a clock that displays the time with second accuracy and cannot have appreciable lag.
Bowling with Robots*
Tools:Denso Robots
Implemented in: 15-384
Two robotic arms are pitted against each other - each has three pegs which it can bowl at its opponent in an attempt to knock down its opponents pegs, as well as the option of guarding its own pegs. The robot that knocks down the most pegs wins. My partner and I received first place trophies in the class tournament. (Specification)
Wandering, Turning Robot*
Tools:Java
Implemented in: 16-862
This assignment required groups to implement functions that allowed a robot to wander until an obstacle was detected or turn towards the closest object. (Specification)
Smarter Wandering*
Tools:Java
Implemented in: 16-862
Create basic functions that allow a robot to move a precise distance or turn a precise angle. Use these functions to create a state-less wanderer that explores a space using preset reactions as well as a stateful wanderer, which keeps information about previous motions to improve planning for future motion.(Specification)
Environment sensation, Corridor Following*
Tools:Java
Implemented in: 16-862
Have the robot report surrounding walls using sonar sensors. Have the robot navigate a narrow corridor without hitting walls.(Specification)
Precise Motion
Tools:Java
Implemented in: 16-862
Implement and test functions which allow the robot to navigate narrow corridors while minimizing encoder error.(Specification)
Maze Navigation the Hard Way
Tools:Java
Implemented in: 16-862
Have the robot navigate through a fixed, prespecified maze to a prespecified goal from six enumerated starting positions. Improve this behavior allowing the robot to find the goal without knowing its starting position. Finally, write a robot that maintains state to optimally navigate the maze based on sensory input. (Specification)
Maze Navigation the Easy Way
Tools:Java
Implemented in: 16-862
Given an arbitrary, known environment, write a sequential planner that reaches a specified goal even if the starting position is unknown. Use a camera interface to detect goal conditions.(Specification)
Navigating Unknown Mazes
Tools:Java
Implemented in: 16-862
Given an arbitrary, unknown environment, write a planner that interleaves planning (and partial planning as an optimization) and execution, using sensory input to refine knowledge about the environment. (Specification)
Cooperative Maze Navigation with Vision
Tools:Java
Implemented in: 16-862
Robots navigate known mazes looking for "gold", using a USB camera and vision routines to detect the gold, they pick up the gold using a magnet and return it to specified "cargo bays". Emphasis is placed on planning movement to avoid deadlock. Robots compete for gold in disjoint mazes during a final competition where our team made it to a semifinal competition.(Specification 1, Specification 2)
GRACE, Artificially Intelligent Graduate Student
Tools:C
Implemented in: 16-863
GRACE (Graduate Robot A Conference) is an entry to the American Associate of Artifical Intelligence Grand Challenge, to create a realistic robotic "graduate student" that will attend a conference, register at the entrance, socialize with colleagues in the hallways, perform menial tasks to earn her keep, and deliver a presentation to an audience of peers. My part in this project was to prepare Grace for one of her volunteer duties at the conference, guarding doors. Using vision algorithms, I programmed Grace to scan the visual field at approximately chest level looking for a "pink" badge that signified the person was authorized to enter the auditorium. Grace would admit or deny entrance using realistic face animations and speech. Furthermore, she would use laser rangefinders to detect the presence of people in her vicinity and wait until she was approached to accost visitors.
Intel Stayton Open Robotics Project
Tools:C
Implemented for: Personal Interest
Worked with a group of students creating cool demonstrations using Stayton boards. I wrote miscellaneous code, including a camera library to interface with a CMUCam, as well as a network communication library. These were used in "Tagbots", two robots that would roam a space until they found the other robot, after which they would move randomly to avoid being "tagged" in a similar fashion.
Engineering
GPS Control Circuit
Tools: Soldering iron
Implemented in: 18-100
Complete the control circuitry for a GPS receiver over the course of a semester.
Hardware Minesweeper Player
Tools: Verilog
Implemented in: 18-240
Complete K-Maps for minesweeper moves given the board state. Implement a synthesizable hardware minesweeper player on Altera FPGA boards.
Hardware Compression Protocol
Tools: Verilog
Implemented in: 18-240
Students are given a signalling protocol and a specification of control states, and must implement the protocol using control logic.
Network on a Chip: Design and Layout
Tools: Verilog, Cadence Spice, Virtuoso
Implemented in: 18-322
Create a synthesizable Verilog implementation of a Network-On-A-Chip processor based on specifications, with attention to logic minimization in terms of transistors. Build a prototype hardware layout and verify this layout using SPICE. Complete a transistor-level design using Virtuoso and verify that it meets the hardware level specification. Optimize sizing and placement for the most efficient design. (Specification)
Synthesizable Calculator with Memory
Tools: Verilog
Implemented in: 18-347
Create a calculator and modify the state diagram and corresponding hardware description to include signals for a memory function, which stores and retrieves a number from a memory cell.
Synthesizable L1 Cache Memory
Tools: Verilog
Implemented in: 18-347
Create a synthesizable L1 cache in Verilog with set-associativity and an effective replacement policy.
Hardware RSA Encryption
Tools: Verilog, C, NIOS, PIC
Implemented in: 18-545
Perform hardware RSA encryption, with a terminal program that runs on a PIC, external SRAM for storage, and synthesizable hardware communication handlers written in Verilog, and an overall software control module that runs on a NIOS core. (Specification)
Capstone Design Project: Hardware Face Detection, Breathalyzer analysis, Flash Memory storage.*
Tools: Verilog, C, NIOS, PIC
Implemented in: 18-545
In this project, our group designed a prototype hardware implementation of an automobile safety product. This product authenticates valid drivers using face detection algorithms operating on custom hardware, upon successful recognition the system will ask the driver to breathe into a breathalyzer and prove that he is sober. If both tests are successful, the car will unlock the car's ignition. Identity data is stored on secure digital media to allow convenient updates of the driver database and data portability. (Project Writeup)
Personal Interest Projects
(or code I wrote for fun)Music Organization*
Tools: C++
Implemented for: Personal Interest
Compare two directories to find duplicate mp3s.
Strategy Game Analysis*
Tools: C++
Implemented for: Personal Interest
Allow user to input a series of moves and results from the board game "Stratego" and let the user track the location of enemy pieces and the enemy's original board configuration.
Conversation Log Analysis*
Tools: Perl
Implemented for: Personal Interest
Analyze Instant Messaging logfiles, extract statistics about the data, parse different message and event types.
Internet Distractions*
Tools: Perl
Implemented for: Personal Interest
Allow users to view a random, anonymous quote from instant message conversations.
CGI FTP Utility*
Tools: Perl
Implemented for: Personal Interest
Track uploads to a directory subtree of an FTP server, display dynamic information about update time and users, and send appropriate e-mail based on a filter list.
Scheduling Utility*
Tools: Perl
Implemented for: Personal Interest
Allow users to easily publish and update an online schedule. Intelligently determine and display activity dates. (Originally implemented so my mother could keep her schedule online and accessible to family members.)
Genealogy Tracking*
Tools: Perl
Implemented for: Personal Interest
Accept data in a generic text base format and assemble a family tree that displays known relationships.
Survey Framework*
Tools: Perl
Implemented for: Personal Interest, Clubs, 85-340
Developed a custom survey framework according to personal style guidelines to collect data through the use of Likert scales and ranking menus. This framework was used for everything from polling my friends whether I should shave my goatee to a survey about attitudes towards marriage for a research methods course.