See Schedule for Due Date
CSIS-385: Homework 1
See schedule for due date.
Overview
Part 1: Implement an algorithm that randomly generates N points in a unit cube and then finds the two closest points. Output the distance between the two points and the x,y-values of the two points.
Part 2: Randomly generate N points, calculate the distance between every pair of points and generate histogram data.
Part 3: Describe in words or pseudocode (you do not have to actually implement it) an algorithm that takes a circle of radius R and N points in a unit cube as input and finds the optimal location such that the maximum number of points falls inside the circle.
Details
Part 1: The user should enter the value N, which is the number of random points to generate. The points should be in unit cube, which basically means that the x,y-values of the points must be floating point values between 0 and 1. The points should be stored in some data structure. For example, you could create a Class called Pair, i.e., for storing the x and y values, and the data structure could simply be an array of Pairs. Once the points have been generated use the nested loop we discussed in class to compare and compute the distance between all pairs of points. Keep track of the minimum distance and the two points that achieve that distance. After you’ve compared all pairs, output the minimum distance (a float) and the two points, i.e., two floating point pairs. Be sure to label your output.
Part 2:You can copy the code from Part 1, but be sure to create a completely new program. Again, the program should generate N random points in a unit cube. The program should compute the distance between all pairs of points and generate histogram data. A Histogram basically splits the data (all the computed distances) into bins and counts how many numbers are in each bin. Here is an example:
The histogram shows how many numbers (distances) fall into each bin. For example there are 77 distances between 0.0 and 0.1. Similarly, there are 32 distances between 0.1 and 0.2.
Your program doesn’t have to create a chart, it just has to generate the data. Your program should output the following data:
0.1 77
0.2 32
0.3 65
0.4 43
…
The first number is the bound of the bin and the second number is the count of how many distances fall into the bin.
Each bin should increase by a unit of 0.1. Since the points are in a unit cube, it is possible that two points could have a distance of sqrt(2) = 1.414, so your bins should go up to 1.5.
Part 3: The user inputs R, which is the radius of a circle. The user inputs N, which is the number of random points to generate in a unit cube. The center of the circle can be placed anywhere in the unit cube. The problem is that you have to find the optimal placement of the circle so that the most points fall within the circle. You can use brute-force computation, i.e., your algorithm doesn’t have to be efficient. Your algorithm should satisfy the 7 properties, but generous partial credit will be given for a good attempt even if its not correct.
Write a verbal or pseudocode description of your algorithm and answer the following questions:
- Is your algorithm correct? Explain what you think might be wrong with it.
- Is it precise? Explain
- Is it finite? Explain
- Is it general? Explain
- Is it deterministic? Explain
Submission
Print your 2 working programs and type-up your algorithm and answers to Part 3. Staple your work together and hand it in at the beginning of class on the due date. See online schedule. You do not have to electronically submit your programs, but be sure to save them because (i) we might use them later in the course and (ii) I may ask you to show them if I have any questions about your work.