Summer 2017, Final Exam

1a. Use bottom-up approach to parse the expression (a * b) + (c + d * e) * f + (g * h).

1b. Use the dependency graph to check which operations can be performed in parallel. If you had unlimited number of processors, how many steps do we need to compute the value of this expression?

1c. Describe this expression in LISP prefix form.

2. Fibonacci numbers are defined as follows: fib(0) = fib(1) = 1,
and fib(n) = fib(n − 1) + fib(n − 2).

2a. Write a Java method fib for computing Fibonacci numbers. In the main program, there is a following call to this method fib:

int c = fib(3);Assuming that the last byte of c was AED, describe, step-by-step, how memory will be allocated as we run this program.

2b. Write a Lisp function for computing fib(n). Show, step by step, how it will compute fib(3).

2c. Write a Prolog program for computing fib(n). Show how it will compute fib(3).

2d. What is the main inefficiency of all these implementations?

3. Let us consider the following program for component-wise
addition of one array to the other one:

for (int i = 0; i < a.length; i++) {a[i] += b[i];}

3a. Use pre- and post-conditions to prove that the program is
correct. *Hint:* For each value i, before we go into the i-th
loop, we have a[j] = a_{0}[j] + b[j] for all j < i and
a[j] = a_{0}[j] for all j ≥ i, where a_{0}[i]
are the original values of the array a[i].

3b. Write down the sequence of quadruples implementing this code.

3c. Explain why in Java, the memory allocated to each data type is a power of two: 1, 2, 4, 8, 16 bytes, etc.

3d. Can we use parallel-for in this program? Explain your answer.

3e. Write a generic Java method for performing the above operation, so that we should be able to use the same method for integers, doubles, etc.

4a. Describe Java integers in BNF and EBNF forms.

4b. Give an example of ambiguous and unambiguous BNF forms for Java integers.

4c. Why do we need BNF? Why do we need EBNF?

4d. Describe a state diagram that would enable a computer to recognize Java integers.

5. *Beyond Java:* for each of the following features,
describe its advantages and disadvantages, and give an example:

5a. declarative programming

5b. multiple assignment (as in Perl)

5c, guarded commands as an alternative to if-then-else statements

5d. Algol's call by name

5e. methods as parameters of other methods

5f. reflection

5g. wave algorithm