ECE220: Computer Systems & Programming Fall 2022
Machine Problem 3
due: Monday 17 October, 11:59:59 p.m. 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.
Copyright By PowCoder代写 加微信 powcoder
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.
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). Each event can only be assigned to a single hour slot, but may occur on multiple days at the same time. 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), 08:00 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. Your task is to assign one hour to each event.
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 depth- first 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<