Lab 7: Exam Scheduling Lab 7: Exam Scheduling Aaron Bauer march 2, 2022 Lab 7: Exam Scheduling1 Assigned: Wednesday, March 02 Check-in Post: Before 9pm Tuesday, March 8 (check-in forum) Due: 9pm Wednesday, March 11 Collaboration: Partner assignment (groups of 2 people—you may also work alone) Handout: starter project Submit: Upload ExamScheduler.java to Lab 7. If you make any changes to UndirectedGraph.java or create any new Java files, upload those as well. If you attempt any Challenges upload a text file named challenges.txt describing what you did. Reference: Introduction to Graphs Graph Data Structures VS Code Live Share—useful for remote pair programming in VS Code 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: Gain experience using basic graph building and traversal operations. Develop a fairly sophisticated algorithm requiring several coordinated data structures. You will use a greedy algorithm to determine an assignment of classes to exam slots such that: No student is enrolled in two courses assigned to the same exam slot. Any attempt to combine two exam slots into one slot would violate rule 1. 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 To gain experience working with data represented as a graph To practice translating an algorithm into code by implementing the greedy algorithm described in this writeup To practice managing multiple interacting data structures Preparatory Exercises Read this entire writeup Watch the Introductory Video Download the starter project, unzip it into its own folder, and open that folder in VS Code. 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 Write pseudocode for (a) processing the input file and (b) generating a schedule by Friday, March 4 Implement and test processing the input file and constructing the graph by Monday, March 7 Implement and test generating a schedule by Wednesday, March 9 Debug and attempt Challenges by Friday, March 11 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 David Liben-Nowell
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 David Liben-Nowell 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: No student is enrolled in two courses assigned to the same exam slot (we can’t be in two places at once, after all). 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: Each node of the graph is a course taken by at least one student in the college. An edge is drawn between two nodes if there is at least one student taking both courses. 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. Choose a course (say, PHIL 112) and stick it in the first time slot. Search for a course to which it is not connected. 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) 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. 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 V()
// return an iterable of the vertices neighboring v
public Iterable 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 We can specify which input file to use via the main method 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 Every vertex in the graph appears in the schedule exactly once Every scheduled exam is a vertex in the graph There are no conflicts (i.e., graph edges) between courses scheduled in the same slot No two slots can be merged without creating conflicts 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: Ordered Output (0.5 points). Print out a final exam schedule ordered by course name/number (ie, AFR 100 would be first, and WGST 999 would be last, if such courses present in the input file). Student Schedules (0.5 points). Print out a final exam schedule for each student, listing students in alphabetical order. Randomize! (1 point). To find a schedule with the fewest slots, you could attempt repeatedly use the greedy algorithm on random orderings of the nodes. After running for a while, you may get lucky and find a schedule close to the optimal, even if you are not guaranteed to find the true optimal. As output, list the largest and smallest solution found in a given run. Give ’em a Break (1 point). Arrange the time slots in an order which tries to minimize the number of students who must take exams in three consecutive time slots. This is trickier than the other options! Striving for Balance (1 point). In addition to trying to generate a schedule with the fewest number of slots, generate a schedule that attempts to distribute the exams in some balanced way. This could be the same number of exams per slot (or, more ambitiously, the same number of students per slot). 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 Submitted 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 Adapted from Bill Lenhart and Bill Jannen: https://williams-cs.github.io/cs136-f20-www/labs/exam-scheduling.html↩︎ Curious what a graph for 100 students would look like? Here’s the one for medium.txt↩︎
