- Background
- Question 1: PositiveInteger.java
- Question 2: Buffon Needle Experiment
- Question 3: Simulation of Derangements Experiment
- Submission

# Background

Now that you have learned how to repeatedly perform the same actions over and over again via loops, you are in a position to use your computer to do something that computers have been used for since the very early days: **simulations**. In this assignment, you will warm up your new loop skills by programming three number theory concepts. Then, you’ll perform a Monte Carlo simulation and then simulate the Buffon Needle problem.

This is a long assignment, so you’ll have two weeks to complete it. Take it step by step!

### Goals of this assignment

- Use iteration to check complex properties of data
- Generate large numbers of random data points for analysis
- Compute probabilities based on results from repeated experiments

# Question 1: PositiveInteger.java

In this part of the assignment, you will write 3 methods to study some simple number theory concepts. To get started, create a file `PositiveInteger.java`

that houses the class `PositiveInteger`

. This class has one single instance variable of type `int`

called `num`

. We have provided you with the skeleton here, including a constructor as well as *stubs* for the methods you’ll need to fill out. Just type it out in your code. **DO NOT** change the method signatures in this class!

```
public class PositiveInteger {
private int num;
public PositiveInteger(int number){
num = number;
}
public boolean isPerfect() {
return false;
}
public boolean isAbundant() {
return false;
}
public boolean isNarcissistic() {
return false;
}
}
```

Study the constructor, and note how it creates a new `PositiveInteger`

by storing its single `int`

input in the field `num`

. This means that the methods that check the properties of this number don’t take any inputs, and that you perform these checks on the field `num`

.

###
isPerfect() **Autograded**

A positive integer is said to be *perfect* if it is equal to the sum of all its unique factors, excluding from the list of factors the number itself.
For example:

`6`

is a perfect number because its factors`1, 2, 3`

all sum together to`6`

.`28`

is a perfect number: its factors are`1, 2, 4, 7, 14`

, which sum to`28`

.`10`

is not a perfect number. Its factors are`1, 2, 5`

, which sum together to`8`

.`1`

is not a perfect number since it has no factors other than itself.

###
isAbundant() **Autograded**

A positive integer is said to be *abundant* if the sum of its unique factors (aside from the number itself) is greater than the number itself.
For example:

`12`

is abundant since`1+2+3+4+6 = 16 > 12`

.`15`

is not abundant since`1+3+5 = 9 < 15`

.`1`

is not abundant since it has no factors other than itself.

###
isNarcissistic() **Autograded**

A positive integer is said to be *narcissistic* if it is equal to the sum of its own digits each raised to the power of `n`

, where `n`

is the total number of digits.
For example:

`153`

is narcissistic because`1^3 + 5^3 + 3^3 = 1 + 125 + 27 = 153`

.- by definition, all single digit numbers are narcissistic (
`1^1 = 1`

,`2^1 = 2`

etc). `14`

is not narcissistic because`1^2 + 4^2 = 1 + 16 = 17 != 14`

.

## What to Submit for Question 1

`PositiveNumber.java`

, with the three specified methods completed. `isPerfect()`

, `isAbundant()`

, and `isNarcissistic()`

will all be graded.

#### General Notes for Question 1

- You can write a helper method if you like in order to simplify your code.
- Make sure to come up with some test cases for your code! We’ll test all sorts of different inputs for these methods. This would be a good opportunity to collaborate with your classmates.
- You can write a
`main`

method in this class if you’d like to use it to test your own code, but we’ll ignore it when grading. Nothing important should go here. - All three of these methods will be graded automatically. Therefore, you must not change the names, parameter lists, or return types of any of these provided methods.

# Question 2: Buffon Needle Experiment

This assignment idea is borrowed heavily from *Big Java* by Cay S. Horstmann. This question will have you implement a simulation as an exercise. Our goal is to estimate the value of `pi`

by modeling the process of randomly dropping needles on a lined piece of paper.

### Background on the Experiment

This experiment was devised by Comte Georges Louis Leclerc de Buffon (1707–1788), a French naturalist.

A needle of length `1`

inch is dropped onto paper that is ruled with lines 2 inches apart many, many times. When the needle drops onto a line, we count it as a hit; otherwise, it’s a miss.

By counting the number of times the dropped needle crosses a line (i.e. the number of `hits`

), as well as the total number of times the needle is dropped, we can calculate the quotient `totalDrops / hits`

