Description
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
