Com S 541 -- Programming Languages I		    Handed out: Mar. 26, 1993
		HOMEWORK 13: Programming in SR

Due: March 31, 1993

		EXTRA CREDIT
These are all extra credit problems to explore programming in SR.
You can do these individually or in groups of any size.

1. Can you simulate a voting algorithm in SR?  That is, write a program
that has N voter processes, and have a concurrent statement that polls
the N voters for yes or no votes and terminates when at least N/2 responses
have been received.  Adapt the program to have the voters be resources,
and have the voting done using various communication mechanisms.
Try distributing the program.

2. The 3x+1 function takes a cardinal number, x, and if it is odd,
returns (3x+1)/2, and otherwise returns x/2.
Write a SR program to read a value of x, compute this function, and print the
result.  See the handout for I/O.  What is in the Interfaces directory
after you compile?

3. Call the 3x+1 function T.  The iterates of T are defined as usual;
that is, T^{(0)}(x) = x, and for all integers k > 0,
let T^{(k)}(x) = T(T^{(k-1)}(x)).
The sequence of iterates (x, T(x), T^{(2)}(x), ...) is called
the trajectory of x.
For example, the trajectory of 7 is:
	7, 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1, 2, 1, 2, 1, ...
The 3x+1 conjecture states that for each n > 0,
there is some k such that T^{(k)}(n) = 1.
Modify the program of problem 2 to print the
first subsequence of the trajectory of the input number that includes 1,
provided that the input is not a counter-example to the conjecture.
This is called the "trajectory of n to 1".
For example, for 7 the program should print (in some fashion):
	7 11 17 26 13 20 10 5 8 4 2 1
Try this on 27 and 703.

4.  One problem is that the numbers tend to get large.
You can try your hand at a infinite precision number resource to solve this.

5. Let max_value(n) be defined to be the maximum value reached in the
trajectory of n to 1.  Let total_stopping_time(n) be one less than the length
of the trajectory of n to 1.
We call max_value and total_stopping_time ``statistics''
of a number, since they summarize its trajectory.
An integer n >0 is a peak in a statistic f,
if and only if for all 0 < m < n, f(m) < f(n).
These numbers are called peaks because if one graphs the positive integers
on the x-axis and the value of the statistic on the y-axis,
then each peak will be a point higher than has been reached before.
For example, 3 is a peak in max_value.
Write a SR program to look for peaks in either max_value or
total_stopping_time.  The program should print out a list of peaks.
For example, for total_stopping_time the list should look something like.
	1 2 3 6 7 9 ...
(You should have some way of stopping the program.)
After a while the peaks come out more slowly.  Can you fix that?
You might try one or more of the following:
	(a) have the SR program save its results in a file so you don't have
		to watch it.  (Use the unix command nice to run your program.)
	(b) distribute the work among 2 or more computers.
	(c) have the program take checkpoints, so you don't lose any work
		when computers crash.
See ISU TR 89-22 for some ideas.  See also ISU TR92-01 for optimizations.
You can get the postscript for these by sending the mail message
	send TR TR89-22
or	send TR TR92-01
to almanac@cs.iastate.edu