Description
For this problem, handin a lab report pdf (include name, date, assignment and class number in pdf). Perform the following two comparisons of AC-1 and AC-3 on the N-queens
problem:
• For N = 4 : 10, for each N generate at least 200 random D matrixes, where the
percentage, p, of ones varies from 0 to 1 in steps of 0.2, and for each matrix record:
– The number of ones before and after the application of the constraint algorithms, and
– The execution time of each algorithm for each trial (using tic and toc).
Study the conditional expected reduction in ones (for each N separately) for a given starting
number of ones. Find the best regression fit and report the constants in the complexity functions of the two algorithms, and find the relative execution time ratio of the two algorithms
(as a function of p and N).
The top-level AC functions should follow these headers:
function D_revised = CS4300_AC1(G,D,P)
% CS4300_AC1 – AC1 function from Mackworth paper 1977
% On input:
% G (nxn array): neighborhood graph for n nodes
% D (nxm array): m domain values for each of n nodes
% P (string): predicate function name; P(i,a,j,b) takes as
% arguments:
1
% i (int): start node index
% a (int): start node domain value
% j (int): end node index
% b (int): end node domain value
% On output:
% D_revised (nxm array): revised domain labels
% Call:
% G = 1 – eye(3,3);
% D = [1,1,1;1,1,1;1,1,1];
% Dr = CS4300_AC1(G,D,’CS6100_P_no_attack’);
% Author:
%
% UU
% Fall 2016
%
function D_revised = CS4300_AC3(G,D,P)
% CS4300_AC3 – AC3 function from Mackworth paper 1977
% On input:
% G (nxn array): neighborhood graph for n nodes
% D (nxm array): m domain values for each of n nodes
% P (string): predicate function name; P(i,a,j,b) takes as
% arguments:
% i (int): start node index
% a (int): start node domain value
% j (int): end node index
% b (int): end node domain value
% On output:
% D_revised (nxm array): revised domain labels
% Call:
% G = 1 – eye(3,3);
% D = [1,1,1;1,1,1;1,1,1];
% Dr = CS4300_AC3(G,D,’CS6100_P_no_attack’);
% Author:
%
% UU
% Fall 2016
%
You should handin the report pdf as well as the code used in the study. The code should
2
conform to the style requested in the class materials. In addition, please turn in a hardcopy
of the report in class before the start of class on September 22, 2015.
Write a lab report in the format (please do not deviate from this format!) described in the
course materials. Discuss the statistical framework to establish a confidence interval on the
means, and the hypothesis test.
3
