Assigned: Jan. 22

Due: Feb. 19

The assignment is to write programs to solve the KERNEL problem described in Problem Set 1 using the two algorithms given there, implementing both using DFS and iterative deepenening; and to test these algorithms over randomly generated graphs.

- 1. Algorithm 1, implemented with DFS
- 2. Algorithm 1, implemented with ID
- 3. Algorithm 2, implemented with DFS
- 4. Algorithm 2, implemented with ID

Note: none of these programs should generate the state space * as a
data structure * and 25% will be deducted for any program that does
this. The state space is purely an * implicit * construct.

For example, a file containing graphs 1 and 2 from Problem Set 1 could have the following form:

A B D A B C C D * E F F G G H H I I E H E *The output for each method on each graph should be:

- A listing of the graph. (Just an echo of the input; reformat if you want.)
- The name of the method (e.g. "Algorithm 1: DFS")
- The first kernel found, or "No solution found".
- The number of states in the state space searched.
- The elapsed CPU time.

for each vertex V do for each vertex U do if U != V begin R := random number between 0 and 1; if R < p then add edge U -> V to G;Carry out the following operation:

For p := {1/4, 1/2, 3/4} do For I := 1 to 100 do begin generate a graph G of density p over 8 vertices; run the four methods on G; collect the statistics listed below endFor each value of p and for each method, you should collect and report the following statistics: the average, max, min and standard deviation of the CPU time and of the number of state space nodes generated. That is, your output should give 96 numbers (3 values of p * 4 methods * 4 statistics * 2 measures of time.) In addition, you should report for each value of p, the fraction of graphs in which a solution is found. For instance, your output could have the following form:

p Method Measure Avg Min Max StDev 1/4 Alg. 1 DFS CPU 2.3ms 0.5ms 15.6ms 1.5ms 1/4 Alg. 1 DFS #States 35.4 8 200 10.2 1/4 Alg. 1 ID CPU 1.5ms 0.8ms 25.4ms 0.6ms ... When p=1/4, 90% of graphs have a kernel When p=1/2, 40% of graphs have a kernel When p=3/4, 20% of graphs have a kernel

Please note: The above numbers were entirely made up out of my head. I have no idea whether they're anywhere close to the true values.

Code may be written in any language that I can compile on the Sun system.

- Source code for parts I and II, suitably commented.
- A README file, telling me how to compile and run your code.
- The output for part II.