Difference between revisions of "CSC212 Homework 5 2014"
(Created page with "--~~~~ ---- <onlydft> * NQueens, make it display the number of probes for finding the 1st solution, and the number of all possible solutions. * Implement some form of cuttin...") |
|||
| Line 2: | Line 2: | ||
---- | ---- | ||
<onlydft> | <onlydft> | ||
| + | <br /> | ||
| − | + | <!-- | |
| + | =Problem #1= | ||
| + | <br /> | ||
| − | * | + | * Explain how you would implement a modification of the N-Queens problem, where you would cut some of the tail-end recursion, in an effort to make the program find a solution faster. |
| − | of | + | * You may want to include the code you propose to add (no more than 10 lines of Java code). |
| + | * You may run your program with and without the modification on some large value of N and report on the execution time improvement you get. To time your program, look at this [[Speed_of_Instructions:_Nasm,_Java,_C%2B%2B_and_Python_comparison#Java_Code| Example]] where the execution time of a Java program is measured. | ||
| + | * Write up your answer as a 1 page pdf which you will submit to Moodle, Homework #5, Problem #1 section. | ||
| + | <br /> | ||
| + | --> | ||
| + | =Problem #1= | ||
| + | <br /> | ||
| + | * Write a recursive Java program called '''Hw5_1.java''' that implements a modified recursive binary search that, instead of returning the index where the ''key'' was found, returns an ArrayList of all the indexes where the ''key'' is located. | ||
| + | * You must use this function to create a sorted array of dimension ''N'': | ||
| + | <br /> | ||
| + | <source lang="java"> | ||
| + | private static int[] initSortedArray( int N ) { | ||
| + | if ( N<10 ) N = 10; | ||
| + | int[] array = new int[N]; | ||
| + | array[0] = 3; | ||
| + | for ( int i=1; i<N; i++ ) | ||
| + | array[ i ] = array[i-1] + (i*11)%7; | ||
| + | |||
| + | // duplicate some keys | ||
| + | for ( int i=1; i<4; i++ ) | ||
| + | array[ N/3 + i] = array[N/3]; | ||
| + | |||
| + | return array; | ||
| + | } | ||
| + | </source> | ||
| + | <br /> | ||
| + | :This way the indexes for a given key will be known to the testing program in Moodle. For verification, this is the array created by the function for ''N'' = 20: | ||
| + | |||
| + | 3 7 8 13 15 21 24 24 24 24 34 36 42 45 45 49 50 55 57 63 | ||
| + | |||
| + | |||
| + | * If the array contains [1, 2, 3, 4, 4, 5, 10, 20, 20, 100], and we are searching for key '''4''', then your program will output | ||
| + | |||
| + | 3 | ||
| + | 4 | ||
| + | |||
| + | * You cannot use an iterative method that is not recursive. | ||
| + | * Your program | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | <br /> | ||
| + | =Problem #3= | ||
| + | <br /> | ||
| + | * Modify the N-Queens problem seen in [[CSC212_Lab_9_2014| Lab #9]] and make it compute the total number of different solutions existing for an NxN board. The program as we have seen in the lab stops when it finds a solution, but there might be many different possible ways of putting N queens on the NxN board. Make your program compute the number of such solutions. | ||
| + | * The output of your program should just be an integer number. | ||
| + | <br /> | ||
</onlydft> | </onlydft> | ||
