Exercises - Constructs
1. Write a program which guesses a number chosen by a user by asking yes/no questions of comparison. The user will be requested to pick a number from 1 to 32. The program will ask whether the number is greater than 16. If so, the program will ask whether the number is greater than 24, otherwise whether the number is greater than 8. Either way, the program will eliminate half the open possibilities. That is, on the first question, the number of possibilities drops from 32 to 16. On the next question the number of possibilites drops to 8. On the next question it drops to 4. Then to 2. On the last question it drops to 1, solving the problem.

It is not hard to see that this problem can be solved using 31 if-else if-else statements. You will solve it using 1 if-else in a for loop that repeats 5 times. This can be done by defining two variables called high and low: the first one keeps track of the highest number that is still possible and the second keeps track of the lowest number that is possible. Initially high is 32 and low is 1. If the answer to the first question is yes, low becomes 17 and high is unchanged. If the answer to the first question is no, high becomes 16 and low is unchanged. Your program changes low or high on each question until they are equal. At that point the number is known and can be output.

The GUI can have yes and no buttons. The questions can be asked in a JTextField. The number can be output in a JTextField.

2. Write a program that takes a number n as input and computes the percentage difference between n2/2 and 1+2+3+...+n. Let S be the sum. Then the percentage difference will be abs(S-n2/2)/S. Use a JTextField to input n and a JTextField to display the percentage difference.

3. The Fibonacci numbers are a sequence of integers where the 1st and 2nd numbers in sequence are both 1 and each of the remaining numbers in the sequence is the sum of the previous two. Expressed mathematically this is:
```   F(1) = 1
F(2) = 1
F(i) = F(i-1) + F(i-2)
```
Write a program to find the nth Fibonacci number. Use a JTextField for input and a 1 row JTextArea for output.

4. The factorial of a positive integer n is the product
```      n*(n-1)*(n-2)*...*1
```
Write a program that outputs the factorial of n. Use a JTextField for input and a 1 row JTextArea for output. How many zeros are at the end of the factorial of n as a function of n?

5. Stirling numbers of the first kind are a sequence of numbers that show up a lot in computer science. The number S(k,n) is the number of permutations of n numbers with exactly k disjoint cycles. The following is well known:
```   S(0,0) = 1
S(0,x) = 0  for x > 0
S(x,0) = 0  for x > 0
S(k,n) = S(k-1,n-1) - (n-1)*S(k,n-1)  otherwise
```
Write a program to find all S(k,n) for some fixed n. It should work like Pascal's triangle.

6. Write a program to find the cube root of a number

7. Write a program to find the fifth root of a number
8. Java has no exponentiation operator. Write a class that provides that service. Call the class Power and implement a method with the prototype
```   double power (double a, double b);
```
that returns ab. It will be used like this, for example:
```   Power p = new Power();
double x = p.power(3.2, 4.5);
```

9. Write a program that maps a year to a number expressing the world's population if population grows at the rate of 1.3% per year and the population is known to be 6,500,000,000 in 2006. The input could be a JTextField and the output could be a JTextField. Java has no exponentiation operator hence Math.log (take the logarithm) and Math.exp (take e to a power) will have to be used. Thus, ab is Math.exp(b*Math.log(a)).

10. The term wind chill was first coined by the Antarctic explorer Paul Siple in 1939 in his dissertation, Adaptation of the Explorer to the Climate of Antarctica where Siple proposed a formula for computing wind chill that remained in use for over 60 years. But, in the fall of 2001, the U.S. National Weather Service replaced Siple's formula with the following:
```   Wind chill = 35.74 + 0.6215*t - 35.75*v0.16 + 0.4275*t*v0.16.
```
where v is in the wind speed in miles per hour, and t is the temperature in degrees Fahrenheit. Siple's wind chill formula was:
```   Wind chill = 0.0817(3.71*v0.5 + 5.81 - 0.25*v)(t-91.4) + 91.4.
```

Write a program that computes and displays both wind chills from user-supplied floating point values of temperature and wind speed via two JTextFields. Again, since there is no exponentiation operator in Java, you will have to use Math.log and Math.exp.

11. Consider the following way to sort a list of integers:
```    Sort the first to next to last integers.
Find where in the list the last integer should go to make a sorted list.
Put the last integer there.
```
Write a program that implements this idea.

12. Craps is played with 2 dice. Each die is a small cube, marked on its faces with spots from one to six. Craps is played as a sequence of betting rounds. The first roll of the dice in a betting round is called the come out roll. If the sum of the spots on the come out roll is 2, 3, 7, 11, or 12, the round is over and a new betting round begins. Otherwise, the sum (one of 4, 5, 6, 8, 9, 10) is called the point and subsequent rolls follow until either point is made again or a 7 is rolled. In either case the betting round ends.

There are many ways to bet in craps but we concentrate here on the following, called the pass-line bet:

Pass Line Bet: You win if the come out roll is a natural (7, 11) and lose if it is craps (2, 3, 12). If a point is rolled (4, 5, 6, 8, 9, 10) it must be repeated before a 7 is thrown in order to win. If 7 is rolled before the point you lose.

Write a program that simulates many betting rounds and returns an estimate of the expected payoff (or loss) for repeatedly betting \$1 in a round. Estimate the average gain or loss per round. Plot a history of gain/loss. Assume the dice are completely fair and that the uniform random number generator of Java is perfect.

13. A factory which produces complex machinery on a single assembly line may need to take some care in planning which subassemblies or components are completed at what point on the line. For, if a component type is scheduled for completion after it is supposed to be installed then a problem will certainly exist. The problem is compounded by the fact that duplicates of the same component type may be used many times in assembling other components which themselves may be used many times and so on.

no component can be built before E components are, A components must wait until D and G components, and so on. If the component assemblies are scheduled in the following order

```
E, G, H, B, F, D, A, C, I, J
```
then all the components can be assembled successfully. Write a program to determine the order in which components are completed on an assembly line to prevent foul-ups as above. Input will be a list of dependencies given in a JTextArea - for example, each line may begin with a name (of the component) followed by a list of numbers representing components that this component depends on. The first line accounts for component 0, the next component 1 and so on.

Hint: An algorithm for solving this problem with recursion is as follows:

```   For all components v execute topo(v) given below

topo:
input: A component v - invoked as topo(v)
Check whether v is in the DONE state
If so, return
Check whether v is in the ERROR state
If so, print "Impossible" and exit
Change v's state to ERROR
For all the components w in the dependency list of v do the following:
Invoke topo(w)
Change v's state to DONE
Print "v"
Return
```
It is wise to build classes representing important objects such as component types.