Class Scheduling

Back to homepage

This PE is worth 15% of your grade. You must work on it alone, without discussing with anyone (whether online or offline).

Problem Description

Before the start of each semester, all University departments undergo a class scheduling exercise so that the timetable can be released early for students to plan their coursework.

We shall look at a scaled down version of such an exercise where classes are scheduled within a single day. A module comprise only two types of classes:

Lecture -- two hours per session
Tutorial -- one hour per session

A class can be represented as follows

CS2030 L1 @ LT19 [hchia] 10--12

which represents a CS2030 (L)ecture with class-id L1 at the venue LT19, and taught by hchia from 10am to 12nn.

A typical single-day schedule for one module could be

CS2030 L1 @ LT19 [hchia] 10--12
CS2030 T1 @ SR7 [tsim] 12--13
CS2030 T2 @ SR8 [hchia] 14--15
CS2030 T3 @ SR7 [dlee] 15--16
CS2030 T4 @ SR8 [ehan] 15--16
CS2030 L2 @ LT19 [hchia] 16--18

Notice that tutorial classes of a module can be scheduled to run in parallel (such as tutorials T3 and T4), provided that the venues and the module instructors are different. Moreover, since each lecture class serves all students in a module, L1 and L2 cannot clash. Not only that, a lecture of a module cannot clash with a tutorial of the same module. In other words, we do not split students of a module into different lecture groups, but they are split into different tutorial groups.

Task

Your task is to write a Java program to facilitate the creation of a single-day class schedule for a number of modules. Classes are scheduled one at a time only if they do not clash with other classes. Take note of the following:

there are two types of classes: lecture (a class prefixed with L), and tutorial (a class prefixed with T)
each class has a unique identifier represented by L or T followed by an integer class number: e.g. L1, T1, T2, etc...
venues used for lectures will not be used for tutorials, and vice versa

This task is divided into several levels. Read through all the levels to see how the different levels are related.

Remember to:

write each class in a separate .java file
always compile your program files first before using jshell to test your program
declare object properties starting with private final...
you may import any Java package; however do not use the wild card * in your import statements, else CodeCrunch will render your program uncompilable
all tests use valid arguments; you need not check for validity of arguments; null will not used for the tests

Level 1

Write a Java class Instructor to facilitate the creation of immutable objects to represent the instructors. Include the overriding equals method to compare if two instructor objects are the same.

$ javac your_java_files
$ jshell -q your_java_files_in_bottom-up_dependency_order < test1.jsh
jshell> new Instructor("hchia")
$.. ==> hchia
jshell> new Instructor("hchia").equals(new Instructor("tsim"))
$.. ==> false
jshell> new Instructor("tsim").equals(new Instructor("tsim"))
$.. ==> true
jshell> new Instructor("tsim").equals((Object)(new Instructor("tsim")))
$.. ==> true
jshell> new Instructor("hchia").equals("hchia")
$.. ==> false
jshell> /exit

Level 2

Write appropriate Java classes to facilitate the creation of an immutable object to represent a scheduled class. Each class (Lecture or Tutorial) is defined by the following:

module code represented as a String
class-id represented by a positive integer
venue-id represented as a String
start time represented as an integer in the range [8, 23]
duration of 2 hours for lecture, and 1 hour for tutorial
the module instructor of the class

You will also need to include the methods hasSameModule, hasSameInstructor and hasSameVenue, that can be called via any class (Lecture or Tutorial) and takes in another class as argument.

$ javac your_java_files
$ jshell -q your_java_files_in_bottom-up_dependency_order < test2.jsh
jshell> Lecture l1 = new Lecture("CS2030", 1, "LT19", new Instructor("hchia"), 10)
jshell> Tutorial t1 = new Tutorial("CS2030", 1, "SR7", new Instructor("tsim"), 12)
jshell> Tutorial t2 = new Tutorial("CS2030", 2, "SR8", new Instructor("hchia"), 12)
jshell> Lecture l2 = new Lecture("CS2040", 1, "LT19", new Instructor("tanst"), 12)
jshell> l1.hasSameModule(t1)
$.. ==> true
jshell> l1.hasSameModule(l2)
$.. ==> false
jshell> l1.hasSameInstructor(t1)
$.. ==> false
jshell> l1.hasSameInstructor(t2)
$.. ==> true
jshell> l1.hasSameVenue(l2)
$.. ==> true
jshell> t1.hasSameVenue(t2)
$.. ==> false
jshell> /exit

