Class Scheduling Project
Submission Type: Video OR Handout OR Poster OR Slide Deck.
Group Size: You may work individually or in a group of up to 3 people.
Problem: In this project, you will try your hand at the job of the registrar’s office. There
are 7 classes you are trying to schedule (listed below) and you want to make sure you and
your three friends can all take the classes they want to take. You must decide which classes
should be offered at which time slots so that you are minimizing the number of time
slots used but everyone can take every class they want to take.
The classes are:
• GEOG 1200
• LING 1010
• CAMS 1103
• FREN 1171
• ENGL 1107
• WGSS 1104
• NRE 1235E
Some assumptions:
- 1. There are four students. Each student takes three of these classes in one semester.
2. No two students should take the same three classes.
3. Each class must be chosen by at least one person.
4. Each class will only be offered once.
5. A student cannot be enrolled in two classes that meet at the same time. - Part 1: Explain in general how you can use graph coloring to solve this type of problem.
Part 2: Decide which three classes each of the 4 people want to take.
Part 3: Create a graph to represent the problem. You should include an explanation on how
the graph was made, including what each vertex represents, and what each edge represents
in the context of the problem.
1Part 4: Color the graph using the least number of colors possible. Explain how you know
you know you need at least that many colors, and also how you know you do not need
more colors. Your submission should include the colored graph and what each of the colors
represents.
Part 5: Choose specific days and times for each class to be offered within UConn’s timeblocks - https://scheduling.uconn.edu/standard-meeting-times/. Assume each class meets inperson either MWF for 50 minutes or TuTh for 75 minutes. You should choose meeting times
to give everyone a “nice” schedule. It is up to you to decide what a nice schedule is. For
example, if you decided that you need 5 timeblocks, you might want to pick timeblocks so
no one has an 8AM class or so that some people only have TuTh classes while other people
only have MWF classes. Or maybe some people prefer morning classes and other people
prefer afternoon classes – your call! - Remember: You must show all work in order to receive full credit!