Extra Credit for Programming Assignment 2
CS 771
北美编程代写 The goal of this extra-credit assignment is to evaluate number of steps the MIN-CONFLICT algorithm takes to solve the n-queen problem…
The goal of this extra-credit assignment is to evaluate number of steps the MIN-CONFLICT algorithm takes to solve the n-queen problem as n increases. If you remember, on page 221 of your textbook it is given that for a million-queen problem. It takes 50 steps to solve this problem on average.You will experiment with the following values of n : 10, 102 , 103 , 104 , 105 , 106 and solve the respective n-queen problems.
Since for any fixed value of n, the number of steps required to solve the instance of an n-queen problem. Is a random variable that depends on the initial configuration. Random order in which conflicted variables are chosen by the algorithm. And so on, for each n, you will solve 10 instances of the n-queen problem. Each time starting from a random initial configuration and note down the mean (average). And standard deviation of number of steps required to solve this problem. You will need to submit an error-bar plot, where on the x-axis you will have log10 n (log of the size of the n-queen problem). And on the y-axis you will plot number of steps required (mean. And standard deviation in the form of an error-bar).
Please note that unlike programming assignment 2. You do not need to take initial configuration as an input from the user in an interactive manner. Rather, you will randomly generate initial configurations placing one queen per column in each case.
What to submit : 北美编程代写
- All files that are necessary to run your program including a README file that will explain very clearly how to compile/execute your program. Also a word/pdf file with the error-bar plot. Since you will be submitting more than one file. Please submit a zip file and name your file in the following format (with appropriate file extension): Extra Credit Program2 Lastname Firstname. For example if I were to submit, I would name my file as Extra Credit Program2 Sinha Kaushik.
- Name and user ID (myWSU ID) must appear on top of each program that you submit and also on the word/pdf document containing the error-bar plot.
