Introduction.
In this homework, you will think about a scheduling problem, implement two simple greedy algorithms for it, and analyze the algorithms with respect to their correctness and running time.

Devising a proper schedule satisfying a bunch of constraints and minimizing some measure of cost (or maximizing some measure of profit) is fundamental problem for many industries and organizations. For example, every semester the university assigns courses to classrooms and slots in the day, while aiming to satisfy a bunch of constraints including "no two courses should be assigned to the same classroom at the same time." Presumably, the university solves this scheduling problem with one of its aims being: maximize the number of courses that can be offered in each semester. Scheduling airline flights, scheduling FexEx dropoffs and pickups, scheduling the restocking of items in a WalMart store, scheduling "jobs" on an assembly line in a car manufacturing plant, etc., are all examples of complicated scheduling problems that companies routinely "solve."

Consider the following "toy" scheduling problem. You own a resource --- it may be a conference room, a supercomputer, or an electron microscope --- and many people request to use the resource for periods of time. A request takes the form: can I reserve the resource starting at time s and ending at time f? In other words, each request is an interval [ s, f]. Your goal is to accept a subset of the requests, rejecting all others, so that the accepted requests do not overlap in time. Assume that you get paid a fixed amount (say $1000) for each request you accept. Therefore, the goal is to maximize the number of requests accepted, thereby maximizing your profit.

Example: Suppose that the set of requests are:

	[9:00, 12:00], [9:30, 10:30], [10:00, 11:00], [10:30, 13:00], [14:00, 16:00], [13:30,14:00], [9:00, 15:00]

        [9:30, 10:30], [10:30, 13:00], [13:30,14:00], [14:00, 16:00]

Greedy Algorithms.
I will describe two greedy algorithms for the above problem. An algorithm is greedy, if it builds up a solution in small steps, making a choice that seems best at each step. Taking this "short-sighted" view and trying to as best as possible at each step and hoping that this will yield a good solution in the long run is what makes these algorithms "greedy." Typically, greedy algorithms will yield a solution that satisfies the constraints of the problem, but may not always be optimal. Here is pseudocode for the two algorithms. Both algorithms take a set I of intervals that correspond to requests, and return a subset S of non-overlapping requests. The span of an interval [s, f] is simply its length, i.e., f - s. Let I be a set of intervals and let x be an interval in I. The degree of x with respect to I is the number of other intervals in I that x overlaps with. The GREEDY_SPAN algorithm greedily picks an available interval with smallest span, whereas the GREEDY_DEGREE algorithm greedily picks an available interval with smallest degree.

	GREEDY_SPAN(I)
		Initialize S to be the empty set
			
		while(I is not empty):
			Pick from I an interval x with smallest span (ties are broken arbitrarily)
			Add x to S
			Delete from I all intervals that overlap with x

		return S

	GREEDY_DEGREE(I)
		Initialize S to be the empty set
			
		while(I is not empty):
			Pick from I an interval x that has smallest degree with respect to I (ties are broken arbitrarily)
			Add x to S
			Delete from I all intervals that overlap with x

		return S

Things you should do.

1. Pen and paper exercise. Explain in 1-2 sentences my motivation in making the greedy choice of an interval with smallest span in the GREEDY_SPAN algorithm. Similarly, explain my motivation for the greedy choice in the GREEDY_DEGREE algorithm, as well.
2. Pen and paper exercise. The GREEDY_SPAN algorithm is correct in one sense --- it returns a set of intervals no two of which overlap. However, the algorithm is not correct in another sense --- it does not always return an optimal solution. Construct a small example of requests for which, the GREEDY_SPAN algorithm does not return an optimal solution. Clearly, show (i) the solution returned by the GREEDY_SPAN algorithm and (ii) a larger solution. The existence of a larger solution is proof that GREEDY_SPAN does not always yield an optimal solution.
3. Pen and paper exercise. The GREEDY_DEGREE algorithm also suffers from the same problem as the GREEDY_SPAN algorithm. Repeat the exercise that you did above for GREEDY_SPAN, for the GREEDY_DEGREE algorithm.
4. Python implementation. Implement two Python functions, one corresponding to each of the two algorithms, GREEDY_SPAN and GREEDY_DEGREE described above. Each of these functions should take a single argument, a list I of intervals, where each interval is itself a size-2 list, specifying the start and end times of the intervals. You should assume that the start and end times of intervals are real numbers. The functions should return the solution as a list of intervals. I implemented these functions, calling them greedySpan and greedyDegree. Here is an example showing how I defined a set I of intervals corresponding to the example earlier in this handout and ran the two functions on this set of intervals.

   	>>> I = [[9,15], [9,12], [9.5, 10.5], [10,11], [10.5, 13], [13.5,14], [14,16]]
   	>>> greedySpan(I)
   	[[13.5, 14], [9.5, 10.5], [14, 16], [10.5, 13]]
   	>>> I = [[9,15], [9,12], [9.5, 10.5], [10,11], [10.5, 13], [13.5,14], [14,16]]
   	>>> greedyDegree(I)
   	[[13.5, 14], [14, 16], [9.5, 10.5], [10.5, 13]]
   

What to submit.
You are required to submit 3 files in a zipped directory (hw8.zip). The files are:

• hw8.py, a file containing your Python program. Make sure that your program is clearly commented.
• README file, describing (as usual) the status of your program (e.g., does it compile? if it does, does it work correctly? if not, under what circumstances does it break down? how long does it take to run? etc.).
• greedy.doc or greedy.pdf, a word document or a pdf document containing answers to the three "pen and paper" exercises listed above.