Com Sci 221 --- Programming Languages Assignment #5 --- Winter 1995 Due Friday, 10 February

Last modified: Fri Feb 10 11:51:42 1995

Other versions:

You may do this problem in Pascal, C, Scheme or any other programming language(s) with the appropriate constructs. You may choose a different programming language for each of the two methods below.
Given a sequence of nonnegative integers (you may choose the representation of this sequence as an array, linked list, file of characters, etc.) find the largest. Produce two different programs, one based on the iteration
```
biggest := 0;

start before the 1st list element;

While there is more in the list do

         advance the list, assigning nextint the next
            integer value in the list;

         biggest := max(nextint, biggest)

end while
```
and the other based on the recursion
```
maxlist(list) =

    if (list = nil)

        then 0

        else max(first(list), maxlist(rest(list)))
```
Make the following 3 separate and independent modifications, in each case choosing the more appropriate of the two programs above as your starting point.
1. Allow negative integers in the input.
2. Make the program interactive, so that whenever the user types "m", the biggest integer input so far is output.
3. Generalize the program to compute the minmax of a tree. Minmax is an important game-theoretic function in which, at subsequent levels of a tree, alternate minima and maxima are taken to compute the effects of two players alternating turns, and each applying his or her best possible strategy.
Explain your method in each case, including the reasons for your choice of a starting point. As usual, you must devise a sequence of inputs that demonstrate the important qualities of your programs.
Do problems 3.4, 3.5, 3.6 on pp. 111-112 of the text.
Show how to implement a for-loop of the form
```
for i := E1 to E2 do SL
```
using assignments, while-loops, and conditionals. You may assume that E1 and E2 are pure integer expressions with no side effects, and that SL does not change the value of i. But, you must insure that your code will execute successfully under all reasonable circumstances. In particular, if E1 > E2, the for-loop must be equivalent to doing nothing. And, you must never assign a value to i that is less than E1 or greater than E2, because that might cause an overflow if the loop is running right up to the limits of the range of i. This problem is taken from problem 3.8 on p. 112 of the text, but you need not use Modula-2 in the solution. No program execution is required, just paperwork.
In principle, all computable functions can be computed using assignments, conditionals, and while-loops. Programs involving go-tos can be systematically translated into pure conditional/iterative programs. Show how to eliminate the go-tos in the following schematic program fragments. You will need to introduce new variables in some cases. Comment briefly in each case on the extent to which the structure of the original program with go-tos is or is not preserved in the translated version without go-tos.
1. ```
<alpha>;
If A then go to l;
<beta>;
l: <gamma>
```
2. ```
<alpha>;
l: <beta>;
If A then go to m;
<gamma>;
If B then go to l;
m: <delta>
```
3. ```
<alpha>;
While A do
<beta>;
If B then go to l;
<gamma>
end while;
<delta>;
l: <epsilon>
```

Comments