. Surprisingly, the result actually approximates `pi`

given enough experiment trials. You can watch a video on this experiment here and read more about it here.

### Conducting the Experiment

Here’s how you can simulate a random individual needle drop. Since the needle has a fixed length of one inch, its position can be defined by two numbers: the y-coordinate of the low end of the needle, as well as the angle between the needle and the x-axis. We’ll call the low y-coordinate `y_low`

and the angle `alpha`

.

For each drop, you’ll need to generate a random value for `y_low`

between `0`

and `2`

inches. You’ll also need to generate a random value for `alpha`

between `0`

and `180`

degrees. Based on `y_low`

and `alpha`

, you will calculate `y_high`

as follows:

```
y_high = y_low + sin(alpha)
```

We say that the needle crosses the line (i.e. we have a `hit`

) when `y_high`

is at least `2`

.

###
runExperiment() **Autograded** **Manually Checked**

To estimate `pi`

, we’ll need to keep track of the number of `hits`

as well as the number of times we drop the needle (`totalDrops`

).

To help you write this experiment, we provide here a class called `Needle`

. `Needle`

has exactly one method (aside from the constructor) called `runExperiment(int totalDrops)`

. In this method, we simulate dropping the needle `totalDrops`

times and return the resulting quotient of `totalDrops`

/`hits`

. The skeleton for this class also has a `Random`

instance variable you should utilize. Refresh your memory on the Random documentation here.. No additional instance variables and methods are needed. Do not change the signature of `runExperiment()`

.

```
import java.util.*;
public class Needle {
private Random generator;
public Needle() {
generator = new Random();
}
public double runExperiment(int totalDrops) {
// implement
}
}
```

## What to Submit for Question 2

`Needle.java`

, with the specified method `runExperiment()`

completed. Your solution for `runExperiment()`

will be automatically graded, although we will verify that you are actually running the experiment and that you aren’t just explicitly returning the literal `3.14159...`

.

#### General Notes for Question 2

- You can write a helper method if you like in order to simplify your code.
- You can use
`Math.sin()`

to compute the`sin`

of an angle. Note that`Math.sin()`

expects an input in**radians**, not degrees! Make sure to convert if needed. - Test
`runExperiment`

with many different inputs values. Which inputs make the result come closer to`3.14159...`

? - You can write a
`main`

method in this class if you’d like to use it to test your own code, but we’ll ignore it when grading. Nothing important should go here.

# Question 3: Simulation of Derangements Experiment

Now you will simulate a famous *derangements* problem, which can be phrased as follows:

There are

`n`

people. Each of these people has a coat. They go to a bar to party. The bar asks them to leave their coats in a checking room. They go and get drunk and when they come back to pick up their coats it is hard for them to recognize theirs, so they just pick up a random coat.

There are two interesting probability questions we can ask about this situation.

- What is the probability of 0 people getting their coats?
- What is the average number (
*expected value*) of people who get their coats back?

We won’t use combinatorial reasoning to solve this problem–that kind of thing is for *boring courses* like CIT 592. *I’m kidding!* Mostly. Instead, we’ll follow our strategy from the needle problem and run many virtual experiments to gather data.

### What Does a Single Trial Look Like?

In our simulation, we assume that the people are numbered from `1`

to `n`

and the coats are also correspondingly numbered from `1`

to `n`

. A random arrangement of numbers from `1`

to `n`

then simulates a virtual “experiment”, where `n`

people picked up `n`

coats in a random manner.

For example, if we have `10`

people and the random arrangement is `[1, 8, 5, 6, 3, 4, 7, 10, 9, 2]`

then this means that person `1`

got coat `1`

, person `2`

got coat `8`

, and so on. In this individual experiment, we see that three people got their own coats back (person `1`

, person `7`

, and person `9`

).

If we want to answer our first question, we can generate many random arrangements and count the total number of trials where zero people got their own coats. To answer the second question, we can see how many coats are returned in each trial and take the average over all of those values from each trial.

### The Provided Framework

For this section of the homework, you will complete the implementation of the class `CoatExperimentSimulator`

. We have also provided a prewritten class called `RandomOrderGenerator`

whose methods you will use.

#### Random Order Generator

`RandomOrderGenerator`

has a method called `getRandomOrder(int n)`

that returns a random ordering (permutation) of the numbers from `1`

to `n`

(inclusive). In our simulation, this random arrangement of numbers indicates which person picked up which coat. In `RandomOrderGenerator`

