**Final report
**

.........I am very pleased that I was selected to be a CRA participant
this summer. This is the

greatest honor that can be given to a student who wish to put all his efforts
and deeds

into the Computer Research.

..........I have had a wonderful summer doing the research with Prof Paula Whitlock
at Brooklyn

College, CUNY. I have gained a very nice and interesting experience in Computer
Science,

Research, and in life in general.

..........Our summer research covered the most interesting and enigmatic area
of the computer

science - SAT problems. To look at the complete description of a problem click
here .

.........First we started testing our code by using 2-SAT problems.
It was a very good determination of the correctness of our program (because
the results of running 2-SAT are well known).

When we got read of all the "memory faults", incorectnesses, and just
errors(+I proposed

and wrote flaCheck -- to determine if we have (A) and (~A) in the same formula
at the same time +

trying different kinds of random number generators), we moved to examining 3-SAT
problems and their properties.

...........These are graphs I got using "gnuplot"
features (week 10):

I tested alpha in the range from 4 to 5 (n=50,number of instances=100 --

before using multithresding advantures)

Here I was trying to take a closer look at the crossover point(the
number of instances is

1000 ) --range of alpha is from 3.6 to 4.8

..........Then we moved to "backbone size" determination.
The *backbone *of a satisfiable

SAT instsance is the set of entailed literals (a literal l is *entailed*
by a satisfiable

SAT instance C iff C AND (NOT l) is unsatisfiable). And so the backbone size

is the number of entailed literals. The backbone fraction if the backbone size
over

the number of variables.

.........Therefore, in determining some backbone size first we should consider

formulae that are satisfiable. Then go through each literal l and add (NOT l)

to the formula. If the formula is unsatisfiable - l is in the backbone. If the
formula is satisfiable - add (l) to the formula, if it is unsatisfiable ~l is
in the backbone;

etc(repeat for all literals). If it the formula is satissfiable in both cases
neither l nor ~l is

in the backbone. I wrote all the code associated with the backbone sizes (week
6).

........ But I could run only a relatively small number of instances.
Therefore, we decided to

pot all our efforts, code writing, and experiments to MULTITHREADING (weeks
7-9).

It was a very interesting and challenging period in our research. We tried a
lot of

aThreadFunction interpretations . + we used mutex_lock() and mutex_unlock()

functions to prevent accessing some glabal variables by multiple processors
at

the same time, and then we tried to avoid using those locks and unlocks!

They slow down the execution of the code. It was a lot of fun and new knowledge.

if you are interested and want to look at our activity closer go to
my journal and

find weeks 7-9.

This graph was produced by using multithreading applications.
The number of instances

is 8000 + a wide range of alpha -- from 2 to 5

This graph represents the relationship of the values of alpha to the backbone
fractions.

........Finally I studied and used GNUPLOT to convert the most interesting of
our results to

graphs (As you have seen before). I found gnuplot very friendly and easy to
us

(thank to my Mentor).

I want to thank my mentor -- Professor Paula Whitlock(at Brooklyn
College, CUNY)

for her brilliant mind, patience, and all the knowledge she gave me. Also --
CRA

organization for the greatest honor to participate in this increadable and wonderful

summer reserach! I am very proud that I was a part of this greatest development
of

Computer Science. Thank you! You gave me the great opportunity to realize myself,

to plan my activities for the graduate school, and to have the BEST EXPERIENCE

IN MY LIFE.

P.S. Special "thank you" - for Professor Scott Dexter
(Brooklyn College, CUNY )- for the huge

part of his life that was given in a name of our research, beautiful and quick
mind, all the advice,

and everything he has done for me.