Sometimes problems that look simple on the surface hide depths of difficulty underneath. Here are a couple of examples of simple ideas with a lot of room to explore.
Assume you are in charge of planning several dinners for large organization. Assume that
How should you arrange seating at the s dinners (after the first) so that over the course of the year each member will have met as many other members as possible?
This problem can be cast as an integer program and is a special case of the Graph Partitioning Problem, which in full generality is NP hard (that is, there is no known solution algorithm whose running time is a polynomial in the size of the problem). One option for this summer is to see if it is possible to exploit the special structure of this problem to find a polynomial time algorithm, and if not, establish bounds on the running time for non-polynomial-time algorithms.
Further ReadingsWhat do computer animation, robotics, and protein configuration have in common? They can all be described in terms of smooth motion in n-dimensional space. That is, positions may be better described by many parameters (such as angles and distances from nearby points) instead of three (or four) coordinates. This summer, we might study how Lie Algebras (or other constructions) allow for modelling of instantaneous velocities in various geometries.