Advanced Software Development
CSG 260 / Fall 2006

Karl Lieberherr

Due date: Sep. 26, 2006

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 interpretation (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 interpretation;

Precise(f) returns interpretation I and unsat_clauses

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

 consider f reduced for x = 0; 
 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 interpretation, we want to find a minimal
interpretation. We call this the max-to-min aspect.
Hint: in AspectJ you can only intercept named methods and not the
comparison operators such as > and <. You need to use
named methods for them.

Regarding AspectJ usage check file CCS_AspectJ_Usage.html.

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 should not be changed. 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 interpretation.
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
The first 5 pages only. This is an unpublished paper.
The same information is in published form here:

http://www.ccs.neu.edu/research/demeter/biblio/maxmean.html

but this published paper might be harder to read.

Notice that algorithm MAXMEAN uses the line:
if mean[k-1](S[x=1]) > mean[k](S[x=0]) then x=1 else x=0
to make the decision whether x should first be set to 1 or 0.
This is called value ordering.

Use an aspect to modify algorithm Precise(f) from Part 1
so that it uses the predicate mean[k-1](S[x=1]) > mean[k](S[x=0])
to decide whether it is better to set x first to true or to false.
In other words, you write an aspect to make the original algorithm more
"clever"  because it can make a big difference in the search space
if the algorithm tries to use a clever way of deciding which
branch of the search space to try first.

Develop the polynomial in MAXMEAN for the simple case of
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 !y)	t4
OR(x)		t5
OR(!x)		t6

Test your aspect on a few examples. Does it actually help to
reduce the size of the search space.
Write a separate aspect to measure the size of the search space.
This is another good use of aspects: collecting statistics.

Again focus on the "aspect interface": what kind of assumptions
do you make about the base program so that your aspect will work properly.

Part 5:
What happens if you apply both aspects: the value ordering aspect
and the max-to-min aspect to the base program?
Does the combined program work properly?

From now on, turn your work in via blackboard and bring a hard copy
with the most important information.

For programs, the hardcopy should include the documented code,
one test input and corresponding output. The source program with 
a compilation and run script is on blackboard in a zipped file
FirstName_LastName_hw2.zip.
Additional test cases are also in the zip file.

The hardcopy should also contain your answer to the questions.

All information you turn in in the hardcopy should also be in the 
electronic file.