Summer 2017, Test 2

1. Describe the expression (a − b * c) * (c * d − e) + f − (g − h) in Lisp's prefix form.

2. Use bottom-up algorithm to parse the expression from Problem 1,
build the dependency graph, explain which operations can be
performed in parallel first, which next, etc.

3. Describe what will be the quadruples generated by Java based on
the following program segment:

for(int i = 1; i <= n: i++) {c[i] = a[i] + b[i];}

4. Can we use parallel-for in computations of Problem 3? Explain
your answer.

5. Use the algorithm from Problem 3 to write a generic Java method
for computing the component-wise sum of two arrays. This method
should work for all possible numerical data types: int, short,
char, double, float.

6. Write a LISP function for computing the component-wise sum of
two lists. Trace it on the example of the lists '(1 10 100) and
'(2 20 200), the result should be '(3 30 300).

7. Write a Prolog program for computing the component-wise sum of
the two lists. Trace it on the same example as in Problem 5.

8. We all know how to find the largest element of an array. Use
Algol's call-by-name feature to write a method max(index, lower,
upper, expression) that would be able to compute the largest value
of a given expression when the index of this expression ranges
between the given lower bound and the given upper bound. Show,
step by step, how this method can be used to find the largest
value of the expression (0.1 * j) - sqr(0.1 * j), when j ranges
from 0 to 10.

9. Use the predicates parent, male, and female to describe the
concept of a brother. Test your definition on the following
database related to the Russian czar Peter I, the founder of St.
Petersburg, Russia:

parent(alexei, peter). parent(alexei, ivan). parent(alexei, sofia). male(peter). male(ivan). female(sofia). ? brother(X, Y).The goal is to find all the brothers. Show, step by step, how Prolog will do it.

10. Use wave algorithm to solve the following problem:

- we know that distance d is equal to velocity v multiplied by time t: d = v * t;
- we know that the cost c of the gas is proportional to the amount of fuel: c = 2.10 * f;
- we know that the amount of fuel f is proportional to the distance: f = d / 20.