## Programming Assignment 1

Assigned: Jan. 25.

Due: Feb. 15.
#### Assignment

Write a program that solves the scheduling problem described in
Problem Set 1,
using the following algorithm:
- In the first stage of search,
use a breadth-first search through the state space of Problem set 1,
problem 2 until the queue of frontier states has reached a specified
maximum.
- In the second stage of search, use iterative deepening starting
from the frontier created in the first stage.

#### Input

The input to your code should be a plain text file of the following format:
**First Line:** The number of tasks, the target value, the deadline, and the
maximum size of the queue

**Next N lines:** Each line is a triple TaskId, Value, Time Requirement
separated by white space. The TaskId is a number between 0 and N-1.

**Remainder** The remainder of the file is an encoding of the prerequisite
DAG. It is a sequence of lines of the form X Y meaning that X is a
prerequisite for Y.

For example, the example in Problem set 1 would be input as follows:

5 7 10 3
0 3 2
1 1 5
2 2 5
3 2 2
4 6 4
0 3
1 4
2 4

You may assume that the input is correctly formatted and that the arcs
describe a DAG. You do not have to do error handling for incorrect inputs.

#### Output

The output should either have the form

List of tasks, total value, total time

or 0 if there is no solution.
For example the output for the above example would be
[0,2,4] 7 9

#### Experimentation

You should create a driver for the program that takes a single argument,
N, the number of tasks, and E, the number of experiments; creates E random
examples each of size N; runs the search code; and then does some statistics
on the results.
You can create a random example as follows:

- Create N tasks.
- Assign values and time randomly uniformly between 0 and N.
- Choose the target value and the deadline randomly between
N
^{2}(1 - 2/sqrt(N))/4 and
N^{2}(1 + 2/sqrt(N))/4
- Create a random DAG as follows:
P = [1,2, ... N]
for (I=1 to N) { /* Construct a random permutation */
J = a random value between I and N;
swap(P[I],P[J])
}
for (I=1 to N-1)
for (J = I+1 to N)
with probability 1/2 create an arc from P[I] to P[J];
sort the arcs lexicographically;

You may either write the example to a text file and use that as input
to your search program, or directly call the top-level function
of the search program.
Test your program with increasing values of N and with E = 1000, up to the
point where the running time becomes impossible. For each value of N,
record

- The fraction of examples where a solution exists.
- The maximum, minimum, and average number of states created in the
search process.
- Any other statistics that interest you.

#### Coding

Programs will be accepted in C, C++, Java, Scheme, Perl, or Python.
If you wish to write programs in other languages, you should discuss
that with the TA; I leave that decision entirely up to his/her discretion.
Programs must run on the department Sun system; you should check this
before you submit your code.
####
Submit

The source code; a README file explaining
how to compile and run your code; and a short summary of your experimental
results.
#### Grading

Grading: 8 points for correctly running code. 2 points for well-written
code. A programming assignment count equally with a problem set in computing
the overall grade.

####
Late policy

Programming assignments are
due at the beginning of class on the due date. I will
accept assignments late with a penalty of 1 point out of 10 for each week late
(fractions of a week are rounded up.)