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...")
 
 
(20 intermediate revisions by the same user not shown)
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 />
 +
__TOC__
 +
<br />
 +
<bluebox>
 +
This assignment is due Friday (note the different day) Oct. 31st, at 11:55 p.m.
 +
</bluebox>
 +
<br />
 +
<!--
 +
=Problem #1=
 +
<br />
  
−
* NQueens, make it display the number of probes for finding the 1st solution, and the number of all possible solutions.
+
* 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. 
 +
* 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.  By ''returning'', I mean either return with a <tt>return</tt> statement, or an ArrayList that is passed as a parameter, or an ArrayList that is a member variable of the class.
 +
* 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
 +
  
−
* Implement some form of cutting of the tail-end recursion for the N-Queens.  Your program will have to output the number  
+
* 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
−
of probes it performs to find the first solution.   This number should be less, on the average, for various dimensions N.
+
−
</onlydft>
+
6
 +
7
 +
8
 +
9
 +
 +
* You cannot use an iterative method that is not recursive.
 +
* Your program should get ''N'', the dimension of the array, and the ''key'' from the command line.  Here's the code you should use:
 +
<br />
 +
::<source lang="java">
 +
    public static void main(String[] args) {
 +
if ( args.length == 0 ) {
 +
System.out.println( "Syntax: javac  Hw5_1  N  key" );
 +
return;
 +
}
 +
int N = Integer.parseInt( args[0] );
 +
int key = Integer.parseInt( args[1] );
 +
    }
 +
</source>
 +
<br />
 +
'''Note'''<br />
 +
::* If you are using Eclipse (which I hope you are), then passing parameters on the command line is a bit tricky, though totally possible.  Here's how you do would do it.  First click on the little black down arrow next to the Green Circle/White Triangle icon (Run icon) you click to run your programs. 
 +
<br />
 +
<center>
 +
[[Image:EclipseRunConfiguration.png|400px]]
 +
</center>
 +
::* Make sure your program is the one currently highlighted in the list, and click on '''Run Configurations'''.
 +
::* Click on the '''Arguments''' tab, and enter N and the key in the '''Program Arguments''' window ("20 24" in this case).
 +
::* Run your program.  From then on, whenever you press the run-icon it will use these two numbers for N and key.  If you want to change them, go through these same two steps again.
 +
<br />
 +
<center>
 +
[[Image:EclipseRunConfiguration2.png|500px]]
 +
</center>
 +
<br />
 +
* Your output should be sorted.  To sort an ArrayList of integers, you can use the ''Collections'' library, as illustrated below:
 +
<br />
 +
::<source lang="java">
 +
import java.util.Collections;
 +
 
 +
...
 +
 
 +
    ArrayList<Integer> indexes = new ArrayList<Integers>();
 +
 
 +
    // add some ints to the array
 +
    ...
 +
 
 +
    // sort the ArrayList
 +
    Collections.sort(indexes);
 +
 
 +
</source>
 +
<br />
 +
* Submit your program on Moodle, in the Homework 5, Problem 1 section.
 +
 +
 
 +
 
 +
 
 +
<br />
 +
 
 +
=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.
 +
* Call your program '''Hw5_2.java'''.
 +
* The output of your program should just be an integer number representing the number of solutions.
 +
* Your program will get ''N'' from the command line, as in:
 +
 +
  java Hw5_2  20
 +
 +
:which will compute the total number of different ways we can organize 20 queens on a 20x20 chessboard.
 +
* Submit your program to Moodle, Homework 5, Problem 2.
 +
<br />
 +
<br />
 +
==Some Solutions==
 +
<br />
 +
* I modified the solution program to make it display the different solutions found:
 +
::<source lang="text">
 +
java Hw5_2_printSolutions 4
 +
--------
 +
. Q . .
 +
. . . Q
 +
Q . . .
 +
. . Q .
 +
--------
 +
. . Q .
 +
Q . . .
 +
. . . Q
 +
. Q . .
 +
2
 +
 
 +
java Hw5_2_printSolutions 5
 +
----------
 +
Q . . . .
 +
. . Q . .
 +
. . . . Q
 +
. Q . . .
 +
. . . Q .
 +
----------
 +
Q . . . .
 +
. . . Q .
 +
. Q . . .
 +
. . . . Q
 +
. . Q . .
 +
----------
 +
. Q . . .
 +
. . . Q .
 +
Q . . . .
 +
. . Q . .
 +
. . . . Q
 +
----------
 +
. Q . . .
 +
. . . . Q
 +
. . Q . .
 +
Q . . . .
 +
. . . Q .
 +
----------
 +
. . Q . .
 +
Q . . . .
 +
. . . Q .
 +
. Q . . .
 +
. . . . Q
 +
----------
 +
. . Q . .
 +
. . . . Q
 +
. Q . . .
 +
. . . Q .
 +
Q . . . .
 +
----------
 +
. . . Q .
 +
Q . . . .
 +
. . Q . .
 +
. . . . Q
 +
. Q . . .
 +
----------
 +
. . . Q .
 +
. Q . . .
 +
. . . . Q
 +
. . Q . .
 +
Q . . . .
 +
----------
 +
. . . . Q
 +
. Q . . .
 +
. . . Q .
 +
Q . . . .
 +
. . Q . .
 +
----------
 +
. . . . Q
 +
. . Q . .
 +
Q . . . .
 +
. . . Q .
 +
. Q . . .
 +
10
 +
 
 +
(Note that the solutions below are all rotations of the same solution!)
 +
