=========================preview======================
(COMP251)COMP251_00F-final_sol.pdf
Back to COMP251 Login to download
======================================================
COMP251 Fall 2000 Final Exam Solution
Problem 1
(a)
In C++, "x" represents a Complex object while in Java, it represents a reference to a Complex object.

(b)
Cut is used to prune a PROLOG search tree: as a goal, it always succeedsand if the search has reached the "cut" point of a rule, it will continue with that rule and will not try other rules.


Example:
not(X) :- X, !, fail.
not(_).

(c)
A statement has side effects when it produces results that persist after it returns. e.g. modifying a global variable or printouts. SMLavoid side effects to variables by allowing only value binding: after a value is bound to a variable, it cannot be changed by any means.

(d)
structrured programs: flow of the program is evident from the program text; single entry/single exit

(e)
arrays: a seqeunce of homogeneous objects.


Problem 2
<Expr> ::= <Expr> + <Term> | <Expr> - <Term> | <Term>
<Term> ::= <Factor> ^ <Term> | <Factor>
<Factor> ::= (<Expr>) | <Id> | <Id>(<Expr>)
<Id> ::= a | b | c

Problem 3

(a)
2 1 1

(b)
2 2 2

(c)
2 1 2

(d)
2 2 2


Problem 4
(a)val foldL = fn : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'aval foldR = fn : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b
(b)
foldL append [ ] X;

(c)
foldR append [ ] X;


(e)
foldL: take a function "g", and accumulate the results when "g" works on
each item of the list progressively from the left. (Like a left-associative
operation)

foldR: take a function "g", and accumulate the results when "g" works oneach item of the list progressively from the right. (Like a right-associative operation)
In this case, right-associative foldR is more efficient because:
foldL append [ ] [[1,2], [3,4], [5,6], [7,8], [9,10]]
=> foldL append (append [ ] [1,2]) [[3,4], [5,6], ...]
=> foldL append (append (append [ ] [1,2]) [3,4]) [[5,6], ...]
=> ...
=> append ... (append (append (append [ ] [1,2]) [3,4]) [5,6]) ...
=> complexity = O(n1+(n1+n2)+(n1+n2+n3)+...)

where nj = length of j-th item list
foldR append [ ] [[1,2], [3,4], [5,6], [7,8], [9,10]]
=> append [1,2] (foldR append [ ] [[3,4], [5,6], [7,8], [9,10]])
=> append [1,2] (append [3,4] (foldR append [ ] [[5,6], [7,8], [9,10]]))
=> ...
=> append [1,2] (append [3,4] (append [5,6] ( ... (append [9,10] [ ]))))
=> complexity = O(n1+n2+n3+..)

Problem 5
Prolog loop: p:-p.
tree: p -> p -> p -> ...
Problem 6 (Java programming)
(a)
class A { A(int x,String y) { number = x; name = y; } private int number; private String name;
}
class B { B(int x,String y) { number = x; name = y; } private int number; private String name;
}
class arrayTest {
public static void main(String[] args) {
A a1 = new A(3,"hello");
A a2 = a1;
A a3 = a1;
B b1 = new B(3,"hello");
B b2 = b1;
B b3 = b1;
A[] a = {a1,a2,a3};

B[] b = {b1,b2,b3};
System.out.println(arrayEqual(a,b)); // false
A[] c = new A[1];
B[] d = new B[1];
System.out.println(arrayEqual(c,d)); // true

}