Exp ::= Num | Exp ^ Num | Exp * Exp | (Exp) Num ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9where Exp and Num are non-terminals and all the other symbols are terminal.
void p(int <parameter-passing method> x){
int temp;
temp = y;
y = y + 1;
x = temp + x + 2;
}
where y is a global variable of type integer.
Say what is the final value of y after the following fragment of code:
y = 0;
p(y);
under each of the following assumptions:
class list { //Implementation of a list (only the methods relevant for this exercise)
private:
int info;
list* next;
public:
list() //Constructor method. It creates a dummy fist element (field info = 0)
{
info = 0;
next = NULL;
}
list(int x, list* L) //Constructor method. It creates a list with info = x and rest L
{
info = x;
next = L;
}
void insert(int x) // Inserts x at the beginning of the list
{
next = new list(x,next);
}
};
void add_to_list(int k, list* L) // Adds k elements to the list
{
if (k<0)
cout << "Error: k should not be negative! \n";
else if (k==0)
cout << "value 0 reached \n";
else {
L->insert(k);
add_to_list(k-1,L);
}
}
////////////////////////////////////////////////////////////
int main()
{
list* L = new list();
add_to_list(3,L); //add 3 elements to L
// ...
}
////////////////////////////////////////////////////////////
Illustrate with a drawing the situation in memory (stack and heap)
at the moment in which the instruction cout << "value 0 reached \n"; is executed.
Please make explicit all the
informations stored in the activation records and in the (allocated part of the)
heap at that moment. Use arrows for pointers. Remember that in C++ there is no
static link
(there is no need for it since nested procedure declarations are not allowed).
For simplicity, you can represent in the stack only the activation records of
main() and of add_to_list(int). You can also omit the control link and
the temporaries.
fun reduce f v [] = v
| reduce f v (x::l) = f(x, reduce f v l);
Using reduce, define in ML the functions
fun exists l p = reduce ...; fun forall l p = reduce ...;
datatype 'a btree = leaf of 'a | node of ('a btree * 'a * 'a btree);
Define in ML a function enumerate : 'a btree -> int btree which,
given a binary tree t : 'a btree, gives as result a tree which represents
the enumeration of the nodes of t according to the traversal by levels
(aka breadth-first traversal)
of t.
For instance, if the tree t is
a
/ \
/ \
b c
/ \ / \
d e j k
/ \ / \
f g l m
/ \ / \
h i n o
then the result of enumerate(t) is
1
/ \
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \
8 9 10 11
/ \ / \
12 13 14 15
Question 7 (ML - Data types)
Given the datatype declaration of Question 6, define
a function numnodes: : 'a btree * int -> int which,
given a binary tree t : 'a btree and a positive number n,
returns the number of the nodes on the n-th level of t.
For instance, if t is the tree in Question 6, we should have
- numnodes(t,1);
val it = 1 : int
- numnodes(t,2);
val it = 2 : int
- numnodes(t,3);
val it = 4 : int
Question 8 (Prolog)
Define in Prolog a predicate solutions(M,N,X,Y)
which, given two natural number N and M,
it returns all possible pairs of natural numbers X and Y which
solve the system of equations
X + Y = M
X * Y = N
For instance, we should have
?- solutions(2,0,X,Y).
X = 0 Y = 2 ;
X = 2 Y = 0 ;
No
?- solutions(5,4,X,Y).
X = 1 Y = 4 ;
X = 4 Y = 1 ;
No
?- solutions(5,6,X,Y).
X = 2 Y = 3 ;
X = 3 Y = 2 ;
No
Note: the above system of equations can be solved in an analytic way,
by reducing it to a quadratic equation.
However, you should try to solve the exercise
in such a way that the solution can be generalized to any
system of equations (like for instance X^3 + X^2 + Y^4 = M and X*Y^3 = N).
The idea is to generate all possible
candidate pairs of natural numbers X and Y and then check whether
they satisfy the equations.
Question 9 (Prolog)
Define in Prolog a predicate flatten(L,K) which,
given a list L, returns in K the list
obtained by flattening L, namely the list
of all the non-list elements of L.
For instance, we should have
?- flatten([a,[b],[[c,d]]],L).
L = [a, b, c, d] ;
No
?- flatten([[1,2],[2,[3]],[],[[[4]]]],L).
L = [1, 2, 2, 3, 4] ;
No
Question 10 (Prolog)
Define in Prolog a predicate merge(L1,L2,K) which, given two
lists L1 and L2, returns in K a list which
contains exactly the elements of L1 and L2 alternated
in an arbitrary way, but in the same order
as they appear in L1 and L2.
For instance, we should have
?- merge([1,2], [3,4,5], K).
K = [1,2,3,4,5];
K = [1,3,2,4,5];
K = [1,3,4,2,5];
K = [1,3,4,5,2];
K = [3,1,2,4,5];
K = [3,1,4,2,5];
K = [3,1,4,5,2];
K = [3,4,1,2,5];
K = [3,4,1,5,2];
K = [3,4,5,1,2];
No