- Write a
*recursive*function that takes a positive integer`n`and produces as output all subsets of the set {1, 2, 3, ..., n}. For example, if n = 3, then the output would beempty set 1 1 2 1 3 2 2 3 3 1 2 3

The 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. -
In this problem you are asked to perform experiments to compare the performance
of
`bubbleSort`,`mergeSort`, and`quickSort`. To perform the experiments, generate for each value of`n`, 10 integer arrays of size`n`, run all three sorting algorithms on each of the 10 arrays, time each run, and report the mean running time (taken over the 10 runs) for each algorithm, for each value of`n`. Do this for the following values of`n`: 1000, 2000, 3000, ..., 10,000 and make a plot of running times, one each for`bubbleSort`,`mergeSort`, and`quickSort`. Write about 10 sentences summarizing your observations, based on these plots. Consider the following questions:- Which implementation is fastest?
- How does the running time seem to grow, as a function of
`n`, for each implementation? Does the growth of the running time match your expectation? - Of
`mergeSort`and`quickSort`, which is faster?

**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. -
This program shows how to define a 2-dimensional
structure using Vectors.
Complete the program as per instructions given in the comments in the program.

**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(); } } } -
Here is a version of the
`partition`function that is different from the one given in the textbook and the one I presented in class. Suppose that the array`data`contains the sequence11 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.