Lab 7: Exam Scheduling

Aaron Bauer

February 27, 2021

Lab 7: Exam Scheduling1

Overview

For this lab you will write a program (that could be used) to schedule final exams for the registrar so that no student has two exams at the same time. The goals of this lab are to:

You will use a greedy algorithm to determine an assignment of classes to exam slots such that:

The second requirement ensures that we do not gratuitously waste exam slots (students would like to start their breaks as soon as possible, after all).

The goals for this lab are

Preparatory Exercises

  1. Read this entire writeup
  2. Watch the Introductory Video
  3. Download the starter project, unzip it into its own folder, and open that folder in VS Code.
  4. Plan out your implementation by writing pseudocode (i.e., an outline) for processing the input file and generating a schedule

Introductory Video

Panopto viewer link: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=5d6d5de1-d89e-4b95-931f-acdf000dda14

Suggested Timeline

Program Input

Before describing the solution strategy, let’s examine the data. The input to your program will be a text file containing (fictitious) student schedule information. For example:

    3 Aaron Bauer
    CS 201
    ENGL 202
    HIST 301
    3 Sneha Narayan
    PSYC 212
    ENGL 202
    PHIL 112
    3 Anya Vostinar
    CS 201
    MATH 236
    PSYC 212
    3 Eric Alexander
    SOAN 201
    HIST 301
    MATH 236

For each student, there will be between three and five consecutive lines. The first line is the number of courses a student is taking followed by the student’s name. After that there is a line for each of the courses that student is taking. In the above example:

Aaron Bauer is taking CS 201, ENGL 202, and HIST 301
Sneha Narayan is taking PSYC 212, ENGL 202, and PHIL 112
Anya Vostinar is taking CS 201, MATH 236, and PSYC 212
Eric Alexander is taking SOAN 201, HIST 301, and MATH 236

The start project contains small, medium, and large input files so you can test your program.

Note that whenever you process data in the “real world”, your code should carefully handle inputs that are not properly formatted. For the purpose of this lab, however, you can assume that all files are properly formatted.

Program Output

The output of your program should be a schedule that satisfies two constraints:

  1. No student is enrolled in two courses assigned to the same exam slot (we can’t be in two places at once, after all).
  2. Any attempt to combine two exam slots into one slot would violate rule 1.

This schedule should be provided as a list of time slots with the courses whose final will be given at that slot. For example, the output below describes a valid schedule for the student data above

Slot 1: PHIL 112, HIST 301
Slot 2: ENGL 202, MATH 236
Slot 3: PSYC 212, SOAN 201
Slot 4: CS 201

An Overview of the Algorithm

The key to doing this assignment is to build a graph as you read in the file of students and their schedules, where:

Thus if there are only the four students listed above, the graph would be as given below2.

A greedy algorithm to find an exam schedule satisfying our two constraints would work as follows.

  1. Choose a course (say, PHIL 112) and stick it in the first time slot.
  2. Search for a course to which it is not connected.
  3. If you find one (e.g., HIST 301), add it to the time slot. Continue until all nodes in the graph are adjacent to at least one element in the time slot. (This is already the case in this example, as PHIL 112 and HIST 301 together are adjacent to every other node)
  4. When this happens, no more courses can be added to the time slot (why?). By the way, the final set of elements in the time slot is said to be a maximal independent set in the graph.
  5. Once you have this set, you could remove the nodes from the graph, or you could mark them as visited and then ignore them in future passes.

If there are remaining nodes in the graph (there should be!), pick one and make it part of a new time slot, then try adding other courses to this new slot as described above. Continue adding time slots for remaining courses until all courses are taken care of. Then return the exam schedule. For the graph shown, here is one solution:

Slot 1: PHIL 112, HIST 301
Slot 2: ENGL 202, MATH 236
Slot 3: PSYC 212, SOAN 201
Slot 4: CS 201

Notice that no pair of time slots can be combined without creating a time conflict with a student. Unfortunately, this is not the minimal schedule as one can be formed with only three time slots. (See if you can find one!) Thus, if a greedy algorithm of this sort gives you a schedule with x slots, no two of which can be combined, a different selection of courses in slots may result in fewer than x slots. Any schedule satisfying our constraints will be acceptable (although see below for Challenges to compute better solutions).

Implementation Advice

The starter project includes adjacency-list-based implementation of an undirected graph in UndirectedGraph.java. I recommend you use this class to construct a graph from the input data (and then use that graph in generating a schedule). You are free to modify/enhance this implementation (this is not necessary to complete the lab), though you must preserve the existing functionaly, as the ScheduleChecker relies on it. Below is the API for the UndirectedGraph class:

public class UndirectedGraph {
    // construct an empty graph
    public UndirectedGraph()
    
    // return a new UndirectedGraph that is a copy of this graph
    public UndirectedGraph copy() 
    