java Hw5_2_printSolutions 6
 +
------------
 +
. Q . . . .
 +
. . . Q . .
 +
. . . . . Q
 +
Q . . . . .
 +
. . Q . . .
 +
. . . . Q .
 +
------------
 +
. . Q . . .
 +
. . . . . Q
 +
. Q . . . .
 +
. . . . Q .
 +
Q . . . . .
 +
. . . Q . .
 +
------------
 +
. . . Q . .
 +
Q . . . . .
 +
. . . . Q .
 +
. Q . . . .
 +
. . . . . Q
 +
. . Q . . .
 +
------------
 +
. . . . Q .
 +
. . Q . . .
 +
Q . . . . .
 +
. . . . . Q
 +
. . . Q . .
 +
. Q . . . .
 +
4
 +
 
 +
java Hw5_2_printSolutions 4
 +
--------
 +
. Q . .
 +
. . . Q
 +
Q . . .
 +
. . Q .
 +
--------
 +
. . Q .
 +
Q . . .
 +
. . . Q
 +
. Q . .  
 +
2
 +
 
 +
</source>
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
[[Category:CSC212]][[Category:Homework]]

Latest revision as of 18:45, 12 November 2014

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



This assignment is due Friday (note the different day) Oct. 31st, at 11:55 p.m.


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. By returning, I mean either return with a return statement, or an ArrayList that is passed as a parameter, or an ArrayList that is a member variable of the class.
  • 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.
  • Your program should get N, the dimension of the array, and the key from the command line. Here's the code you should use:


     public static void main(String[] args) {
		if ( args.length == 0 ) {
			System.out.println( "Syntax: javac  Hw5_1  N  key" );
			return;
		}
		int N = Integer.parseInt( args[0] );
		int key = Integer.parseInt( args[1] );
    }


Note

  • If you are using Eclipse (which I hope you are), then passing parameters on the command line is a bit tricky, though totally possible. Here's how you do would do it. First click on the little black down arrow next to the Green Circle/White Triangle icon (Run icon) you click to run your programs.


EclipseRunConfiguration.png

  • Make sure your program is the one currently highlighted in the list, and click on Run Configurations.
  • Click on the Arguments tab, and enter N and the key in the Program Arguments window ("20 24" in this case).
  • Run your program. From then on, whenever you press the run-icon it will use these two numbers for N and key. If you want to change them, go through these same two steps again.


EclipseRunConfiguration2.png


  • Your output should be sorted. To sort an ArrayList of integers, you can use the Collections library, as illustrated below:


import java.util.Collections;

...

     ArrayList<Integer> indexes = new ArrayList<Integers>();

     // add some ints to the array
     ...

     // sort the ArrayList
     Collections.sort(indexes);


  • 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.
  • Call your program Hw5_2.java.
  • The output of your program should just be an integer number representing the number of solutions.
  • Your program will get N from the command line, as in:
 java Hw5_2  20
which will compute the total number of different ways we can organize 20 queens on a 20x20 chessboard.
  • Submit your program to Moodle, Homework 5, Problem 2.



Some Solutions


  • I modified the solution program to make it display the different solutions found:
java Hw5_2_printSolutions 4
--------
. Q . . 
. . . Q 
Q . . . 
. . Q . 
--------
. . Q . 
Q . . . 
. . . Q 
. Q . . 
2

java Hw5_2_printSolutions 5
----------
Q . . . . 
. . Q . . 
. . . . Q 
. Q . . . 
. . . Q . 
----------
Q . . . . 
. . . Q . 
. Q . . . 
. . . . Q 
. . Q . . 
----------
. Q . . . 
. . . Q . 
Q . . . . 
. . Q . . 
. . . . Q 
----------
. Q . . . 
. . . . Q 
. . Q . . 
Q . . . . 
. . . Q . 
----------
. . Q . . 
Q . . . . 
. . . Q . 
. Q . . . 
. . . . Q 
----------
. . Q . . 
. . . . Q 
. Q . . . 
. . . Q . 
Q . . . . 
----------
. . . Q . 
Q . . . . 
. . Q . . 
. . . . Q 
. Q . . . 
----------
. . . Q . 
. Q . . . 
. . . . Q 
. . Q . . 
Q . . . . 
----------
. . . . Q 
. Q . . . 
. . . Q . 
Q . . . . 
. . Q . . 
----------
. . . . Q 
. . Q . . 
Q . . . . 
. . . Q . 
. Q . . . 
10

(Note that the solutions below are all rotations of the same solution!)
java Hw5_2_printSolutions 6
------------
. Q . . . . 
. . . Q . . 
. . . . . Q 
Q . . . . . 
. . Q . . . 
. . . . Q . 
------------
. . Q . . . 
. . . . . Q 
. Q . . . . 
. . . . Q . 
Q . . . . . 
. . . Q . . 
------------
. . . Q . . 
Q . . . . . 
. . . . Q . 
. Q . . . . 
. . . . . Q 
. . Q . . . 
------------
. . . . Q . 
. . Q . . . 
Q . . . . . 
. . . . . Q 
. . . Q . . 
. Q . . . . 
4

java Hw5_2_printSolutions 4
--------
. Q . . 
. . . Q 
Q . . . 
. . Q . 
--------
. . Q . 
Q . . . 
. . . Q 
. Q . . 
2










Retrieved from "http://dominiquethiebaut.com/dftwiki3/index.php?title=CSC212_Homework_5_2014&oldid=24201"