100 points + 20 points extra credit, due March 4, 1997
Use the version of the A* algorithm discussed in class to solve some or all of the 7 problems described below. Recall that to apply the A* algorithm to an optimization problem your estimator must be an optimistic estimate for any feasible state accessible from the given state. A Scheme implementation of this algorithm is available both through my web page for this course, and in the file K:SMITH\CS156\SEARCH.PCS
Each problem is worth 35 or 40 points; for your overall grade for this assignment I will add the 3 highest grades for individual problems. Thus you can get full credit (plus up to 20 points extra credit) by doing only 3 problems. Don't count on there being extra credit available on later assignments or tests.
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 should still use the A* algorithm.
HAMILTONIAN CIRCUIT (35 points): Given a directed graph G = (V,E), determine whether it has a Hamiltonian Circuit -- a directed path of |V| edges, whose only repeated vertices are the first and the last. Note that in this case the path must visit all vertices in the graph.
VOTE POWER (35 points): Given a sequence S of integers, where the ith element represents the number of votes possessed by the ith voter, determine whether the voter with the smallest number of votes can ever make a difference between an election succeeding or failing. For example, if the voters have respectively 64, 32, 16, 8, 4, 2, and 1 votes, the voter with just 1 vote can never make a difference. If the voters have respectively 64, 32, 16, 8, 4, 3, and 2 votes, then the weakest voter can make a difference if the vote is otherwise 64 to 63.
You may assume that the sequence S is sorted in nonincreasing order. An instance should yield the answer "no" if the weakest elector can only make the difference between success and a tie, or a tie and failure.
JOB SEQUENCING WITH DEADLINES (35 points): Given a sequence J of job names and a sequence D of positive integer deadlines, where |J| = |D| and the ith element of D is the deadline for the ith element of J, determine whether there is a schedule containing all jobs in which each job is finished by its deadline. Assume that each job requires 1 time unit to complete, and that no two jobs can be run concurrently.
For example, if the sequence of jobs is (a b c d e) and the sequence of deadlines is (4 5 1 4 2), then all jobs can be run by their deadlines (e.g., in the order (c e a d b)). If the sequence of deadlines is instead (3 5 1 3 2), then there is no solution, since four of the jobs would have to be run in the first three time slots.
MAX CLIQUE (40 points): Given an undirected graph G, find the largest clique in G. By definition, a clique is a complete subgraph of G.
MIN COVER (40 points): Given a nonnegative integer n, a set S of size n, and a set T of subsets of S, find the minimum size subset C of T such that the union of all elements of C is S.
MIN CUT (40 points): Given a complete undirected graph G = (V,E) with |V| even, and with a positive cost c(e) defined for every edge e in E, find the cheapest partition of V into two subsets of size |V|/2. The cost of a partition {X,Y} is the sum of the costs of the edges between vertices in X and vertices in Y.
SHORTEST SUPERSTRING (40 points): Given an alphabet A 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. For example, if A = {a,b} and S={abb, bab, abab, bba}, then one possibility for M is ababba. You may assume that the strings are represented as lists of elements of A, rather than as Lisp strings or symbols.
You should turn in a disk with all of your code, as well as a hard copy with all your code and the results of all of your tests.
For each problem, run the search algorithm on each test instances by showing the steps of the computation (e.g., by tracing the GOAL? function). You may also want to test each instance without a trace.
For each problem, you may, and probably should, have additional components of states beyond those given in the definition of the problem instance. For example, you may want to explicitly represent the input size, or the partial solution constructed so far. This means that the solution to an instance may not be obvious from the goal state returned by the search algorithm. In this case, it's ok to emphasize on your hard copy (e.g., by magic marker) the portion of the state that corresponds to the solution.
You are not expected to find and use the best possible estimator for a problem. In general, I will not deduct points for minor inefficiencies, but I may deduct for gross inefficiency. If your representation or estimator is inefficient, it's possible that you will not have enough time and/or space to get all the test instances to work. In this case you might get less of a deduction if you replace the bad test instances by others. If an instance works but the trace is too large to print, you might test without the trace and use the RUNTIME function to show that the computation takes too long.
Use at least the following test cases:
For HAMILTONIAN CIRCUIT (the adjacency matrices are):
0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1
1 0 1 0 0 0 0 1 0 1 1 0 0 1 1 0 1 0 1 0 1 0
0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 1
0 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0
0 0 0 1 0 1 0 1 1 1 1 0 0 1 0 1 0 1 0 1 0 1
0 0 0 0 1 0 1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0
1 0 0 0 0 1 0 1 0 1 1 0 0 0 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 1 1 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 1 1 1
1 0 1 1 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 0 1
1 1 0 1 1 1 0 0 0 1 0 1 0 1 0 1 0 0 1 1 0
1 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1
1 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 1 1 0 0 1
1 1 1 1 1 0 0 0 1 0 1 0 1 0 1 0 1 1 1 1 0
1 1 1 1 1 1 0 0 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1
For VOTE POWER:
S = (64 32 16 8 4 3 2)
S = (128 64 32 16 8 4 2)
S = (11 11 11 11 11 11)
S = (40 30 20 10 7 5 3 2)
S = (40 30 20 20 7 5 3 2)
S = (40 30 20 20 20 5 3 2)
S = (80 40 30 20 15 8 8 3)
For JOB SEQUENCING WITH DEADLINES (in each case, let J be the sequence of integers from 1 through |D|):
D=(4 5 1 4 2)
D=(4 5 1 4 2 4)
D=(3 5 1 3 2)
D=(4 5 1 6 2 4)
D=(3 5 3 6 3 6)
D=(3 5 3 5 3 5)
For MAX CLIQUE (the adjacency matrices are):
0 1 0 1 0 1 0 0 1 0 1 0 0 1 1 1 1 1 0
1 0 1 0 1 0 0 0 0 1 0 1 1 0 1 1 1 1 1
0 1 0 1 0 1 1 0 0 0 1 0 1 1 0 1 1 1 1
1 0 1 0 1 0 0 1 0 0 0 1 1 1 1 0 1 1 1
0 1 0 1 0 1 1 0 1 0 1 0 1 1 1 1 0 1 1
1 0 1 0 1 0 0 1 0 1 0 0 1 1 1 1 1 0 1
0 1 1 1 1 1 0
0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 1 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 0 0
0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0
1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0
0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 0
For MIN COVER:
n = 8, S = {1 2 3 4 5 6 7 8},
T = {{2 4 6 8}, {3 6}, {4 8}, {5}, {6}, {7}, {8}}
n = 8, S = {1 2 3 4 5 6 7 8},
T = {{1}, {2 4 6 8}, {3 6}, {4 8}, {5}, {6}, {7}, {8}}
n = 7, S = {1 2 3 4 5 6 7},
T = {{1 2 3}, {1 3 5}, {1 2 4 6}, {2 3 6}, {4 7}}
n = 7, S = {a b c d e f g},
T = {{e g g}, {b a g}, {b e d}, {f a c e}, {c a b},
{b a g g a g e}, {c a b b a g e}}
n = 7, S = {mon tue wed thu fri sat sun},
T = {{mon wed fri}, {sat sun}, {fri sat}, {tue thu},
{mon tue wed thu fri}, {sat sun mon tue wed}}
n = 6, S = {1 2 3 4 5 6}, T = {{5}, {4}, {1}, {3}, {2}, {6}}
For MIN CUT (the cost matrices are):
0 1 1 1 1 1 0 1 2 4 0 1 2 3 1 0 1 1 1 1 1 0 8 16 1 0 3 2 1 1 0 1 1 1 2 8 0 32 2 3 0 1 1 1 1 0 1 1 4 16 32 0 3 2 1 0 1 1 1 1 0 1 1 1 1 1 1 0 0 2 1 2 1 2 1 2 0 1 2 1 2 1 2 1 0 7 10 9 5 4 2 0 2 1 2 1 2 1 1 0 1 2 1 2 1 2 7 0 3 1 13 11 1 2 0 2 1 2 1 2 2 1 0 1 2 1 2 1 10 3 0 2 14 12 2 1 2 0 2 1 2 1 1 2 1 0 1 2 1 2 9 1 2 0 8 15 1 2 1 2 0 2 1 2 2 1 2 1 0 1 2 1 5 13 14 8 0 6 2 1 2 1 2 0 2 1 1 2 1 2 1 0 1 2 4 11 12 15 6 0 1 2 1 2 1 2 0 2 2 1 2 1 2 1 0 1 2 1 2 1 2 1 2 0 1 2 1 2 1 2 1 0For SHORTEST SUPERSTRING:
A={a,b}, S={abb, bab, abab, bba};
A={a,b,c}, S={ab, bc, ac, ca, cb, ba};
A={0,1}, S={0 ,01, 001, 0001, 00001};
A={0,1}, S={000, 001, 010, 011, 100, 101, 110, 111};
A={a,b}, S={aa, aba, abba, abbba}