CS 327, Spring 2013
Homework 6 and Program 3

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

Homework 6

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:

  1. 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?
  2. 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.

Program 3

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 P0, P1, ..., Pn-1 in the plane, find the two points Pi and Pj, 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 Θ(n2). 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.