Project 1: Activity Scheduling

Due: Tuesday, February 23, 2016 by 9:00PM

Addendum

An additional test program proj1test.cpp has been posted. Put this file in the same directory as sched.cpp and compile just proj1test.cpp. On GL, just type: g++ proj1test.cpp When you run the program, the output should look like this: proj1test-outupt.txt.

We are releasing this test program because we have noticed that the you are not testing your code even though we have said that you need to test you code. Here's what it means to test your code:

Use new data with different sizes.
Check that your sort function actually sorts. You should have printed out the events in end time order after sorting and check it either visually or with a short piece of code, preferrably both.
After scheduling, check that the output is correct. In this case, the data was arranged so that "Event A", ..., "Event G" are the scheduled events.

This is code you should have written yourself to test your program. We expect you to do this for all the projects.

You should NOT just run this program and say "Great, I'm done!" You should make new data to go into proj1test.cpp to further test your code. If all you do is run proj1test.cpp unmodified, you have once again failed to understand that it is your responsibility to test your own code.

We will not do this again for future projects in this class.

Objective

In this project, you will demonstrate your ability to apply basic C/C++ syntax, user-defined functions, and arrays to implement a solution to a room scheduling problem.

Background

Suppose we are in charge of scheduling events in a lecture hall. For any given day, we have a list of event requests, which include the events' start times, end times, and descriptions. Our goal is to schedule as many events as possible. This is known as the activity-selection problem. For example, suppose we have three requests for ITE 102:

0800 – 1600 Algorithms Workshop
1000 – 1130 Spanish 101
1100 – 1300 Big Cheddar Fussball Camp
1400 – 1600 Study Group

It is easy to see that we can schedule at most two events, and that there are two different ways to achieve this:

Spanish 101 and Study Group
Big Cheddar Fussball Camp and Study Group

We only care that we schedule as many events as possible, so either of these two options is acceptable. We will say a schedule is optimal if it includes the maximum number of events. This example shows that there may be multiple optimal solutions.

It turns out that there is an efficient algorithm for finding optimal solutions to the activity-selection problem. Here is an outline of the algorithm:

Sort the events in ascending order by end time.
Schedule the first event on the sorted list; remove the event scheduled and all events that start before the scheduled event ends.
Repeat the previous step until there are no more events to schedule.

We can apply this algorithm to the example given above. First, we sort the events by end time:

1000 – 1130 Spanish 101
1100 – 1300 Big Cheddar Fussball Camp
0800 – 1600 Algorithms Workshop
1400 – 1600 Study Group

We schedule the event Spanish 101 since it has the earliest end time. Next, we remove Spanish 101, Big Cheddar Fussball Camp, and Algorithms Workshop from the list. This leaves only Study Group, which we add to the schedule. Since there are no more event requests, we are done. The resulting schedule is:

1000 – 1130 Spanish 101
1400 – 1600 Study Group

Assignment

Your assignment is to write three functions necessary to complete an activity-scheduling program. The main() function, function prototypes, and one set of test data are provided in two files:

sched.h — event data.
sched.cpp — function prototypes and main() function.

On GL, these files can be copied from Prof. Marron's shared directory: /afs/umbc.edu/users/c/m/cmarron/pub/cmsc202 You may not modify the provided function prototypes or main() function. You will write the function implementations; they must be written in sched.cpp following the main() function.

The event data is provided in the header file sched.h. You should not modify the data in the provided header file, but you may create other header files to test your program with other event lists. To compile the program using event data in a different header file, you will need to change the line #include "sched.h" in sched.cpp to reference the new header file.

The number of events is given by the constant NUM_EVENTS, and the event data is given in three arrays:

float startTime[NUM_EVENTS] — array of event start times given as floating point numbers, e.g. 12:30 is represented by the floating point value 12.5 (12th hour and .5*60 = 30 minutes).
float endTime[NUM_EVENTS] — array of event end times given as floating point numbers.
string description[NUM_EVENTS] — array of event description strings.

The three functions you must implement are sort(), sched(), and printEvent():

sort() — a function to sort a floats array data[], creating an array of sorted indices. The sort() function does not sort the data, but fills the the array indx[] so that are the values of data[] in ascending order.
sched() — a function that implements the scheduling algorithm given arrays of start times, end times, and the indx[] array created by sort(). The function returns the number of events scheduled and fills the array scheduled[] so that are the scheduled events in order of increasing end time.
printEvent() — a function that "pretty-prints" an event to the console. Times should be printed in hh:mm format, rather than as decimal numbers. For example, the event Spanish 101, starting at 10.0 and ending at 11.5 should print as

See the function prototypes and comments in sched.cpp for more information.

Implementation Issues

Here are some issues to consider and pitfalls to avoid.

Note: do not develop your programs in the submission directories. Develop your programs in some other location in GL or on your own computer. The files that you have in the submission directory should not be your only copy of your code.
You may not use the vector class in this project. You will have points deducted if you use vectors instead of arrays.
On some compilers, to use the string class you must have:
You can compile your program with the command

Sample Output

With the data provided in sched.h, your program should schedule five events:

linux2[1]% ./sched 
07:30 - 08:30 Breakfast Club 
10:30 - 12:30 Teaching Workshop 
14:00 - 14:45 Big Cheddar Fussball Camp 
16:00 - 17:00 Delta Tau Chi 
17:00 - 18:00 Dead Poets Society

Submitting your program

You should submit these files to the proj1 subdirectory:

sched.h — should be unchanged.
sched.cpp — should included your implementations of the required functions.

If you followed the directions in setting up shared directories, then you can copy your code to the submission directory with: cp sched.h sched.cpp ~/cs202proj/proj1/

You can check that your program compiles and runs in the proj1 directory, but please clean up any .o and executable files. Again, do not develop your code in this directory and you should not have the only copy of your program here.

CMSC 202 — Spring 2016 — Prof. Marron