Consider a group of n robots, numbered R2D1 through R2Dn, and m tasks, numbered 1 through m. Tasks can be different and robots are specialized, hence a given robot can only perform certain tasks. This information is provided as part of the input specification: For each robot, you are given a list of all tasks that robot is capable of performing. This project is about getting as many tasks done in a given amount of time by this collection of specialized robots. For all three parts, assume that each task takes one day to perform from start to finish, and once a robot starts working on a task, it completes that task before starting on another task. Also the robots cannot multi-task, i.e. they cannot work on two or more tasks at the same time. For parts 1 and 2, also assume that there are no dependencies among tasks (this makes your life a lot easier!), i.e. any subset of tasks can be worked on concurrently by qualified robots.

1. (a) Suppose your goal is to maximize the number of tasks that can be completed in a single day. Formulate this problem in such a way that one of the graph algorithms covered in class can be applied to solve it.

(b) Write code to solve this problem. Your code should output the maximum number of tasks you can complete in one day, as well as one set of robot-task pairings that will achieve this result. See the coding instructions for more information on writing your code.

2. (a) Suppose your goal is now to minimize the number of days taken to complete all tasks. One way to address this is to apply the solution for 1(a) above to pending tasks at the end of every day. Thus, you do as many tasks as you can on day 1; on day 2, apply the same algorithm but on a reduced" input, where tasks already completed are removed, and so on till all tasks are done. This approach has a greedy flavour to it. Show with the aid of a counter-example that this approach may not always lead to the optimal solution (or prove that it always provides an optimal solution).

(b) Since the problem above seems to be difficult, you instead set an objective of doing as many tasks as possible in a specified number of days, d. Describe how you can conceptually find an optimal solution to this problem. Show the correctness of your algorithm, i.e., argue that the solution will indeed be optimal.

(c) Write code to implement your solution to 2(b) above. You can reuse any code developed for earlier parts of this project. Your code should output the maximum number of tasks you can complete in d days, as well as one set of robot-task pairings for each day that will achieve this result. Hint: Observe that there are only 5 points for this section. That suggests that if you have the code working for problem 1, this would not be much more e ort if you did have a suitable formulation for this problem! Despite this hint, if you were not able to get a suitable formulation for 2(b), then you can do 2(c) by using the approach of 2(a). This is not the desirable option: You will only get half-credit for 2(c) if you do so, but that is better than nothing.

Suppose now that your tasks may have dependencies among themselves. These dependencies are specified by an m*m adjacency matrix A, where a _i,j = 1 if task i needs to be completed before task j can be started, and is zero if task j is not directly dependent on task i. Suggest a reasonably efficient way of trying to finish all the tasks in as few days as you can, that builds upon your solutions to the earlier problems. Argue whether your procedure is provably optimal, or just a very good heuristic. No need to write code.

Coding Instructions

1. You can code in C/C++, Java, or Python. You can use the standard library of whatever language you code in but no other "ready made" code. A part of this project is to get you to implement some of the algorithms that you have seen in class.
2. Make sure that your code compiles and runs on an LRC machine.
3. You can use the sample problem specification on Blackboard to test and debug you code. The problem specification consists of three plain text files:

- A robot capabilities le for problems 1(b) and 2(c), the first line of this le specifies n and m as two comma separated numbers. For example, if the first line reads 10; 20, then there are n = 10 robots and m = 20 tasks. All other lines of this le specify a robot and the tasks that robot is capable of performing as a comma separated list. For example, if a line reads 10; 1; 2; 3, then robot 10 is capable of performing tasks 1, 2, and 3. There will be n + 1 lines in this file.

- A task dependencies le for problem 4(c). Each line of this le specifies a dependency between a pair of tasks as two comma separated numbers. For example, if a line reads 1; 2, then task 1 needs to be completed before task 2 can be started. There will be as many lines in this le as there are edges in the dependency graph.

- A task times le for problem 4(c). This le lists the completion times of each task as a comma separated list. For example, if the le reads 2; 4; 6; : : : , then task 1 takes 2 days to complete, task 2 takes 4 days to complete, task 3 takes 6 days to complete, and so on. There will be just one line in this le.

1. The executable compiled from your code will be called with the le names (that includes the full le path) of these three les as its arguments. The order of these arguments will be the same as the one above. You should print your results to standard out.
2. Your code will be tested on a different problem specification that will follow the same file formats as the sample specification.