Advanced Software Development
CSG 260

Karl Lieberherr

Homework 2
----------

Part 1:
=======

The motivation for this homework is to learn more 
about what you can do with aspects.

Implement a recursive backtrack algorithm for finding
a maximal assignment (satisfying the maximum weight)
for the standard satisfiability problem. Use
the OR relation (OR1, OR2) is enough to make the
problem interesting because this problem
is already NP-hard.

I suggest a simple algorithm of the form:
f is a cnf.

current_min_unsat = |clauses(f)|;
current_best_I = random assignment;

Precise(f) returns interpretation I and unsat_clauses

 consider f reduced for x = true;
 if unsat_clauses < current_min_unsat then 
   Precise(f[x=1]);
   update current_min_unsat and current_best_I

 consider f reduced for x = false; 
 if unsat_clauses < current_min_unsat then 
   Precise(f[x=0]);
   update current_min_unsat and current_best_I

You are welcome to add improvements to this algorithm
but this is not needed. 

Does this algorithm work for any CSP problem captured in
/home/lieber/.www/courses/csu670/f06/hw/2/csp ?

Don't read further than this before you have implemented
your search algorithm. If you do, then observe how knowledge
of what follows influences your design of part 1.

Part 2:

Use AspectJ aspects that turn your maximization algorithm from
part 1 into a minimization algorithm.
Instead of finding a maximal assignment, we want to find a minimal
assignment.

Can you change your algorithm without touching it, using aspects?
What kind of "Aspect interface" are you assuming?
In other words, what kind of properties must your base-program
have for your aspect to work? For example, if you replace every less_than
by a greater_than then you might accidentally capture a less_than
that sould not be changes. For example, you might use a
less_than also in the printing part for formatting purposes.

Consider the maximization and minimization problem together
for the general CSP problem.
Find a set of relations A so that t[Max,A] is different from
t[Min,A] and where the minimization problem can be solved
in polynomial time while the maximization problem is hard.


Part 3:
Use AspectJ aspects that turn your maximization algorithm from
part 1 into a maximization and minimization algorithm.
As output it prints both a maximal and a minimal assignment.
Can you solve the problem so that only one pass through the search 
space is done? (Just running Part 1 and Part 2 does not count as
a solution because it would traverse the search space twice)

Part 4:

Read the paper
http://www.ccs.neu.edu/home/lieber/p-optimal/partial-sat-II/Partial-SAT2.pdf
first 5 pages only




===================
Develop MAXMEAN for simple case

Consider MAX-2-SAT where the weighted constraints can only be of the form:

OR(x y) 	t1
OR(x !y)	t2
OR(!x !y)	t3
OR(x)		t4
OR(!x)		t5

Consider