we also provide a `main`

method that shows you how `getRandomOrder()`

is used.

```
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class RandomOrderGenerator {
public static int[] getRandomOrder(int outputLength) {
List<Integer> range = new ArrayList<>();
for (int i = 1; i <= outputLength; i++) {
range.add(i);
}
Collections.shuffle(range);
int[] outputArray = new int[outputLength];
for (int i = 0; i < outputLength; i++) {
outputArray[i] = range.get(i);
}
return outputArray;
}
public static void main(String[] args) {
// Print the results of RandomOrderGenerator.getRandomOrder(10);
// ten different times.
for (int i = 0; i < 10; i++) {
int[] randomOrder = RandomOrderGenerator.getRandomOrder(10);
System.out.print("order " + (i + 1) + ": [ ");
for (int j = 0; j < 10; j++) {
System.out.print(randomOrder[j] + " ");
}
System.out.println("]");
}
}
}
```

For example, the following would produce a random ordering of the numbers from `1`

to `10`

:

```
int[] randomArrangement = RandomOrderGenerator.getRandomOrder(10);
```

**Do not change anything in this file.** Just use the `getRandomOrder`

method in it. You can place this file directly into your Java project.

#### Coat Experiment Simulator

You have to write one class in the same project in order to do this HW question. It should be called `CoatExperimentSimulator.java`

. It should have one single instance variable called `numberOfPeople`

(please make sure your instance variable is called exactly this). The class must have a simple constructor, which is provided to you.

```
public class CoatExperimentSimulator {
private int numberOfPeople;
public CoatExperimentSimulator(int numPpl) {
numberOfPeople = numPpl;
}
public int numPplWhoGotTheirCoat(int[] permutation) {
return 0;
}
public int[] simulateCoatExperiment(int iterations) {
return null;
}
public double answerToQuestionOne(int[] results) {
return 0.0;
}
public double answerToQuestionTwo(int[] results) {
return 0.0;
}
}
```

###
numPplWhoGotTheirCoat() **Autograded**

This method determines the number of people who got their coat back given an array that represents a randomly generated arrangement. This permutation array will have the same length as the number of people in the experiment.

###
simulateCoatExperiment() **Autograded**

This method simulates the coat experiment multiple times and counts the number of people who got their coats back in each experiment. These counts should be stored in an array, which is returned by the method. The returned array should have its length be equal to the number of experiments run. The value at position `i`

in the returned array should represent the number of coats correctly returned in trial `i`

.

The input argument `iterations`

is likely to be a large number so that we have enough data to get a reliable result. Don’t get confused between what `iterations`

and what the field `numberOfPeople`

represent!

###
answerToQuestionOne() **Autograded**

Given the results of some number of iterations of the coats experiment, this computes the probability of `0`

people getting their coats back by taking the number of times `0`

people got their coats back and dividing that number by the total number of iterations run (i.e. the length of the input array).

###
answerToQuestionTwo() **Autograded**

Given the results of n iterations of the coats experiment, this computes the average number of people who get their coats back across all experiments. For example, if we run two trials, we might get the output `{1, 6}`

, in which case the average number of coats returned per trial is `3.5`

.

### Optional: What Are the Answers?

You can write yourself a `main`

method and print out the results of your previous work! **It is imperative, however, that your other methods should not print anything out at all.**

## What to Submit for Question 3

`CoatExperimentSimulator.java`

, with the specified methods `numPplWhoGotTheirCoat()`

, `simulateCoatExperiment()`

, `answerToQuestionOne()`

, `answerToQuestionTwo()`

. All of this will be automatically graded. Do not change any of the method signatures. **It is imperative that none of these default methods have any print statements!** The autograder will break.

#### General Notes for Question 3

- You can write a helper method if you like in order to simplify your code.
- Start small! Take this work one method at a time.
- Check with your classmates: do your probabilities & averages look about the same?

# Submission

Submit `PositiveNumber.java`

, `Needle.java`

, and `CoatExperimentSimulator.java`

.
**Ensure that your files do not have a package header!** Specifically, the first lines of your file should not read `package xyz`

or similar.

Please find these files locally on your file system. By default, they will be found in a folder called `eclipse_workspace`

, often in your user’s directory. You should select each of the files and upload them as files (**not** as a directory, and preferably not as a `.zip`

either). If you need help, please reach out on Piazza or in Office Hours.