Groups will be assigned by either yourselves or me and will not change for the duration of the project. Each week, each group will have a leader, recorder, and presenter. The leader should schedule meetings, and move meeting discussions forward smoothly. The recorder will be responsible for keeping notes and writing any reports that are to be submitted to me. The presenter will be responsible for giving in class progress statements.

By the end of the project, groups should have working code, an
analysis of their algorithm, a discussion of the approach used
including test data, and a
discussion of things you might have liked to do but did not have time
for.

CPU scheduling

You have recently been hired by a large data center to develop a new
algorithm for scheduling jobs on a single processor. Clients can
submit jobs to the data center. Each job Sum of n dice

Most people are familiar with basic probabilities when rolling one die
or two dice. For example, what is the probability of a roll of two
random six sided dice summing to seven? But not much is typically known about Google Maps Spatial Queries

Google maps and other map search engines allow users to search using text queries that describe geographic locations. Another way to search for objects would be to allow searches to be describe by a geographic box, circle, or in the most general case, an arbitrary two dimensional simply connected planar region. How would you design a data structure to store and query two dimensional point data using such query regions. It suffices to focus on bounded rectangular axis-aligned queries. Can you design a structure to support queries and updates? Analyze the space and runtime complexity of your approach.
Keep 'em separated

Election fever is sweeping through campus and a variety of student organizations are planning to staff a variety of booths over the weekend to support their cause. Groups have place their rectangular booths across Cunningham field (the rugby teams were away that weekend) in a haphazard manner. With no football team and no ruggers on campus to break up anticipated disputes, the campus administration has decided it would be safest if they could set up a temporary partition or fence to separate the two main groups of booths: Democrats and Republicans. The partition must be a simple straight line. Depending on the configuration of booths, such a partition may not be possible. Design an algorithm that determines if two groups of booths can be separated by a single line and returns one possible line if a separation is possible, or informs users that no such separation is possible. What is the complexity of your algorithm. Will it work on all possible configurations of booths, or only under limiting assumptions? Explain.
Intersection monitoring

Traffic in Philadelphia has become a mess. City planners would like to remote traffic monitors to observe traffic patterns to eventually commission construction project to relieve the traffic. Suppose a traffic monitor can only be placed at intersections and can only observe traffic along any road meeting at that intersection until the next intersection along that road. (It is easier for me to draw a picture of this). Naturally, the city would like to monitor all roads in the city with the minimal number of monitors. Design an algorithm that can determine the minimal number of monitors needed and their location such that all roads segments can be seen by at least one monitor.