    // add vertex v to the graph
    public void addVertex(String v)

    // add an undirected edge from u to v to the graph
    public void addEdge(String u, String v)

    // return a set of the vertices in the graph
    public Set<String> V()

    // return an iterable of the vertices neighboring v
    public Iterable<String> neighbors(String v)

    // return the degree of vertex v
    public int degree(String v)

    // remove vertex v, if present
    public void removeVertex(String v)

    // remove the undirected edge from u to v from the graph
    public void removeEdge(String u, String v)

    // return true if the graph contains vertex v
    public boolean containsVertex(String v)

    // return true if the graph contains an edge from u to v
    public boolean containsEdge(String u, String v)

    // return the number of vertices in the graph
    public int numVertices()

    // return the number of edges in the graph
    public int numEdges()
    
    // return a string representation of the adjacency lists
    public String toString()
}

You should implement the lab in the provided ExamScheduler.java (this is the file you will submit). As the TODO comments in the starter code suggest, the constructor (public ExamScheduler(String filename)) is where you can read the input file and construct the corresponding graph. I recommend using the In class from the algs4 library for this.

The makeSchedule method is where you should use the graph created in the constructor to generate and return a schedule. This is a similar structure to the TextGenerator class from Lab 5. See the Introductory Video for note about the (strange-looking) return type of makeSchedule.

We will evaluate your submission using the main method in ExamScheduler. You can add more methods and restructure the existing ones, but it must be the case that

  1. We can specify which input file to use via the main method
  2. The main method calls ScheduleChecker.check on the graph of the input file and the schedule you create for it (the printed output of ScheduleChecker.check is how we will grade the correctness of your program. See Testing for more details on SchedulerChecker.

Here is one possible way to find a collection of maximal independent sets from the graph (a more concrete description of the greedy algorithm described above): represent each “slot” by some sort of a list or set (or, if you’re implementing some of the extensions, consider a binary search tree like TreeSet). To find a maximal independent set for a slot, pick any vertex of the graph and add it to the slot. Then, iterate through all other vertices of the graph; if a vertex is not connected to any of the vertices already in the slot, add that vertex to the slot. Continue until you have tried all vertices. Now delete from the graph (or mark visited) all vertices that you added to the slot. Continue to fill successive slots in the same way until there are no vertices left in the graph.

Testing

There are two primary components of your implementation you will want to test: (1) constructing a graph from the input file and (2) generating a schedule. The simplest way to test the former is to print out the final graph for small.txt (System.out.println(graph); will use the toString method of the UndirectedGraph class to produce a string representation of graph to print out). A visualization of this graph is shown above, so you should make sure the graph you construct prints out with the same nodes and edges.

The ScheduleChecker class is provided to you for testing your schedule generation. ScheduleChecker.check (a static method) takes in an UndirectedGraph and a data structure representing an exam schedule (i.e., an iterable containing collections of strings, each collection representing one exam slot). It will print out the schedule (using ScheduleChecker.print), print out information about the graph and the schedule, and check for various inconsistencies. Specifically, it checks that

An error message will be printed for each inconsistency detected. The first two properties are what is meant by covers all courses in the Grading breakdown, and a SUCCESS message will be printed if those two conditions are satisfied. A final message indicating whether the schedule is correct or not will be printed at the end.

Style

You are expected to submit files that contains no checkstyle errors or warnings. You will lose 0.5 points per error (up to a maximum of 3) and per warning (up to a maximum of 2), as indicated in the Grading breakdown.

Challenges

Consider attempting any or all of these additional challenges if you have time:

Grading

This lab will be graded out of 40 points as shown below. See the Testing section for advice on how to evaluate whether your implementation is correct. Partial credit will be awarded based on evidence of a good-faith effort to implement the related features. Comments explaining your approach can help earn partial credit.

Requirement Points
SchedulerChecker.check reports 0 errors for small.txt 10 points
SchedulerChecker.check reports schedule covers all courses for small.txt 4 points
SchedulerChecker.check reports 0 errors for medium.txt 3 points
SchedulerChecker.check reports schedule covers all courses for medium.txt 3 points
SchedulerChecker.check reports 0 errors for large.txt 3 points
SchedulerChecker.check reports schedule covers all courses for large.txt 3 points
Reasonable running time (a few seconds) on all input files 4 points
Submitted files do not have any checkstyle errors 3 points
Sbumitted files do not have any checkstyle warnings 2 points
Check-in post 2 points
ExamScheduler.java compiles without warnings 0.5 points
Correct submission format (ExamScheduler.java) 0.5 points
Challenges up to 4 points

  1. Adapted from Bill Lenhart and Bill Jannen: https://williams-cs.github.io/cs136-f20-www/labs/exam-scheduling.html↩︎

  2. Curious what a graph for 100 students would look like? Here’s the one for medium.txt↩︎