Schedule Algo Design

Naive Algorithm for Course Scheduling

1. Input: Courses and preferences.
2. Process:
   • Generate all possible combinations of elective courses.
   • For each combination, enumerate every possible section arrangement.
   • Assess each potential schedule based on the given preferences.
3. Output: The schedule that attains the highest preference score.

Enhanced Algorithm for Optimized Course Scheduling

1. Input: Courses and preferences.
2. Process:
   • Enumerate all combinations of elective courses.
   • Innovatively search through potential schedules:
     • Prioritize sections using heuristic methods, such as selecting single-section classes first.
     • Implement various pruning techniques:
       • Partially evaluate schedules even if not all sections are finalized.
       • Discontinue search if hard preferences are breached.
       • Halt if no further potential schedule can surpass the current highest score.
3. Output: The most optimal schedule based on preference scoring.

Advanced Algorithm with Heuristics and Coroutines

1. Input: Courses and preferences.
2. Initial Steps:
   • Make random course and section selections to establish a baseline score for schedules, aiding in efficient pruning.
   • Combine each elective with mandatory courses and rank them in descending order based on scores to prioritize higher scoring schedules.
3. Process:
   • Systematically enumerate course combinations, employing coroutines for efficient processing.
   • Conduct a detailed search through potential schedules:
     • Apply heuristic ordering for section selection.
     • Utilize advanced pruning strategies:
       • Continuously evaluate schedules, even if incomplete.
       • Order potential combinations by descending score for earlier discovery of higher-scoring schedules.
       • Cease searching if hard preferences are not met or if no better schedule can be derived.
4. Output: The highest-scoring, preference-aligned schedule.

On the same set of some intensive input, here are the performances:

1. Naive: 300s+
2. Enhanced: ~25s
3. Advanced: ~2s