View Question
Q: Course scheduling algorithm or solution ( No Answer,   0 Comments )
 Question
 Subject: Course scheduling algorithm or solution Category: Computers > Algorithms Asked by: anthony3425-ga List Price: \$200.00 Posted: 12 Apr 2006 10:33 PDT Expires: 12 Apr 2006 12:34 PDT Question ID: 718227
 ```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.```