# Undergraduate Projects

## Interests

My main research interest is in the design, analysis, and implementation of computer algorithms, especially problems in combinatorial optimization. I am also happy to advise Princeton undergraduate projects in a number of popular computer science areas including the development of educational tools to illustrate computer science ideas. Here are a few possible topics:- Implement and investigate the empirical behavior of a recent graph algorithm or data structure.
- Implement and investigate the utility of recent web information algorithms that exploit the underlying hyperlink topology of the web.
- Develop pedagogical tools for the introductory computer science curriculum at Princeton and beyond.
- Design and implement visualizations of graph algorithms or data structures.

## Junior Projects

- Nicholas Byrd.
*The Automation and Improvement of the Outdoor Action Frosh Trip Assignment Process*. Fall 2006, Princeton University. Automate the assignment of 600 students to 70 outdoor action trips subject to a variety of constraints such as requests, gender ratio, physical condition, geographic diversity, and allergies. - Jon Epstein.
*Artificial Intelligence Algorithms for Domain.*Spring 2005, Princeton University. Create a computer player for the Parker Brother's game of Domain. Princeton campus landmarks. - Raymond Lenihan.
*From Here to There: Point to Point Directiosn on Princeton's Campus.*Spring 2005, Princeton University. Find shortest paths between Princeton campus landmarks. - Tianhui Li.
*A Theoretical Study of Link-Analysis Algorithms.*Fall 2005, Princeton University. Introduce an axiomatic framework (inspired from voting theory) for investigating link analysis algorithms, including PageRank, Hubs and Authorities, and SALSA. Prove that receiving a new incoming edge cannot decrease your PageRank. - Dan Benediktson.
*Complexity Analysis of Enhanced-Movement Sokoban Variants.*Fall 2005, Princeton University. Investigate the computational complexity of variants oof the game Sokoban. Proves PSPACE-complete and NP-hardness results for two natural variants. - Andrew Jennings.
*No Limit Texas Hold'em.*Spring 2004, Princeton University. Apply machine learning algorithms (perceptron and Adaboost) to predict the two card hand a player holds in Texas Hold'em based on preflop betting. - Joshua Lee.
*Visualization of Maximum Flow Algorithms.*Spring 2004, Princeton University. Algorithmic visualization of the Goldberg-Tarjan preflow-push algorithm for the maximum flow problem. - Don Sheehy.
*The Complexity of Domino Tiling Problems.*Fall 2004, Princeton University. Investigate the intractability and decidability of certain tiling problems in the plane using techinques from graph theory, group theory, and ergodic theory. - David Kaplan.
*Developing an Accessible GUI to a Box Diffusion Model for Use In Carbon Cycle Studies.*Fall 2004, Princeton University. Develop a graphical user interface for a HILDA (high-latitude excahnger/interior diffusion advection) box-diffusion model for use by geophysicists to understand global climate. - Monte McNair.
*Winning Tournament Poker.*Fall 2004, Princeton University. Design a bot to play online poker and win money at PartyPoker.com. - Josh Probst.
*Graphing collegefacebook.com.*Fall 2004, Princeton University. Analyze social networks at Central Michigan University by exploring student profiles and connections between students (friendships, dorm, major, fraternity). - Michael Dinitz.
*Graphical Representation of Clutters.*Fall 2003, Princeton University. Design an algorithm and software tool to convert from clutters to sets of minipaths of a k-terminal network and vice versa. - Alicia L. Wright.
*Artificial Intelligence As it Relates to the Two-Player Game of Connect Four.*Spring 2001, Princeton University. - Joe Rybacki.
*StatMaster.*Spring 2001, Princeton University. - Aaron Sarfatti and John Wei.
*Cray to Intel Architecture Optimization.*Fall 2001, Princeton University. The project is to port and optimize a numerical simulation of mantle convection named TERRA from a Cray architecture to an x86 architecture. - Amr Z. Kronfol.
*Dots-and-Boxes: A Neural Networks Approach.*Fall 2000, Princeton University. - Ilan Sender.
*An Approximation Algorithm for Non-Linear Shortest Path Problems in Bi-Criteria Networks: A Theme and Two Variations.*Spring 1999, Princeton University.

## Senior Projects

- Lisa Chung.
*Laptops in Public Education: The Teaching and Learning Technology Initiatives of Henrico County Public Schools.*Spring 2007, Princeton University. Assess Henrico County's Teaching and Learning Technology Initiative to issue iBooks to all teachers and high school students. - Jon Epstein.
*Learning Domain.*Spring 2006, Princeton University. Use reinforcement learning to estimate the utility of a game state for the Parker Brother's game of Domain. - Greg Fields.
*Artificial Intelligence in Horse Racing Games.*Spring 2006, Princeton University. Simulate the 3D motion of horses in a race using the A* path-finding algorithm. - Ryan Teising.
*The Game of Hex*. Spring 2004, Princeton University. Design a compute algorithm to play the two-player game of Hex using alpha-beta pruning and a well-chosen evaluation function. - Ian Prevost.
*Three Gambling Games - Let It Ride Poker, Casino War, and Tournament Texas Hold'em*. Spring 2004, Princeton University. Investigate how to obtain a systematic advantage in a variety of gambling games. - Michael C. Bulboff.
*A Sum of Kloosterman Sums: A Project in Mathematical Computation.*Spring 2002, Princeton University. This project focuses on the following generalized Fermat type conjecture: given three relatively prime integers A, B, and C, and a prime number p > 5, the only integral solutions to A^{4}+ B^{2}= C^{p}is A = B = C = 0. Mathematicians had reduced the problem to checking a finite number of cases, but the number of such cases is prohibitively large to explore by brute force. The goal of this project was to produce a computer-assisted proof of these cases. - Stephanie Duda and Michael Newman.
*MindSpeak: Networked Software for Lecture Interaction and Analysis.*Fall 2001, Princeton University. - Rachel Fithian.
*Improving Introductory Computer Science Education.*Fall 2001, Princeton University. - Paul Simbi.
*Visualizing Graph Algorithms.*Fall 2001, Princeton University. - Yasir Alvi.
*Searching on the Internet: Exploiting the Underlying Link Structure of the Web.*Spring 2001, Princeton University. - Andrew Sobel.
*Exploring the Optimal Coalescing Problem as a Chromatic Generalization of the Minimum k-cut Problem.*Spring 2001, Princeton University.