After the PowerPoint presentation, we spent some time defining a few (hopefully interesting) problems, such as:

SoCBook:  You are trying to develop an app to help people connect online.  There are currently several hundred SoCBook users - your first task is to find the largest group that are all friends.  Your second task is to find the largest group such that none of them are friends.

Shuttle Loading:  You have been hired by NASA to help plan the final flight of the space shuttle to the space station.  There are many items that can be included in the final payload, each with a known potential benefit - your task is to choose a combination that stays within the mass restrictions for the flight, and maximizes the total value.

Travelling Salesperson:  Your task is to find the shortest route among a group of cities, such that you visit each city once and return to your starting point.

Event Scheduling:  Your task is to schedule 200 Orientation Week activities so that nobody is required to be in two places at once.  How many different time slots do you need?

Partition:  You are in charge of a work team, and you have two projects for them to complete.  You know the IQ of each employee.  You want to split the team into two groups so that the total IQ in each group is equal.  

Resource Allocation:  What is the smallest number of defibrillators you can install around campus (and where should you put them) so that there is at least one within 5 minutes of every classroom?


These problems seem quite unrelated - though you may have noticed that there is a common theme of choosing some elements of a large set.  It turns out that these problems have something very profound in common with each other.  We will spend the first part of 365 identifying and exploring the common nature of these and other problems.

To begin this exploration, we took a trip back in time to the 1960's.  We talked about how computers were just starting to become widespread, to the point where it was feasible for small labs or even individual researchers to have a computer at their disposal.  Simple programming languages such as BASIC were becoming available, opening the doors to the development of software by people with a broad range of interests, and a broad range of problems to solve.

People very quickly recognized that the problems they were trying to solve fell into two broad categories:  "easy" and "really hard".  Here we find the first evidence of similarity among the problems listed above - they are all in the "really hard" category.  But "really hard" is a very vague term ... we need to formalize it.