Description
Solving a Scheduling Problem with DFS
Your task this week is to write an LC-3 program that
attempts to find a compatible combination of times at
which events can be inserted into an existing weekly
schedule. Given a list of extra events, each of which can
occur at one or more hours, your program must use a stack
to perform a depth-first search (DFS) of possible time
combinations until a compatible combination is discovered
(or until all possible combinations are eliminated as
incompatible). Your program must extend your solution
for MP2, and requires roughly another 130 lines of LC-3
assembly code.
The objective for this week is to give you additional experience with understanding and manipulating arrays
of data in memory, and particularly in developing and using a stack.
The Task
In this program, you must try to fit a set of extra events into an existing schedule. Each extra event can be
inserted at some number of possible hours, and your program must try to find a way to insert all of the
events (each at one of the times allowed for that event) such that no events conflict with each other or with
the predefined schedule (the output of your MP2 code’s translation step). If no compatible combination of
times is possible for the extra events, your program must print an error message and terminate without
printing the schedule. If a compatible combination is found, your program should print the final schedule,
with all extra events inserted at appropriate times.
Start by making a copy of your MP2 program. You should insert the new code for this MP between the
schedule translation code and the schedule printing code from MP2. You may find it useful to wrap up the
MP2 work as subroutines before you begin writing new code. In particular, you may want to have a
subroutine for clearing the schedule, a second subroutine for performing the translation, and a third
subroutine for printing the schedule. The code for MP3 can then be written as a fourth subroutine. We
suggest that you return 0 or 1 in some register to indicate failure or success of the subroutines for translating
the schedule and for inserting the extra events (the MP3 code). The main program can then check the value
returned and handle it appropriately.
The extra event list starts at address x6000 in LC-3 memory. Each extra event consists of three fields. The
first field is a string pointer—the address of a string describing the event. The second field is a bit vector
of days for the event: Monday is bit 0 (value 1), Tuesday is bit 1 (value 2), and so forth, through Friday
(bit 4, value 16). The days on which the event occurs are OR’d together to produce the bit vector. The
third field is a bit vector of hour slots for the event: 07:00 is bit 0 (value 1), 0:800 is bit 1 (value 2), and so
forth, through 22:00 (bit 15, value x8000). The hours in which the event can appear in the schedule are
OR’d together to produce the bit vector.
The event list ends with a NULL (x0000) string pointer.
Notice that there are two differences between the events provided in MP2 and the extra events. First, the
string is NOT part of the event, but has been replaced with a pointer to a string. Having written MP2, you
know how to handle strings already.
Also, the single hour slot is now a bit vector of possible hours. In this MP, you must determine which
combination of hours (chosen from the possible hours in each extra event’s bit vector) for each event
produces a compatible schedule, in which no two events conflict with one another. Your code must prefer
early hours to late hours, so you should start by checking bit 0, then bit 1, then bit 2, and so forth. (It’s
much more difficult to test in other orders with LC-3, and allowing other orders makes grading more
difficult.)
To explore the space of possible combinations, your program must make use of a stack and perform a depthfirst search (DFS). In the path-finding problem in class, we used a queue and performed a breadth-first
search (BFS). In that case, nodes in the graph were explored in the order that they were added to the queue:
first-in, first-out (FIFO). In contrast, as your program adds new events to the stack, it will then explore
those events before expanding any previous events. In other words, your code works in a last-in, first-out
(LIFO) order.
At first, the stack will be empty. Your program should take the first event from the extra event list and
push it onto the stack using a structure that you design, then choose an hour from among the possible hours
for that event, and try to insert the event into the schedule. If successful, your code should continue with
the next event. If at any point, your program manages to find hours for all events in the extra event list, a
compatible schedule has been found, and your code can proceed with printing (the stack can be discarded—
no need to clean it up).
If your program finds that an event on top of the stack has conflicts for every possible hour, that event must
be popped from the stack. After popping an event structure, your program should then remove the event
on top of the stack from the hour at which it was previously inserted into the schedule and try to find an
alternative possible hour for that event (remember that the impossible event has been popped). If your
program finds the stack empty when it tries to pop an incompatible event, no compatible combination of
the extra events exists, and your program must stop exploring and print an error message, then terminate.
You must decide what information to include in the event structures your stack. Whatever you decide, be
sure to add comments describing how events appear on your stack in your code. You may want to keep a
copy of the design nearby as you write your code (on paper, for example).
You may want to consider the following questions as you design the structure of events on your stack. Does
the “first” (smallest) 1 bit of an event on the stack represent the hour slot currently occupied by the event,
or the next slot to be tested if remaining events cannot fit into the schedule? Also, does your event structure
include the current hour slot for the event (call it S) and/or the current bit for that slot (1<<S)?
You may choose to make use of the data in the extra event list directly for your stack, in which case your
stack will grow towards larger memory addresses instead of smaller ones. However, you may not modify
the extra event list, so you must copy it before using it as a stack (since your program must use the stack to
keep track of possible hours for each of the extra events).
If you create your own stack (the simpler approach, we think), we suggest using x8000 as the base, as
checks for an empty stack are then slightly easier to perform.
Here is an example (provided to you as short.asm and inserted into the simple.asm schedule from MP2
in the figure to the right) of how an extra event list might appear in memory and how the schedule produced
by your program should appear after finding and printing a compatible schedule. The data shown list only
two extra events starting at x6000 and x6003. The NULL at x6006 marks the end of the list.
address contents Meaning
x6000 x6007 points to “x1”
x6001 x0015 Mon (1) | Wed (4) | Fri (16)
x6002 x0144 09:00 | 13:00 | 15:00
x6003 x600A points to “x2”
x6004 x0007 Mon (1) | Tue (2) | Wed (4)
x6005 x0444 09:00 | 13:00 | 17:00
x6006 x0000 NULL (ends list)
x6007 x0078 ‘x’
x6008 x0031 ‘1’
x6009 x0000 NUL
x600A x0078 ‘x’
x600B x0032 ‘2’
x600C x0000 NUL
Specifics
Your code must be written in LC-3 assembly language and must be contained in a single file called
mp3.asm. We will not grade files with any other name.
Your program must start at x3000.
Your program must perform all tasks from MP2 correctly.
Your program must attempt to find a compatible combination of times in the schedule at x4000 in
memory for all events in the extra event list starting at x6000 in memory.
o Each event in the extra event list consists of a pointer to a string, a bit vector of days of the
week (Monday = 1, Tuesday = 2, Wednesday = 4, Thursday = 8, Friday = 16), and bit
vector of possible hours (07:00 = 1, … , 15 = x8000).
o A NULL pointer (x0000) ends the event list (the final entry is not considered an event, and
no bit vector of days nor possible hours are included after the NULL).
o You may assume that all extra event string pointers point to valid and unique ASCII strings.
The assumption of uniqueness makes it slightly easier to remove conflicts that are partially
written into the schedule, as otherwise an event’s name may match that of another event.
Be sure that you do not create tests that break this assumption (and thus spend time
‘debugging’ your code for no reason).
o You may assume that all bit vectors of days are valid combinations representing (possibly
empty) subsets of weekdays (Monday through Friday).
o You may assume that all bit vectors of hours are valid combinations representing (possibly
empty) subsets of hour slots (07:00 through 22:00).
o Your program must make use of a stack and a DFS to explore the possible combinations
of hours. Earlier hours must be considered first. For example, if an event can occur at
07:00 or at 08:00, and both hours are compatible with all other events, 07:00 must be
chosen for that event.
o The DFS must explore events in the order in which they appear in the event list. The first
extra event must be added to the stack first, then the second, and so forth.
o Your program must make not modify the extra event list in any way.
If a compatible combination of hours for events in the extra event list is found, your program must
print the schedule with the extra events included at the chosen time for each event on the days on
which the event occurs.
If no compatible combination exists for all events in the extra event list, your program must print
the message, “Could not fit all events into schedule.\n” and terminate without printing a schedule.
Your code must be well-commented, and must include a table describing how registers are used
within each part of the code. Follow the style of examples provided to you in class and in the
textbook.
Do not leave any additional code in your program when you submit it for grading.
Testing
We strongly suggest that you make use of pencil and paper when developing your code. You are likely to
run short on registers and need to use some LC-3 registers for multiple purposes. Be sure to keep track of
the meaning of each register for each part of the code (write the meanings into comments!).
Be sure that you remove any conflicting events correctly. In MP2, when you found a conflict, you could
just leave any instances of the conflicting event (on non-conflicting days earlier in the week) in the schedule.
For this MP, you must remove such instances. Similarly, when you remove an event from the stack, your
program must remove all instances of that event from the hour slot in which it was previously scheduled.
You may want to work through a small example on paper and think about when and why your code should
push a new event structure onto the stack as well as when and why your code should pop an event structure
from the stack.
Several tests have been provided to you along with samples of original schedule data and extra events. The
tests provided are likely to help you find bugs, but remember that testing your program is your
responsibility. Duplicating the results provided with the given tests does not guarantee that your program
contains no errors.
Grading Rubric
Functionality (70%)
15% – program handles extra event lists with no schedule conflicts (in which all extra events can
occur at their earliest possible hour)
20% – program handles extra event lists with no backtracking (in which all extra events can occur
at the earlier possible hour that does not conflict with the starting schedule, nor with earlier extra
events)
30% – program handles backtracking correctly (extra events lists that require popping events from
stack to explore alternative hours for events already on the stack)
5% – program correctly identifies cases in which no compatible combination of extra events
exists, and outputs the correct message in such cases.
Comments, Clarity, and Write-up (30%)
5% – a paragraph appears at the top of the program explaining what it does (this is given to you;
you just need to document your work)
5% – event structure used on the stack is defined clearly in the code
10% – register use is well-documented in the code (register tables and/or additional comments as
necessary)
10% – code is clear and well-commented
Note that some categories in the rubric may depend on other categories and/or criteria. For example, if
your code does not assemble, you will receive no functionality points. Similarly, if MP2 code is not
working, you are likely to lose lots of points. Finally, if you violate constraints (for example, changing the
extra event list data, or not using a stack), the penalty will be substantial (half or all of the points).
