CIT 594 Assignment 13: Pair Programming (Scala)
Spring 2015, David Matuszek

Purposes of this assignment

General idea of the assignment

You are the instructor of an introductory programming class. For each programming assignment, you want to put all your students into two-person teams, such that each student gets a different partner for every assignment.

Basic assumptions:

Additional, simplifying assumptions:

In more detail

When the main method runs, it should call methods to

Also supply the following two methods:

def generateTeams(numStudents: Int, numAssignments: Int): List[List[Tuple2[Int, Int]]
where Tuple2[Int, Int] represents a pair of students; List[Tuple2[Int, Int]] represents all the student pairs for a given assignment; and each element of List[List[Tuple2[Int, Int]] represents the pairs for one assignment.

def check(teams: List[List[Tuple2[Int, Int]]): Option[List[Tuple2[Int, Int]]]
returns a list of student pairs that occur more than once in the input, or None if all the constraints are met.

These two methods (along with main) are required, but you will need to write several additional methods.

Scala hint: Within an object or a class, you can define an alias for a type, for example, type Team = Tuple2[Int, Int] . This would enable you to define check as:

     def check(List[List[Team]): Option[List[Team]]

You can also use type aliases to define more type aliases. For example you might say type Teams = List[Team].

The point of type aliases is to make complicated data structures more readable by giving them names.

It seems like there ought to be a simple and fast algorithm to generate these pairs, but to the best of my knowledge, there isn't. In theory it can be solved by systematically trying all possible pairings. In practice, this systematic approach requires an exponential amount of time, and is totally out of the question for the numbers involved.

You should recall that an algorithm is (1) a well-defined method that (2) terminates (3) in finite time (4) with a correct result. For this problem, "finite time" may be millenia rather than seconds, so any feasible program cannot justifiably be called an algorithm. Therefore, your goal has to be to write a program that has a very high probability of finding a solution in a reasonable amount of time. One way to do this is to use randomization to try to improve an incorrect solution.

Here's an analogy:

void stupidSort(int[] array) {
    while (!sorted(array)) {
        shuffle(array);
     }
}
void notAsStupidSort(int[] array) {
    while (!sorted(array)) {
        int i = rand.nextInt(array.length);
        int j = rand.nextInt(array.length);
        if (i < j && array[i] > array[j]) {
            swap(array, i, j);
        }
     }
}

The expected running time of stupidSort is O(n!), which is infeasible for arrays of any reasonable size. I think the running time of notAsStupidSort is O(n4), which is much superior.

The point of this analogy is, if you just try one random "solution" after another, you probably won't succeed. But if you start with a random "solution" and randomly improve it, you probably will succeed. I know this is possible, because years ago I wrote such a program for assigning teams in CIT 591, and it hasn't failed me yet.

Due date

Turn your assignment in to Canvas before 6 a.m. Tuesday, April 28. Late programs, even if only a minute late, will be penalized 5 points per day, up to a maximum penalty of 50 points.

Hard deadline: 6 a.m. Monday, May 4. Canvas will be set to reject any program submissions after that time.