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.
Below are some projects that I've advised at Princeton.
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 A4 + B2 = Cp 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.