Level 3

Define the clashWith method that determines if two scheduled classes clash. Recall that no two lecture classes can have overlapping time slots. However tutorials of the same module can be scheduled in parallel if the instructors and venues are different.

$ javac your_java_files
$ jshell -q your_java_files_in_bottom-up_dependency_order < test3.jsh
jshell> Lecture hchia_L = new Lecture("CS2030", 1, "LT19", new Instructor("hchia"), 10)
jshell> hchia_L.clashWith(hchia_L)
$.. ==> true
jshell> hchia_L.clashWith(new Lecture("CS2030", 1, "LT19", new Instructor("hchia"), 10))
$.. ==> true
jshell> hchia_L.clashWith(new Lecture("CS2030", 1, "LT19", new Instructor("tsim"), 11))
$.. ==> true
jshell> hchia_L.clashWith(new Lecture("CS2030", 1, "LT19", new Instructor("hchia"), 12))
$.. ==> false
jshell> hchia_L.clashWith(new Lecture("CS2040", 1, "LT19", new Instructor("tanst"), 10))
$.. ==> true
jshell> Tutorial tsim_T = new Tutorial("CS2030", 1, "SR7", new Instructor("tsim"), 10)
jshell> tsim_T.clashWith(tsim_T)
$.. ==> true
jshell> tsim_T.clashWith(hchia_L)
$.. ==> true
jshell> hchia_L.clashWith(tsim_T)
$.. ==> true
jshell> tsim_T.clashWith(new Tutorial("CS2030", 2, "SR8", new Instructor("ehan"), 10))
$.. ==> false
jshell> tsim_T.clashWith(new Tutorial("CS2030", 2, "SR7", new Instructor("ehan"), 10))
$.. ==> true
jshell> tsim_T.clashWith(new Tutorial("CS2030", 2, "SR8", new Instructor("tsim"), 10))
$.. ==> true
jshell> tsim_T.clashWith(new Tutorial("CS2040", 2, "SR8", new Instructor("tsim"), 10))
$.. ==> true
jshell> /exit

Level 4

Write a Java class Schedule to create an immutable schedule of classes. Include a method add that takes in a class as argument and adds to the current schedule only if the class does not clash with existing classes in the schedule.

$ javac your_java_files
$ jshell -q your_java_files_in_bottom-up_dependency_order < test4.jsh
jshell> Schedule s0 = new Schedule()
jshell> s0 = s0.add(new Lecture("CS2030", 1, "LT19", new Instructor("hchia"), 10))
jshell> System.out.println(s0)
CS2030 L1 @ LT19 [hchia] 10--12
jshell> Schedule s = s0.add(new Tutorial("CS2030", 1, "SR7", new Instructor("tsim"), 11))
jshell> System.out.println(s)
CS2030 L1 @ LT19 [hchia] 10--12
jshell> s = s.add(new Tutorial("CS2030", 1, "SR7", new Instructor("tsim"), 12))
jshell> System.out.println(s)
CS2030 L1 @ LT19 [hchia] 10--12
CS2030 T1 @ SR7 [tsim] 12--13
jshell> System.out.println(s0)
CS2030 L1 @ LT19 [hchia] 10--12
jshell> s = s.add(new Lecture("CS2030", 2, "LT19", new Instructor("hchia"), 16))
jshell> s = s.add(new Lecture("CS2040", 1, "I3-AUD", new Instructor("tanst"), 15))
jshell> s = s.add(new Tutorial("CS2030", 4, "SR8", new Instructor("ehan"), 15))
jshell> s = s.add(new Tutorial("CS2030", 3, "SR7", new Instructor("dlee"), 15))
jshell> s = s.add(new Tutorial("CS2030", 2, "SR7", new Instructor("hchia"), 14))
jshell> System.out.println(s)
CS2030 L1 @ LT19 [hchia] 10--12
CS2030 T1 @ SR7 [tsim] 12--13
CS2030 T2 @ SR7 [hchia] 14--15
CS2030 T3 @ SR7 [dlee] 15--16
CS2030 T4 @ SR8 [ehan] 15--16
CS2040 L1 @ I3-AUD [tanst] 15--17
CS2030 L2 @ LT19 [hchia] 16--18
jshell> /exit

