Description
2 Programming Part (70 points)
Many businesses need to schedule workers for shifts. The
worker scheduling problem (which includes times of shifts,
number of employees per shift, workers’ availability and so
on) could be quite complex. We are going to investigate a
similar but simpler scheduling problem that you are familiar
with. During course registration each semester, students need
to select courses that do not have a time conflict with each
other. Students usually have a set of candidate courses and
each course might have multiple sections (at different times).
The goal of this assignment is to automate part of the student course scheduling process. That is, you can save time in
course scheduling in the future (Yeah!). Given a set of candidate courses and their time slots (sections), we would like the
largest subset of courses that do not have a time conflict. Also,
a student can specify the preference order of candidate courses
and time slots (sections) for each course. If two courses are
in the same time slot, the course with a higher preference
is considered first. If a course has multiple time slots, the
time slot with a higher preference is considered earlier. That
is, we would like to find the “best” schedule that has the
largest number of courses (first priority) with the most preferred courses (second priority) and time slots (third priority).
Design a “brute-force” algorithm that recursively enumerates all possible schedules and find the “best” schedule. For
simplicity, all courses are in standard time slots—MWF on
the hour or TR every 1.5 hours starting at 0800 (and ending
before 1700), MW or TR every 1.5 hours starting at 1700 (and
ending before 2130). That is, the time slots do not overlap.
Suggestion/hint: consider the correctness of your algorithm
before its efficiency. Sample input and sample output are on
the course website.
We will evaluate your submissions on code01.fit.edu so
we strongly recommend you to test your programs on
code01.fit.edu. To preserve invisible characters, we strongly
recommend you to download, NOT copy and paste, input
data files.
Input (from a file): The command-line argument for
hw2.c is the name of the input file. Each line has the course
number and its time slots (sections). The candidate courses
are ordered according to the student’s preference. If a course
has multiple time slots (sections), they are ordered according
to the student’s preference. For example:
CSE4301 MWF0900
MTH2001 MWF0900 MWF1500
PHY1001 MWF1500
COM2223 MWF1100 TR0930 TR1530 MWF1000
Output (to the screen): Course schedule with the course
number and its time slot on each line (same ordering as input, ie, student’s preference). The course schedule is followed
by courses with a time conflict and their time slots (same
ordering as input, ie, student’s preference) or “None”. For
example,
—Course schedule—
CSE4301 MWF0900
MTH2001 MWF1500
COM2223 MWF1100
—Courses with a time conflict—
PHY1001 MWF1500
Extra Credit (10 points): Separate submission via
hw2extra.c. Solve the problem without recursion (or using
a stack to simulate recursion).
1
3 Submission
Submit hw2.c that has the main method and other program
files. Submissions for Individual and GroupHelp have the
same guidelines as HW1.
Submit the written part in PDF format to the Submit
Server. Hardcopy is also acceptable in the lab. GroupHelp
submission is not applicable to the written part.
Note the late penalty on the syllabus if you submit after
the due date and time as specified at the top.
For extra credit, submit hw2Extra.c that has the main
method and other program files. GroupHelp submission is not
applicable to extra credit. Late submission for extra credit is
not accepted.
2