1) Write a program in your favorite High-Level language to implement the greedy activity-selection problem.  You should input the number of activities, the start and finish times of each activity, then sort the activities, and choose the activities greedily by finishing time.

2)Suppose we modify the activity selection problem to allow requests for the conference room to come with bribes (or, if you're more moral, “priorities”).  Our goal now is to maximize our total bribe (or priority) income.  This might mean we DON'T schedule the largest number of activities.  

Instead of maximizing the number of activities, you're maximizing the total bribes paid by each activity that gets scheduled.

This is a Dynamic Programming problem, and I think your recurrence should look like this:

Profit(i,j) = total profit made by scheduling tasks i to the end, if task j was the last task scheduled.  THE TASKS ARE SORTED BY FINISH TIME (obviously when you write the program, you should do this first)

= 0 if i > n  (out of tasks)

= Profit(i+1,j) if i's starting time is before j's finish time.  (It's impossible to schedule i, move on to the next feasible task if there is one)

= ??? (this is the recursive part for you to do) otherwise

You should write this recursively, and it will most likely take exponential time (don't do memoization yet)

3) Modify your  Dynamic Programming solution above to either calculate the profit using memoization or using the bottom-up method described in class.  This new version should be O(N^3) or faster.