You may wish to view this question in a nicer than text format:
Word Version: http://programaccess.com/documents/CourseScheduleAlgorithmDefinition.doc
HTML version: http://programaccess.com/documents/Courseschedulealgorithmdefinition.htm

Summary of problem:  Find an efficient method of creating a schedule
of courses (for a school) to satisfy student graduation requirements
while minimizing the number of courses offered in such schedule.

///////////////////////////////////////////////////////
// Data-type definitions:
	1)	Course
		a.	Credits: An arbitrary integer.
		b.	Pre-requisites: A list of 0 or more courses that must be
completed before this course is taken
	2)	Semester
		a.	A set of Courses to be taught by the school at any one given time
	3)	Student
		a.	History: A list of completed courses
		i.	Not all students will have History
		b.	Program: A list of courses needed to take in order to graduate
		c.	Schedule: A list of courses the student must take in the coming semesters
		i.	There will be 1 or more courses scheduled per semester
		ii.	Not all students will have schedules
	4)	School schedule: A chronological list of Semesters

///////////////////////////////////////////////////////
// Input:
	1)	Courses 1?m
	2)	Students 1?n
	3)	Integer: X
	4)	Integer: Y

///////////////////////////////////////////////////////
// Constraints:
	1)	Students must not go above x units per Semester
	2)	Students must not fall below y units for any 2 sequential Semesters

///////////////////////////////////////////////////////
// Output:
	1)	A School schedule with the minimum number of Courses over all
semesters that will fulfill every student?s program
		a.	Note: It does not matter how many students are in a course

///////////////////////////////////////////////////////
// Possible Solutions:
	1)	Pre-built software that will solve this problem with little configuration
		a.	We need to plug this into a PHP/MySQL based system.  Something
that we can run in real time through such system is preferable.
		b.	We may later need to add other constraints to the system, so it
is preferable that such system allows this easily
		i.	Or if it?s heavily developed enough pre-defined constraints may already exist

	2)	An algorithm that will solve this problem in a reasonable amount
of time (would be computable by a p4 3Ghz in under 1 day
approximately), please provide the following:
		a.	Please provide asymptotic behavior of the given algorithm (okay
if not all given but we need a reasonable assurance we can use this
algorithm)
			i.	O-notation (big-oh) 
			ii.	o-notation (little-oh) 
			iii.	ÿ-notation 
			iv.	ÿ-notation 
			v.	ÿ-notation 
		b.	Heuristics can be used to bring down the running time so long as
they have minimal impact on results.

We do not need both solutions, but if multiple are easily available
feel free to mention everything so we may choose what best suites our
needs.

///////////////////////////////////////////////////////
// Data information:  The following information may be useful in
developing efficient/effective heuristics
	1)	Most Students will have very similar, and even exact student schedules.
		a.	This is because a ?new? student comes with no History.  We
estimate that 90% students will have been new students for us at one
point, and hence we will have chosen similar schedules.
	2)	The remaining 10% of the incoming students will likely have
homogeneous course backgrounds (general education / lower division). 
We estimate that 80% of Student history will fall into 30% of the
courses.
	3)	Most courses will not have long ?pre-requisite chains?
		a.	The longest chain we have currently is 4 courses long
		b.	Most chains do not exceed 4 courses
	4)	We expect a student to take approximately 1-3 courses per semester
and to complete their program in 15 semesters.