empty set 1 1 2 1 3 2 2 3 3 1 2 3The order in which the subsets are generated does not matter.
To write this recursive function use the following idea of expressing
the problem with input n in terms of a smaller problem with input n-1.
To generate all subsets of {1, 2, ..., n}, first generate all subsets
of {1, 2, 3, ..., n-1}. Then generate all subsets of {1, 2, 3, ..., n-1}
a second time, but this time appending the number n to each subset generated.
What to submit: A printout of just the function genSubsets.
Solution: Here is the solution.
Some more details. You should fill the integer arrays with randomly
generated integers. To randomly generate an integer you can use the class
Random defined in java.util.
To learn more about this class see this page at java.sun.com.
To time your functions use the function System.currentTimeMillis().
Here is an example of the bubble sort
algorithm being timed.
To ensure that all of you are timing the same code, I would like you to start
with our textbook's implementations of three algorithms.
You can download them from here:
bubbleSort,
mergeSort, and
quickSort.
What to submit: (i) One program that contains your entire experiment. It should include the functions for the three sorting algorithms, it should include code for generating the arrays, and it should include code that calls and appropriately times the sorting functions. (ii) three plots, one for each sorting algorithm, and (iii) a brief write-up (about 10 sentences, at most) containing your observations.
What to submit: A printout of the updated program.
Solution:
import java.util.*; class hello { public static void main(String[] args) { // Defines x as a reference/pointer to a Vector object // The definition also specifies that each element // of the Vector is itself a Vector of Integer objects // So you should think of x as a 2-dimensional object Vector> x; // Allocates space for x by calling a constructor in // the Vector class that takes a single argument that // specifies the initial capacity of the Vector. // Now x contains 3 items, each item currently points // to nothing x = new Vector >(3); // Now each item in x is a reference/pointer to a Vector // of size 4. So now x can be thought of as a matrix // with 3 rows and 4 columns for(int i = 0; i < 3; i++) x.add(new Vector (4)); // Add code here that reads 12 integers input by a user. // Assume that the user inputs the 4 numbers in row 1 // followed by the 4 numbers in row 2, followed by the // 4 numbers in row 3 Scanner input = new Scanner(System.in); System.out.println("Enter 12 integers"); for(int i = 0; i < 3; i++) for(int j = 0; j < 4; j++) (x.get(i)).add(input.nextInt()); // Add code here to output the 12 numbers in the matrix. // The output is required to contain the 3 numbers in column // 1, followed by the 3 numbers in column 2, etc. for(int j = 0; j < 4; j++) { for(int i = 0; i < 3; i++) { System.out.print(x.get(i).get(j)); System.out.print(" "); } System.out.println(); } } }
11 3 4 9 34 6 9 18 2 7 8 1.Show how data is rearranged after the execution of partition. Also, indicate what the value returned by the function is.
public static int partition(int[] data, int left, int right) { int i, j; i = left; for(j = left; j <= right; j++) { if(data[j] < data[i]) { swap(data, i, j); i++; swap(data, i, j); } } return i; }
In 2-3 sentences, describe the algorithm that partition is using to achieve its task.
Solution: Shown below is thte arrangement of the elements in the array data, at the beginning of each execution of the for-loop. The values of i and j are also shown. The value returned by the function is left+9.
i 11 3 4 9 34 6 9 18 2 7 8 1. j i 11 3 4 9 34 6 9 18 2 7 8 1. j i 3 11 4 9 34 6 9 18 2 7 8 1. j i 3 4 11 9 34 6 9 18 2 7 8 1. j i 3 4 9 11 34 6 9 18 2 7 8 1. j i 3 4 9 11 34 6 9 18 2 7 8 1. j i 3 4 9 6 11 34 9 18 2 7 8 1. j i 3 4 9 6 9 11 34 18 2 7 8 1. j i 3 4 9 6 9 11 34 18 2 7 8 1. j i 3 4 9 6 9 2 11 18 34 7 8 1. j i 3 4 9 6 9 2 7 11 34 18 8 1. j i 3 4 9 6 9 2 7 8 11 18 34 1. j i 3 4 9 6 9 2 7 8 1 11 34 18.
The first element in data is chosen as the pivot and this element is always at the right end of the first block constructed by partion. In the above example, 11 is chosen as the pivot. The subarray data[left..i] is the first block, the subarray data[i+1..j] is the second block, and the subarray data[j+1..right] is the unprocessed block. In each iteration of the for-loop the next unprocessed element is processed and is either added to the first block or to the second block, depending on how it compares to the pivot element.