Assignment #1

CS 156
due September 22, 2005
100 points + 20 points extra credit

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.

To solve a problem using my version of the A* algorithm, you will need to define a class that implements the State interface (which is also given 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 likely 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.

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.

Please use Java 5.0 for this assignment, if at all possible. If you use an earlier version of Java, you will need to rewrite the search method of the AStar class so that it uses a while loop controlled by an iterator. I will also accept submissions in Scheme, but in this case you are responsible for translating the Java code that I am providing into Scheme.

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.

You needn't check for illegal input to a problem. If you do so, 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 text's more general version of the A* algorithm, or about making your estimator monotonic.

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. 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, but make sure to use the A* algorithm.

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 variables in addition to those that are required by the assignment.

You are to test your program with the test class A1.java available from the class web site. You are to turn in both hard and soft copies of all of your code (but not A1.java, unless you modify it) as well as a hard copy of the results of your testing. Unless I say otherwise in class, the soft copy of your code should be turned in on a diskette.

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

PARTITION
Given a set of items, each of which has an integer weight, determine whether or not there is a partition of the set into two subsets, each of which has the same total weight. Here the (total) weight of a subset is the sum of the weights of its members. The input to this problem should be represented as a LinkedList of the integer weights (you don't have to represent the items explicitly).
SHORTEST SUPERSTRING
Given an alphabet A of symbols and a sequence S of strings over the alphabet, find the shortest string M over A such that every string of S is a substring of M. Assume that S is represented as a LinkedList of Strings, while the alphabet is represented only implicitly, as the set of all characters appearing in some string of S. For example, if S={abb, bab, abab, bba} (so that A = {a,b}), then one possibility for M is ababba.
TOPOLOGICAL SORT
Given a set of tasks and a collection C of pairs of tasks, find a sequence S that contains all and only the elements of the set, and such that for all pairs (v,w) in C, v appears before w in S. In other words, if the pair (v,w) is interpreted to mean that v is a prerequisite to w, then S gives an order in which the tasks may be performed so that no task is completed until all of its prerequisites are done. For this problem you are to represent the tasks as integers and the collection C in terms of a class IntegerPair that is given on the class web site. The set of tasks is to be defined implicitly as the set of all task that appear in some pair of C, so the constructor for the TopologicalSortState is to take a LinkedList of IntegerPairs of integers as its only argument.

GRAPH COLORING
Given an undirected graph G = {V,E}, find a "coloring" function c mapping E to the set of the first n positive integers such that
(1) whenever (v,w) is an edge, c(v) is different from c(w) and
(2) n is the smallest possible integer for which such a function c exists.
For example, if V is the set of U.S. states containing Nevada and the states that border it, and (v,w) is an edge iff v and w have a common border, then the smallest possible value of n is 4, and one coloring gives Nevada the color 1, California and Idaho the color 2, Oregon and Utah the color 3, and Arizona the color 4.

BIN PACKING
Given a collection of items represented as an array of integer weights, find the smallest number of bins that is necessary to contain all the items, if each bin has capacity 100. In other words, find a partition of the array into pieces such that the sum of the weights of each piece is at most 100, and make sure that your partition has minimum possible size. So for example, given the input {20,30,40,50,60}, two bins are enough -- one to contain the items of weights 40 and 60, and one to contain the items of weights 20, 30, and 50. On the other hand, the inputs{20,30,40,50,61} or {40,40,40,40,40} would each require three bins.

HAMILTONIAN PATH
Given a weighted directed graph G = (V,E) represented as an adjacency matrix, find its lowest-cost Hamiltonian Path -- a directed path of |V| vertices, such that every vertex appears in the path exactly once. The cost of a path is the sum of the costs of the edges in the path. You may assume that the edge costs are integers.

POST'S CORRESPONDENCE PROBLEM
Given two arrays A and B of strings, find a nonempty string that is both the concatenation of elements of A and the concatenation of the corresponding elements from B. Here two strings are said to correspond iff A[i] = B[i]. You may assume that A and B have the same length. So for example, if A = {"1","10111","10"} and B = {"111","10","0"}, then the string "101111110" is a solution, since it is the concatenation of A[1], A[0], A[0], and A[2] and also the concatenation of B[1], B[0], B[0], and B[2].

On the other hand, if A = {"1","10","0"} and B = {"11","101","10"}, then there is no solution, since the concatenation of any nonempty sequence of strings from A is shorter than the concatenation of the sequence of corresponding strings from B. Note that the state space for this problem is infinite, so that A* will run forever if there is no solution. The test cases for this problem have been selected so that they all have solutions; however you should choose your estimator so that every state in the state space has a chance to be visited. It turns out that there is no solution algorithm of any kind for this problem, so in a sense, A* does as well as one could hope for.