CSCI 136

CSCI 136 - Fall 2019

Data Structures & Advanced Programming

Lab 10: Exam Scheduling

You may again choose to work with a partner this week.
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

Regardless of whether or not you would like to work with a partner, please fill out the following Google form by Monday at midnight so that we can make your Lab 10 repositories. And, of course, develop a design document to bring to lab so that you can maximize the amount of progress you make during lab!

Input File

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
            SOCI 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:

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 SOCI 201 CSCI 136, MATH 251, and PSYC 212.

We will 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 SOCI 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).

Thus 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 would work as follows. Choose a course (say, PHIL 101) 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. Now try to find another which is not connected to any of those already in the time slot. If you find one (e.g., SOCI 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?). 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 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. Print the exam schedule. For the graph shown, here is one solution:

            Slot 1: PHIL 101, HIST 301, SOCI 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!) 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 extensions to compute the optimal solution).

Details

We recommend that you use the list-based graph implementation rather than the matrix-based one. (Why does that 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.

Here is one possible way to find a collection of maximal independent sets from the graph: represent each slot by some sort of a list (or, better yet, a binary search tree—why?). To find a maximal independent set for a slot, pick any vertex of the graph and add it to the list. Cycle through all other vertices of the graph. If a vertex is not connected to any of the vertices already in the slot, throw it in. Continue until you have tried all vertices. Now delete all vertices that you added to the slot from the graph[2]. Fill successive slots in the same way until there are no vertices left in the graph.

Extensions

For full credit on this lab, please complete at least one interesting extension to the program. We have listed a few examples 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 extra credit.

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 are offered this semester).
Print out a final exam schedule for each student, listing students in alphabetical order.
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 solution found in a given run.
Use the Permute.java class to try the greedy algorithm with every permutation of vertices. As we discussed, one of these permutations is guaranteed to minimize the number of exam slots. This means that by trying every permutation, you can find the best solution. This method will only work in a reasonable amount of time on small graphs.
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.

Feel free to add other features as well. Be sure sure to indicate in the heading of your program (in comments) what extras you have included.

Lab Deliverables

Please complete and submit the following items in your repository:

Your well-documented source code for all Java files that you write.
The file README.md with the lab description and a list of your collaborators for this lab.

Submitting Your Lab

As you complete various milestones, 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 include "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 GitHub
Verify your changes on Github. Navigate in your web browser to your team's private repository on GitHub. It should be available at:
```
https://github.com/williams-cs/cs136f19_lab10_exam_scheduling-{USERNAME1-USERNAME2}
```
You should see all changes reflected in the various files that you submit. If not, go back and make sure you 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. Our goal is to grade the programs anonymously to avoid any bias. However, 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 "I am the sole author of the work in this repository." in the comments at the top 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?