Programming Assignment 1

Assigned: Jan. 25.
Due: Feb. 15.


Write a program that solves the scheduling problem described in Problem Set 1, using the following algorithm:


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.


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


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:

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


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.


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


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.)