Difference between revisions of "CSC212 Homework 5 2014"

From dftwiki3
Jump to: navigation, search
Line 1: Line 1:
 
--[[User:Thiebaut|D. Thiebaut]] ([[User talk:Thiebaut|talk]]) 23:24, 22 October 2014 (EDT)
 
--[[User:Thiebaut|D. Thiebaut]] ([[User talk:Thiebaut|talk]]) 23:24, 22 October 2014 (EDT)
 
----
 
----
<onlydft>
+
 
<br />
 
<br />
  
Line 40: Line 40:
 
   
 
   
  
* 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
+
* If the array contains [3 7 8 13 15 21 24 24 24 24 34 36 42 45 45 49 50 55 57 63], and we are searching for key '''24''', then your program will output
 
   
 
   
  3
+
  6
  4
+
  7
 +
8
 +
9
 
   
 
   
 
* You cannot use an iterative method that is not recursive.
 
* You cannot use an iterative method that is not recursive.
* Your program
+
* Submit your program on Moodle, in the Homework 5, Problem 1 section.
 
   
 
   
 
    
 
    
Line 52: Line 54:
  
 
<br />
 
<br />
=Problem #3=
+
=Problem #2=
 +
<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 total number of such solutions.
 +
* The output of your program should just be an integer number representing the number of solutions.
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 
<br />
 
<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 />
 
<br />
</onlydft>
+
[[Category:CSC212]][[Category:Homework]]

Revision as of 11:07, 23 October 2014

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



Problem #1


  • 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:


        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;
        }


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 [3 7 8 13 15 21 24 24 24 24 34 36 42 45 45 49 50 55 57 63], and we are searching for key 24, then your program will output
6
7
8
9

  • You cannot use an iterative method that is not recursive.
  • Submit your program on Moodle, in the Homework 5, Problem 1 section.




Problem #2


  • Modify the N-Queens problem seen in 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 total number of such solutions.
  • The output of your program should just be an integer number representing the number of solutions.