Lab 10: Exam Scheduling

This week, you will write a program 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 slots into one would violate rule 1. The second requirement ensures that we do not gratuitously waste exam slots (students would like to get out of here as soon as possible, after all).

PRE-LAB: Step 1

Before lab, read through this entire handout carefully. You should construct a design document explaining the general operation of your algorithm and which classes you intend to create to represent various objects in the program. Since you will be working with a partner, you should each create your own design document. Bring your design document to lab on Wednesday.

Input

The input to your program will be a text file containing (fictitious) student class information. For example:

Jeannie Albrecht
CSCI 136
MATH 251
ENGL 201
PHIL 101
Duane Bailey
PSYC 212
ENGL 201
HIST 301
CSCI 136
Andrea Danyluk
SOC 201
CSCI 136
MATH 251
PSYC 212

For each student, there are five lines. The first is the name, and the next four are the courses for that student. In our fictional world, we have no over-achievers taking 5 or more courses.

  • Jeannie Albrecht is taking CSCI 136, MATH 251, ENGL 201, and PHIL 101;
  • Duane Bailey is taking PSYC 212, ENGL 201, HIST 301, and CSCI 136; and
  • Andrea Danyluk is taking SOC 201, CSCI 136, MATH 251, and PSYC 212.

We provide small, medium, and large input files in your starter repository.

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 and that all students take exactly four courses.

Output

The output of the program should be a list of time slots with the courses whose final will be given at that slot. For example [1]:

Slot 1: HIST 301 PHIL 101 SOC 201
Slot 2: CSCI 136
Slot 3: ENGL 201
Slot 4: MATH 251
Slot 5: PSYC 212

Algorithm

The key to doing this assignment is to build a graph as you read in the file of students and their schedules. Each node of the graph will be a course taken by at least one student in the college. An edge will be drawn between two nodes if there is at least one student taking both courses. The label of an edge could be the number of students with both classes (although we don’t really need the weights for this program).

Therefore, if there are only the three students listed above, the graph would be as given below (edges without a weight label have weight 1).

A greedy algorithm to find an exam schedule satisfying our two constraints might work as follows. Choose a course (e.g., PHIL 101) and assign it to 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. Now try to find another which is not connected to any of those already in the time slot. If you find one (e.g., SOC 201), add it to the time slot. Continue until all nodes in the graph are connected to at least one element in the time slot. When this happens, no more courses can be added to the time slot (why?). 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 them from the graph or you could mark them as visited and then ignore them in future passes. Below, we’ll assume that we’ve removed them from the graph.

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.

Finally, print the exam schedule. For the graph shown above, here is one solution:

Slot 1: PHIL 101 HIST 301 SOC 201
Slot 2: MATH 251
Slot 3: CSCI 136
Slot 4: ENGL 201
Slot 5: PSYC 212

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 four time slots. See if you can find one! A greedy algorithm of this sort will give you a schedule with \(n\) slots, no two of which can be combined, but a different selection of courses in slots may result in fewer than \(n\) slots. Any schedule satisfying our constraints will be acceptable (although see below for extensions to compute the optimal solution).

Building the Graph

We recommend that you use a list-based graph implementation rather than a matrix-based one. Why does that choice make the most sense for this application? Think about the relative strengths of list-based and matrix-based graph representations as you implement the lab. Vertex labels should be the course names.

Extensions

For full credit on this lab, please complete at least one interesting extension to the program, from those listed below. This is also a great opportunity for earning some extra credit by adding any features you find interesting. If you complete more than one extension, you will receive bonus credit.

  • Print out a final exam schedule ordered by course name/number (i.e., AFR 100 would be first, and WGST 999 would be last, if such courses are offered this semester). For each course, you should print all students taking that course.
  • Print out a final exam schedule for each student, listing students in alphabetical order. For each student, you should list which exam slots they should attend.
  • Randomize! To handle large files, you could also 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. Feel free to explore other approaches as well. As output, list the largest and smallest solutions found in a given run.
  • Arrange the time slots in an order that tries to minimize the number of students who must take exams in three consecutive time slots. This is trickier than the other options!

Be sure to indicate in the heading of your program (in comments) what extras you have included.

How to Run Your Program

Please ensure that your program can be run as follows (this example assumes the input file is called input.txt):

$ java ExamScheduler < input.txt
 

Lab Deliverables

We provide several input files, small.txt, medium.txt, and large.txt to help you design and test your program. We recommend that you initially develop your code using the small.txt file, and then move on to the larger files as you gain confidence in your code.

By the start of lab, you should see a new private repository called cs136lab10-examscheduling in your GitLab account.

For this lab, please submit the following:

cs136lab10-examscheduling/
    README.md
    ExamScheduler.java
    Student.java
    {any other classes you created}
    inputs/
        small.txt
        medium.txt
        large.txt

where ExamScheduler.java, Student.java and {any other classes you created} should contain your well-documented source code.

Recall in previous labs that you had a Java file that contained a convenient main method pre-populated with a variety of helpful tests. It is always a good practice to create a small set of tests to facilitate development, and you are encouraged to do so here.

As in all labs, you will be graded on design, documentation, style, and correctness. Be sure to document your program with appropriate comments, a general description at the top of the file, and a description of each method with pre- and post-conditions where appropriate. Also, use comments and descriptive variable names to clarify sections of the code which may not be clear to someone trying to understand it.

Whenever you see yourself duplicating functionality, consider moving that code to a helper method. There are several opportunities in this lab to simplify your code by using helper methods.

Submitting Your Lab

As you complete portions of this lab, you should commit your changes and push them. Commit early and often. When the deadline arrives, we will retrieve the latest version of your code. If you are confident that you are done, please use the phrase "Lab Submission" as the commit message for your final commit. If you later decide that you have more edits to make, it is OK. We will look at the latest commit before the deadline.

  • Be sure to push your changes to GitLab.
  • Verify your changes on GitLab. Navigate in your web browser to your private repository on GitLab. It should be available at https://evolene.cs.williams.edu/cs136-labs/[your usernames]/lab10-examscheduling.git. You should see all changes reflected in the files that you push. If not, go back and make sure you have both committed and pushed.

We will know that the files are yours because they are in your git repository. Do not include identifying information in the code that you submit. We grade your lab programs anonymously to avoid bias. In your README.md file, please cite any sources of inspiration or collaboration (e.g., conversations with classmates). We take the honor code very seriously, and so should you. Please include the statement "We are the sole authors of the work in this repository." in the comments at the top of your Java files.

Footnotes

[1] Different implementations of the algorithm may lead to different results!

[2] Or just mark them as visited and ignore them in future passes. Can you think of a reason why this might be better or worse than deleting them?

  • CSCI 136, Spring 2022

Website for CSCI 136, Spring 2022 (instructors: Sam McCauley and Dan Barowy)

Powered by Bootstrap 4 Github Pages