Doubling test for random grids. Develop a performance-testing client that takes an int val...

Doubling test for random grids. Develop a performance-testing client that takes an int value T from the command line and performs T trials of the following experie-ment: Use your client from exercise 1 to generate the connections in an N-by-N square grid, randomly oriented and in random order, then use UF to determine connectivity as in our development client, looping until all sites are connected. For each N, print the value of N, the average number of connections processed, and the ratio of the running time to the previous. Use your program to validate the hypotheses in the text that the running times for quick-find and quick-union are quadratic and weighted quick-union is near-linear. Note : As N doubles, the number of sites in the grid increases by a factor of 4, so expect a doubling factor of 16 for quadratic and 4 for linear.

exercise 1) that uses UF as in our development client to check connectivity and uses StdDraw to draw the connections as they are processed.

Exercise 1

Random grid generator. Write a program RandomGrid that takes an int value N from the command line, generates all the connections in an N-by-N grid, puts them in random order, randomly orients them (so that p q and q p are equally likely to occur), and prints the result to standard output. To randomly order the connections, use a RandomBag (see exercise 2). To encapsulate p and q in a single object, use the Connection nested class shown below. Package your program as two static methods: generate(), which takes N as argument and returns an array of connections, and mainO, which takes N from the command line, calls generate(), and iterates through the returned array to print the connections.

Exercise 2

Random bag. A random bag stores a collection of items and supports the following API:

Write a class RandomBag that implements this API. Note that this API is the same as for Bag, except for the adjective random, which indicates that the iteration should provide the items in random order (all N! permutations equally likely, for each iterator). Hint: Put the items in an array and randomize their order in the iterator’s constructor.