CIT 594 Assignment 13: Pair Programming (Scala)
Spring 2015, David Matuszek
You are the instructor of an introductory programming class. For each programming assignment, you want to put all your students into twoperson teams, such that each student gets a different partner for every assignment.
Basic assumptions:
numStudents
students, where 20 ≤ numStudents
≤ 40. numAssignments
assignments, where 8 ≤ numAssignments
≤ 12.Additional, simplifying assumptions:
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]]
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]]]
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 definecheck
as:
def check(List[List[Team]): Option[List[Team]]
You can also use type aliases to define more type aliases. For example you might saytype 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 welldefined 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:


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(n^{4})
, 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.
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.