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

# Purposes of this assignment

• Get you a little more familiar with Scala
• Give you experience with randomized methods

# 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:

• You will have `numStudents` students, where 20 ≤ `numStudents `≤ 40.
• You will have `numAssignments` assignments, where 8 ≤ `numAssignments` ≤ 12.

• You will have an even number of students.
• There are no absences; every student does every assignment.

# In more detail

When the `main` method runs, it should call methods to

• Ask the user for the number of students and the number of assignments. If the user enters a number that does not satisfy the above constraints, or something that isn't a number, the program should repeat the question as many times as necessary until the user enters valid numbers.
• Generate the teams for each assignment.
• Check whether the teams were generated successfully (if not, your program needs more work), and
• Print the results.

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.