Homework 6 and Program 3

These assignments are due on Friday, March 15, the last day before Spring Break.

Turn in your answers to the following exercises no later than the beginning of class on Friday, March 15:

Do Exercises 5.2.8 and 5.2.9 from Section 5.2 of the textbook, pages 181 and 182. These exercises are in the section that covers QuickSort. You should think about how Quicksort and, in particular, the partitioning algorithms work.

Apply **both** the Lomuto partitioning (p. 159) algorithm and
the Hoare partitioning algorithm (p. 178) each of the following
sequences of numbers:

6 8 2 3 7 5 1 4 9 53 27 82 98 17 5 45 67 88 34 71 30 32

(This exercises asks you to one partitioning step, **not** to apply the full
QuickSort algorithm.)

Answer these two questions about the big integer multiplication algorithm:

- The algorithm was presented in terms of decimal (base-10) numbers, but computers usually use binary numbers. What change has to be made in the algorithm to apply to binary numbers? Does the run-time analysis also change?
- The algorithm is for multiplying two n-digit numbers, but often we have to multiply two numbers of very different sizes. How should the algorithm be changed to take that fact into account? How does the change affect the run time of the algorithm? Hint: Consider the multiplication of an n-digit number with a number that has less than or equal to n/2 digits.

The third programming assignment deals with the **closest pair** or **minimum distance**
problem for points in the plane. The problem is, given a list of points P_{0}, P_{1},
..., P_{n-1} in the plane, find the two points P_{i} and P_{j}, with
i ≠ j, such that the distance between the two points is minimized.

There is an obvious algorithm: Compute the distance between each possible pair of points and
keep track of which pair gives the smallest distance. This algorithm has run time Θ(n^{2}).
Section 5.4 in the textbook presents an algorithm that has run time Θ(n*log(n)).

You should write two programs to implement the two algorithms. Each program will read a list
of points from a file. The format of the files is as follows: The first line contains an integer
giving the number of points (n). After that, there are n lines, each containing two real numbers
giving the x and y coordinates of one of the points. You should run your programs on
some large data files and compare their run times. Some sample data files can be found in
*/classes/cs327/point-files*; some of the files are short and
some are long. **In addition to turning in your programs, you should turn in a short report
on your timing results.** Programs and report should be copied to your homework folder
in */classes/cs327/homework* no later than the morning of
Saturday, March 16. Alternatively, you can turn in the report in writing in class on
Friday.

**Some other requirements**: Your programs should take the name of the input file
as a command-line parameter, and it should use a *Scanner* to read the data from the
file. If you don't know how to do this, see the solutions to programming assignment 2 in
*/classes/cs327/DFS-BFS-solutions*.
The output from your programs should include both the minimum distance and a pair of
points that have that minimum distance.