# Course scheduling is a practical problem in that multiple courses are scheduled to be offered at different time slots in

This problem has been solved!

Do you need an answer to a question different from the above? Ask your question!

## Question:

As we discussed in the class, for each course there are two attributes: classroom and time which have the impact to the scheduling. Here is a toy example of the course scheduling problem: there are five courses {A, B, C, D, E}, four time slots {1, 2, 3, 4} and there are two classrooms {I, J} (I stands for Integrated lab classroom, while J stands for Joyful classroom). For each classroom, we could only schedule one course at a time.

Here are some other constraints:

Course B must be offered at time slot 1

Course D must be offered at time slot 3 or after

Course A is to be offered at time slot 1 or 2

Course D must be offered before C

Courses A, B, C need to use computer lab, so they would rather be scheduled to classroom I, Course D and E would use classroom J.

In this assignment, you are asked to implement solving the course scheduling problem based on the modified arc consistency algorithm.

You need to implement the following steps:

1. based on all the constraints, build the constraint graph (with programming, but not manually build the graph)

2. Implement the minimum remaining values (MRV) heuristic, it will be used to order the variables when there is a need to select among many variables for consideration. e.g., you could use it to determine how to choose a variable to assign value in the backtracking-search algorithm, or you may try to manage the arcs in the queue in ARC algorithm, etc.

3. enforce unary constraints, if there are existing unary constraints, we could easily reduce the domain(s) on those related variables.

4. Implement forward-checking on top of the backtracking search, again, you could utilize the sample code provided, but please make sure you have a new function named "forward-checking" to differentiate it from the original backtracking search.

5. arc consistency algorithm, I would suggest you to integrate above features if possible to improve the standard ARC.

**Related Book For**

## Essentials of Database Management

ISBN: 978-0133405682

1st edition

Authors: Jeffrey A. Hoffer, Heikki Topi, Ramesh Venkataraman

**View Solution**

Create a free account to access the answer

**Cannot find your solution?**

Post a FREE question now and get an answer within minutes.
* Average response time.

**Question Details**

Chapter #

**4**Section: Problems and Exercises

Problem: 17

**Posted Date:**September 25, 2023 04:13:53