Assigned: April 4
Due: May 2
This assignment will be considered as equal in value to two problem sets. Assignments will be accepted up until May 9; assignment submitted after the due date will be penalized one point out of ten.
Your assignments can be done in any language that can run on the Sun system. They should be submitted by email to Ji-Ae Shin, the TA for this course, at jiae@cs.nyu.edu. Your email should include:
The basic GSAT subroutine takes as arguments:
(1) the set of atoms used;
(2) the set of clauses;
(3) values for the parameters max_climbs and max_restarts.
It should return a satisfying valuation on the atoms, if it can find
one; else a flag indicating failure.
You should implement three super-routines that invoke this. The first accepts a set of clauses from standard input, one clause per line, using single alphabetic characters as propositional atoms, "|" as the symbol for "or" and "-" as the symbol for "not". It should output a line either showing a satisfying assignment in the form "atom = value" or showing the message "Failure" Thus, a typical input might be
A | -B | C | D -A | C | -D -A | -B | -C
and the corresponding output might be
A=T B=F C=T D=T
The second superroutine program takes a value N as input, generates 20 random sets of KN clauses, of 3 literals each, over N atoms, for K=1 to 10, and outputs the median, maximum, and minimum time required for each value of K.
The third superroutine takes a value N as input. It then solves the N-queens problem by generating an atom for each square on the chessboard; generating clauses asserting (a) that no two queens can take each other; (b) that every column contains a queen; and running GSAT. Do a little hand-tuning to find a suitable value of max_climbs.
Let me give a little more detail here. To translate the N-queens problem into GSAT, you should:
1. Generate a propositional atom for each square, asserting that it contains a queen.
2. For each column, add a clause of length N asserting that there is at least one queen in the column.
3. For each pair of squares that can attack either along a row or along a diagonal, add a binary clause stating that at least one of the square is empty.
Note that these guarantee that there is exactly one queen in each column. Proof: If there were two queens in one column and at least 1 in every other column, then there would have to be a row with two queens, since there are the same number of rows as columns.
Now, the number of pairs of squares on the board that can attack in a row is N^{2}(N-1)/2. The number of pairs of squares that can attack on a diagonal is, as it happens, (N-1)N(2N-1)/3. The total number of clauses is therefore about (7/6)N^{3}. So with a reasonable encoding scheme, the demands on memory should be bearable for N=20 (about 9400 clauses), perhaps even for N=30 (about 31,500 clauses). N=100 (about 1,160,000 clauses) would need some serious bit squeezing; don't feel obliged to try this.
Your writeup should present your experimental results.
In this project, you construct a program that recommends movies to users.
A file showing how 20 or so people have rated 40 movies will be made available on the course home page. The possible ratings are 1 -- poor; 2 -- OK; 3 -- good; 4 -- great; 0 -- not seen.
The input to this program is this data file. The output should be the same matrix, but with every 0 replaced by the program's estimate of how well the individual would rate the movie.
I suggest using one of the following three methods, or a combination of them:
Each of these involves the use of a numerical weighting scheme. You should not just use the first numbers that occur to you. Rather you should tune these weights, either by hand, or automatically. Your write-up should include a description of the method the program uses to make prediction, and the method you or it uses to tune the parameters involved.
If you want to try some other method, discuss it with me.
To collect the data, I will email a questionaire to the class. Please answer the questions in a return email to jiae@cs. Please do NOT email the ratings to the entire class. Please do NOT share your ratings with anyone else.
The data file will be assembled from the responses. Each line of the file corresponds to one person; the ratings for the movies are listed in the same order as in the email. One quarter of the ratings submitted, chosen randomly, will be replaced by 0; the true value will be used for testing by the grader.
To test your own code, and to tune the parameters, you should do likewise; replace some fraction of the data you are given by 0, and see how well your algorithm estimates the missing data. (You might also enjoy checking the program's recommendations for yourself.)
To be frank, I don't know how successfully this project can be carried out, even in principle. Twenty people is really a small sample for any statistically reliable inferences. Also, I don't know how systematic movie preferences actually are; after all, if the entries in the matrix are generated by flipping coins, then no amount of data will allow you to make any predictions. Also, I hope that most of you have seen a lot of these movies; if most of the entries in this matrix are 0, I will have to do something about this assignment. Do the best you can.