Difference between revisions of "CSC212 Homework 5 2014"

From dftwiki3
Jump to: navigation, search
(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 />
  
* NQueens, make it display the number of probes for finding the 1st solution, and the number of all possible solutions.
+
<!--
 +
=Problem #1=
 +
<br />
  
* Implement some form of cutting of the tail-end recursion for the N-QueensYour program will have to output the number
+
* 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 probes it performs to find the first solutionThis number should be less, on the average, for various dimensions N.
+
* 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 getTo 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 MoodleFor 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>

Revision as of 11:05, 23 October 2014

--D. Thiebaut (talk) 23:24, 22 October 2014 (EDT)



...