Note that the output of a schedule is in chronological order of start time. In the case of two classes have the same start time, then the earlier module should come first. If the module codes are also the same, then the smaller class-id should come first. Moreover, do not worry about extra blank lines in your output, all blank lines will be ignored in CodeCrunch.

Hint: Java's List interface provides a sort method.

Bonus Level 5 [No marks awarded]

Congratulations if you have made it thus far! Proceed on to this level to gain a priceless sense of personal achievement!

As you can see, the clash of classes imposes a constraint on when a class can be scheduled. Other than such hard constraints, there are also soft constraints which may affect timetabling. Two examples of such constraints are:

Instructor hchia's lunch time is from 2 to 4pm
Venues used for lectures must be scheduled with at least a one hour gap between them for disinfecting purposes (again due to COVID..)

Individual constraints are defined in separate Java classes. Each constraint makes use of a test method that takes in a schedule and applies the constraint check. The test method returns true if the constraint is met, or false otherwise.

Your task is to define Java classes HchiaLunch and GapBetweenLectures for constraints (1) and (2) above. You may only import Iterator from java.util.

$ javac your_java_files
$ jshell -q your_java_files_in_bottom-up_dependency_order < test5.jsh
jshell> Schedule s = new Schedule().
   ...> add(new Lecture("CS2030", 1, "LT19", new Instructor("hchia"), 10)).
   ...> add(new Tutorial("CS2030", 1, "SR7", new Instructor("tsim"), 12)).
   ...> add(new Lecture("CS2030", 2, "LT19", new Instructor("hchia"), 16)).
   ...> add(new Lecture("CS2040", 1, "I3-AUD", new Instructor("tanst"), 15)).
   ...> add(new Tutorial("CS2030", 4, "SR8", new Instructor("ehan"), 15)).
   ...> add(new Tutorial("CS2030", 3, "SR7", new Instructor("dlee"), 15)).
   ...> add(new Tutorial("CS2030", 2, "SR7", new Instructor("hchia"), 14))
jshell> System.out.println(s)
CS2030 L1 @ LT19 [hchia] 10--12
CS2030 T1 @ SR7 [tsim] 12--13
CS2030 T2 @ SR7 [hchia] 14--15
CS2030 T3 @ SR7 [dlee] 15--16
CS2030 T4 @ SR8 [ehan] 15--16
CS2040 L1 @ I3-AUD [tanst] 15--17
CS2030 L2 @ LT19 [hchia] 16--18
jshell> List constraints = List.of(new HchiaLunch(), new GapBetweenLectures());
jshell> List results = new ArrayList<>();
jshell> for (Constraint c : constraints) {
   ...>     results.add(c.test(s));
   ...> }
jshell> results
results ==> [false, true]
jshell> /exit

From the above sample run, the HchiaLunch constraint is not met as he has a tutorial class from 2 to 3pm. However, the GapBetweenLectures is met as the two lectures at LT19 is four hours apart; only one lecture is scheduled at I3-AUD.

Design Tips:

Suppose the Schedule class is implemented with the following list attribute:

class Schedule {
    private final List list... // use of raw type to mask out implementation details
    ...
}

Every soft-constraint check would entail going through the list of classes. While an accessor (getter) method can be written within Schedule to return the list to the constraint checker, this inevitably exposes the internal implementation details.

The proper design is to make Schedule an Iterable. The following Jshell session demonstrates how we can iterate over an Iterable.

jshell> class A implements Iterable {
   ...> private

jshell> class A implements Iterable {
   ...> private final List list = List.of("abc", "xyz");
   ...> @Override
   ...> public Iterator iterator() {
   ...> return this.list.iterator();
   ...> }}
|  created class A

jshell> for (String s : new A()) {
   ...> System.out.println(s);
   ...> }
abc
xyz

Notice that now, the client (in this case the for loop) is not dependent on the specific data structure that stores the strings. In fact, we may replace this list with any Java Collection and the client will still work!