# Project 1 hints

Here is one way to perform the experiments. In the text below, n refers to the number of variables in the CNF and m the number of clauses.

## 1. Finding hard problems

In the Mitchell/Cook paper, they did an experiment (p.8) on DPLL, showing that at a certain point the problems become very hard, and then drops off. It is related to the structure of the CNF. The second graph shows the relationship between the % of problems solvable in the range. You can carry out a similar experiment with a couple of different values for n to see if you get similar results.

## 2. Tuning Walksat

Initially Walksat seems to perform much worse than DPLL. However, when given good parameter values, Walksat can do very well. In the "Evidence for Invariant ..." paper, they describe such phenonmenon. You can implement sophisicated adjustment described in the paper. A more straightfoward approach is to take a number of harder problems (which you know how to generate from part 1) and run different values of Nflips, Nrestarts and p against it. To test the values of one parameter, you need to fix the other parameters. For example, to test for values of p, you need to fix Nflips and Nrestarts.

## 3. Comparing DPLL & Walksat

From part 1 above, you should now be able to tell what are easy and hard problems, and generate them accordingly. Try to run Walksat and DPLL on these problems, and see what happens. One possible way to evaluate the algorithms is to cut off the search at a fixed time, say a few minutes. Find some n so that DPLL fails within the time threshold, and test how Walksat performs given the timethreshold. You can make plots similar to figure 1 of Mitchell/Cook paper, but with data for both DPLL and Walksat.