Assignment #1

CS 156
due September 24, 2009
100 points + 20 points extra credit

Be sure you have read the handouts entitled Assignments and Documentation and Style in Java before submitting your solution to this assignment.

 

Use the version of the A* algorithm available on the class web site to solve some or all of the 7 problems described below. Test with the test class A1.java available from that site. This assignment is to be done in Java (version 5.0 or later).

To solve a problem using my version of the A* algorithm, you will need to define a class that extends the abstract class State (which is also available on the web site). Your class will also need an appropriate constructor. And since the answer to the problem is to be clear by looking at the solution state, your class will need a version of the toString method that is more informative than the one that is inherited from the Object class. The arguments that each constructor needs should be clear from the description below of the corresponding problem; you may also look at the test class A1.java to double check. This test class also gives the class names (and thus the constructor names) that you are to use.

Each problem is worth up to 40 points; for your overall grade for this assignment I will add the 3 highest grades for individual problems. However the grading scale will assume a maxmium of 100 points for the assignment. Thus you can get full credit (plus up to 20 points of extra credit) by doing only 3 problems. There is unlikely to be extra credit available on later assignments or tests.

The only illegal arguments you need to check for are null arguments to class constructors. You should assume that these arguments represent empty data structures (or graphs with 1 vertex and 0 edges). If you check for other illegal arugments, I may allow this extra work to offset other deductions that I make for that problem, but in no case will you get more than 40 points per problem.

For each problem, you should assume that the state space takes the form of a tree. You needn't worry about the the version of the A* algorithm that assumes a more general state space, or about making your estimator monotonic. Recall that the A* algorithm is not guaranteed to work correctly for an optimization problem unless the estimator has the properties given in the documentation for the State.findEstimate method. In particular the estimator must be optimistic. In some cases you may need extra documentation to make clear that this is true.

For the given problems I am primarly concerned that you can use the A* algorithm. I am less concerned about having the most efficient possible implementation, so I will deduct for inefficiency only in the case of gross inefficiency. In fact, for some of the problems, no efficient solution is known. Some of the problems may have asymptotically better solution algorithms that do not involve the A* algorithm. In this case you should NOT use these particular algorithms. You are to use the A* algorithm in every case.

If you do not solve all 7 problems, or if some test cases don't work for the problems that you do solve, feel free to comment out the corresponding code for the test class A1.java, or to replace the given test cases by others. Of course, you can expect a deduction for a problem if you cannot handle all of its given test cases. It's also possible that you will receive a deduction if you can handle all of the given test cases, but cannot handle all possible instances of a problem. Finally, note that for some problems, it's possible that a more efficient representation or estimator will allow the solution of more instances in a reasonable time than a less efficient representation will.

As for every assignment this semester, any of your Java classes may have extra methods or instance fields in addition to those that are required by the assignment.

You are to turn in both hard and soft copies of all of your code (but turn in only the soft copy of A1.java, and only if you modify it) as well as a hard copy of the results of your testing.

Finally, here are the 7 problems that you may attempt:

SCHEDULING WITH DEADLINES AND PENALTIES
Given a set of n tasks, each of which has an integer length, an integer deadline, and takes 1 unit of time to complete, find the least costly one-processor schedule if no task may be interrupted, no two tasks can run concurrently, any task that is not completed by its deadline incurs its penalty, and the cost of a schedule is the cost of all the penalties incurred by all the tasks.

So for example if there are 7 tasks whose deadlines are respectively 2, 5, 2, 3, 5, 4, 3 and penalties are respectively 5, 2, 3, 7, 1, 6, 4, then only 5 tasks can be scheduled by their deadlines. The optimal schedule allows the tasks with penalties 7, 6, 5, 4, and 2 to complete by their deadlines, and thus has cost 3 + 1, or 4. One optimal schedule begins with the tasks with penalties 4, 5, 7, 6, and 2.

Note that optimal schedules need not contain gaps -- for every optimal schedule with a gap there is another optimal schedule that performs the tasks in the same order and has no gaps.

LONGEST MOSTLY TRUE SUBSTRING
Given a string of bits, find the longest substring with the property that at least half of its bits are 1. So for example the string 001110000 would have three optimal solutions of length 6 -- 111000, 011100, and 001110. As always, you need only find one optimal solution.

INDEPENDENT SET
Given an undirected graph, find a subset of its vertex set of maximal size such that no two vertices are adjacent in the graph. So for example if the vertex set is {1, 2, 3, 4, 5, 6, 7}, and two vertices are adjacent iff one is even and one is odd, then one maximal independent set (in fact, the only one) is {1, 3, 5, 7}.
EXACT SET COVER
Given a collection of sets, determine whether there is a subcollection whose union is the same as that of the original collection, and for which each pair of sets in the subcollection is disjoint. Assume that sets are represented as TreeSets of Comparables. So for example, the collection { {1,2,3,6}, {1,2,4,6}, {1,3,4,6}, {2,3,4,6}, {4,5}} is a positive instance, with solution { {1,2,3,6}, {4,5} }. And the collection { {1,2,3,6}, {1,2,4,6}, {1,3,4,6}, {2,3,4,6}, {3,4,5,6}} is a negative instance, since no two sets in the subcollection can be disjoint.

DOMINO COVERING
Given a set of squares of an m by n checkerboard (i.e., an m by n array of squares), determine whether the set can be covered exactly by a set of dominoes, where a domino is a 2 by 1 or a 1 by 2 array of squares. No square outside the set may be covered by a domino.

The board and the input set are to be represented by an array of bits, so that the array literals

{{0,0,1,0}, {0,1,1,0}, {0,1,0,0}, {0,0,0,0}} and
{{0,1,0,0}, {0,1,1,0}, {0,1,0,0}, {0,0,0,0}} and
represent respectively the 4 by 4 boards 
       ..X.       .X..
       .XX.       .XX.
       .X..       .X..
       ....       ....
with four given squares each (the ones represented by X's). Here the first set can be covered but the second set cannot.

LEAST COST CYCLE
Given a directed graph with edge weights, find the lowest-cost simple cycle, where the cost of a cycle is the cost of the edges that make it up. The input graph is to be represented as an adjacency matrix whose entries are edge weights. Do not assume that edge costs are nonnegative (in practice, it is of some importance to determine whether a graph has a negative cost cycle). For example, the graph represented by the Java array literal
{{0,9,9,9}, {-1,0,9,9}, {9,-1,0,9}, {9,9,-1,0}} has a minimum cost cycle (0 3 2 1 0) of cost 6.
COMMON DEADLINE TASK SCHEDULING
Given a set of tasks with a common deadline D, where each task has a positive integer time requirement and a value equal to its time requirement, determine the schedule of maximum value if the value of a schedule is the sum of the values of those tasks that are scheduled to complete by their deadlines. Assume that no task may be interrupted and that no two tasks can run concurrently. So for example if D = 23 and the time requirements are 32, 16, 8, 4, and 2, the optimal schedule has value 22 = 16 + 4 + 2.