Course scheduling algorithm or solution
Course scheduling algorithm or solution
Computers > Algorithms
12 Apr 2006 10:33 PDT
12 Apr 2006 12:34 PDT
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:
a. Credits: An arbitrary integer.
b. Pre-requisites: A list of 0 or more courses that must be
completed before this course is taken
a. A set of Courses to be taught by the school at any one given time
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
1) Courses 1?m
2) Students 1?n
3) Integer: X
4) Integer: Y
1) Students must not go above x units per Semester
2) Students must not fall below y units for any 2 sequential Semesters
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
i. O-notation (big-oh)
ii. o-notation (little-oh)
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
// 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
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.
|There is no answer at this time.|
|There are no comments at this time.|
Answers and comments provided on Google Answers are general
information, and are not intended to substitute for
informed professional medical, psychiatric, psychological, tax,
legal, investment, accounting, or other professional
advice. Google does not endorse, and expressly disclaims
liability for any product, manufacturer, distributor,
service or service provider mentioned or any opinion
expressed in answers or comments. Please read carefully the
Google Answers Terms of Service.
If you feel that you have found inappropriate content,
please let us know by emailing us at
with the question ID listed above. Thank you.
|Search Google Answers for