### CSE 428: Exercises on Imperative Programming

Notes:

The superscript "(d)" stands for "difficult". Exercises similar to those marked with "(d)" might appear in candidacy exams, but not in the standard exams of CSE 428.

The superscript "(s)" stands for "solution provided". You can find the solution of these exercises here.

1. (s) In C and C++ the concepts of "expression" and "command" are not as separated as in other languages. For instance, --x is an expression, in the sense that it returns a result, and also a command, in the sense that it changes the state of x. (The exact meaning of --x is: evaluate x-1 and let v be the result, then store v in the location associated to x, and return the value v.) Expression whose evaluation might affect the state are called "expressions with side effects", and require special care by the programmer as they cannot be regarded as "pure values". Consider for instance the following (incorrect) definition of the factorial function:
2. ```   int fact(int x) {
if (x == 0)
return 1;
else return fact(--x) * x;
}
```
1. What is the result returned by the call fact(3) ?
2. Would the definition become correct if we substitute the command return fact(--x) * x; with {int y = x; return fact(--x) * y;} ?
3. Would the definition become correct if we substitute the expression fact(--x) * x; with x * fact(--x); ? (This last question is quite tricky and it is just for curiosity: it would not be given at the exam.)

3. (s) Consider the following command c:
```   begin
x, y : integer
in
x := 1;
y := 1;
begin
x : integer
in
x := 2;
y := x
end;
print(x + y)
end
```
Assume that env and s are the initial environment and state (immediately before the execution of c). Describe (using a drawing if you want):
1. The state and environment immediately after the execution of y := 1
2. The state and environment immediately after the execution of y := x
3. What is the value printed by the instruction print(x + y) ?
4. (s) Consider the following command
```   begin
x : integer
in x := 1;
begin
y : integer
in y := 2;
begin
x : integer
in x := y;
print(x)
end;
y := x;
print(y)
end
end
```
5. Assume that env and s are the initial environment and state. Describe (using a drawing if you want):
1. The state and environment immediately after the execution of y := 2
2. The state and environment immediately after the execution of x := y
3. What are the value printed by the instructions print(x) and print(y) ?

6. (s) Some imperative languages allow the so-called multiple assignment, namely a command of the form
```   x1 , x2 := e1 , e2
```
The meaning is: Given the initial environment env and state s, the final state is obtained as follows:
• let v1 be the result of the evaluation of e1 in env and s,
• let v2 be the result of the evaluation of e2 in env and s,
• put v1 and v2 in the locations associated to x1 and x2 respectively
1. Find a particular case of e1, e2 for which the above command is semantically different from the following concatenation: x1 := e1 ; x2 := e2
2. Assume having a language with blocks (and declarations inside blocks) and the (single) assignment, but not the multiple assignment. Write in this language a command semantically equivalent to x1 , x2 := e1 , e2. If you prefer, you can define a procedure
3. Use the multiple assignment to write a command which exchanges the values of two variables x and y (swap).
7. (s) The Fibonacci function can be defined recursively in Pascal as:
```   function fibo(n:integer):integer;
begin
if n < 0
then fibo := 0 /* error */
else if n = 0
then fibo := 0
else if n = 1
then fibo := 1
else fibo := fibo(n-1) + fibo(n-2)
end;
```
Write an equivalent iterative implementation of this function in C or in Pascal using only the basic commands of the mini-imperative language (while, if_then_else, assignment). Don't use either recursion or data structures like arrays and lists.
8. (s) The following is a recursive function in Pascal computing the Greatest Common Divisor of two positive natural numbers x and y, based on the Euclid's algorithm:
```   function GCD(x,y:integer):integer;
begin
if x < 1 or y < 1
then GCD := 0 /* error */
else if x = y
then GCD := x
else if x < y
then GCD(x,y-x)
else GCD(x-y,y)
end;
```
1. Is this function tail-recursive?
2. Write an equivalent iterative function in C or in Pascal using only the basic commands of the mini-imperative language (while, if_then_else, assignment). Don't use either recursion or data structures like arrays and lists.
9. (s) For each of the following three while commands, say for which initial values of x it eventually terminates. Assume that x is declared as an integer variable.
```   (1) while x > 0 do x := x - 1
(2) while not (x = 0) do  x := x - 1
(3) while x > 0 do x := x + 1
```
Note1: we say that a while command "terminates" if the condition eventually becomes false. This includes the case in which the condition is immediately false and the body is never executed.
Note2: do not consider the case of "anomalous termination" due to overflow of the value of x.
10. Exercise 4.2 in Sethi
11. Write a procedure which prints all the prime numbers from 2 to n (if n is smaller than 2, then it doesn't print anything). Remember that a number is prime if it is not divisible by any number except 1 and itself.)
12. Write a procedure which prints all the factorials of the numbers from 0 to n (if n is negative, then it doesn't print anything). Remember that the factorial of a natural number k is the product of all the numbers from 1 to k if k is positive, and it is 1 if k is 0.