CSE413 Final Exam – Spring 1999 - Solutions

 

 

Question 1. (6 points) (a) What is the value of the following let expression if we evaluate the following lines with a Scheme interpreter?

(define x 10)

(define y 11)

(define z 12)

(let ((x 2)

(y (+ x 1))

(z (+ y x)))

(* x z))

SOLUTION

Step by Step : The x in the let is bound to 2, the (+ x 1) in the binding of y refers to the GLOBAL x (which has a value of 10), and so

y is bound to 11, z is similarly bound to 11 + 10 = 21.

Therefore the result of the let expression is (* x z) = (* 2 21) = 42

 

  1. What is the value of the above expression if let is replaced by let*?

If the let is replaced by let*, earlier bindings of variables in the let declaration part are used to evaluate later bindings. So the x is bound to 2, the x in the binding of y refers to the LOCAL x (which is bound to 2), and so y is bound to 3, similarly z is bound to

(+ 3 2), that is, 5. Now the result of the let* expression evaluates to (* 2 5) = 10

Question 2. (10 points) Write a Scheme function zip that takes a pair of lists as arguments and returns a list of pairs, where the kth pair in the result is formed from the kth elements of the argument lists. If one of the than the other, the extra elements of the longer list should be discarded.

lists is longer

Examples:

(zip ‘(1 2 3) ‘(a b c)) => ((1 a) (2 b) (3 c))

(zip ‘(1 2 3 4 5) ‘(a b)) => ((1 a) (2 b))

(zip ‘((1 2) (((3))) (4) 5) ‘(a b (c d) e ((f)))) =>

(((1 2) a) ((((3))) b) ((4) (c d)) (5 e))

SOLUTION

(define (zip list1 list2)

(if (null? list1) ()

(if (null? list2) ()

(cons (list (car list1) (car list2)) (zip (cdr list1) (cdr list2)))

)

)

)

Question 3. (9 points) Short answer questions about Java &c. Please keep your answers brief and to the point.

  1. The following code doesn’t compile. Why not? (The answer is a semantic error, not a misplaced brace or semicolon, or something like that.)

    2. public class NotHappy {

    private int a, b;

    public NotHappy( ) {

    a = 17; b = 42;

    }

    public int getSum( ) {

    return a+b;

    }

    public String toString( ) {

    return "NotHappy: a = " + a + " and b = " + b;

    }

    // test program for NotHappy

    public static void main (String [ ] args) {

    NotHappy nh = new NotHappy();

    System.out.println(nh + a + b);

    }

    }

     

    The semantic error we were looking for is that a and b are not static, and hence it is not semantically correct to refer to them from inside a static function in the class (which main is ).

     

     

     

  3. In both C++ and Java, a function declared in a subclass can override the definition of the same function in the parent class. In C++, functions that might be overridden must be declared with the keyword virtual; in Java, all functions are implicitly "virtual". C++ gives the programmer the option of having functions that are not virtual; the claim is that it is possible to implement non-virtual functions somewhat more efficiently than virtual ones. Is this true? If so, why?

    4. It is true that non-virtual functions can be implemented efficiently compared to virtual functions. If a function is not virtual, the call instruction can jump directly to the first instruction of the function. For virtual functions, usually some sort of indirect lookup is required to locate the function address in the class address table.

     

     

     

     

     

     

     

     

     

     

     

     

     

  4. The Java classes Container and Component both define elements of the user interface that can appear on the screen. What is the basic difference between these two classes?

Containers may hold other components.

Question 4. (10 points) Java classes can be used to implement data structures like linked lists and trees. For example, nodes in a binary tree could be represented as instances of the following class.

class TreeNode { // Binary tree node

Object data; // Data in this tree node

TreeNode left, right; // references to left and

// right subtrees (null

// if subtree is empty)

}

For this question, implement method equals for a binary tree class. If a and b are binary trees, a.equals(b) should yield true if the trees are the same (have the same structure, and have nodes that are equal, in the sense of equals). If the trees have different structures, or if two corresponding nodes in the trees are not equal, method equals should yield false. Feel free to create additional auxiliary functions if that is helpful.

class BinaryTree { // Binary tree object

private TreeNode head; // head node of the tree, or

// null if the tree is empty

The basic thing to realize here is that we are asking for a equals method for the BinaryTree class, not the TreeNode class. While writing this, we cannot assume that an appropriately defined equals method for the TreeNode class exists. Here’s the solution :

public boolean equals(Object t) {

if (t == null)

return false; // we are definitely not null!

if (!(t instanceof BinaryTree))

return false; // fails for any NON-BinaryTree.

BinaryTree t1 = (BinaryTree)t; //note: need to typecast

return equals_helper( head, t1.head);

}

private boolean equals_helper(TreeNode n1, TreeNode n2)

{

if (t1 == null && t2 == null)

return true;

else if ((t1 == null && t2 ! = null)

|| (t1 != null && t2 == null))

return false;

else return (t1.data.equals(t2.data) && equals_helper(t1.left, t2.left) && equals_helper(t1.right,t2.right));

}

}

Question 5. (12 points) Here is a grammar for a silly language containing a’s, parentheses, and commas.

S ::= ( L ) | a

L ::= L , S | S

  1. What are the terminal symbols in this grammar?

    2. a,<comma>, ( and )
  2. What are the non-terminal symbols in this grammar?

    3. S and L
  3. Give a complete derivation (parse tree) for the string

    4. (a, (a, a))

    S

    L

    L S

    S L

    L S

    S

     

    ( a , ( a , a ) )

    Question 5. (cont.)

    S ::= ( L ) | a

    L ::= L , S | S

  4. Write a recursive descent parser for this grammar in pseudo-Java. Be sure to get recursive function calls and other control structures correct, but you can be informal about scanning the input (i.e., it’s ok to write things like "if (the next symbol is *@#$%) … "). Ask if you’re not sure that you’ve got the right amount of detail.

// parse : S ::= (L) | a

void parse_S() {

if (next_symbol is ‘(‘)

{

scan over ‘(‘;

parse_L();

scan over ‘)’;}

else if (next sym is ‘a’)

scan over ‘a’;

}

// parse : L ::= L,S | S

void parse_L() {

parse_S();

while (next sym is ‘,’)

{

scan over ‘,’;

parse_S();

}

}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Question 6. (12 points) This question involves x86 assembly language. Your answers should be sequences of assembly language instructions that work as specified; you are not being asked to write compiler routines to generate the assembly language code.

For this question, assume the local symbol table contains the following variables with the specified offsets in the stack frame.

a

-8

b

+4

c

+8

Your answers don’t need to contain code that is as bad as the code generated by a naïve compiler. For example, if the question asked for an assembly language version of the assignment statement "a=a+a;", your answer could be something like this

mov eax,[ebp-8]

add eax,[ebp-8]

mov [ebp-8],eax

You don’t need to move the variable into eax, then push it, then pop it into ecx, etc.

Invent new label names when you need them in your code.

  1. The do-while loop in C works much like an ordinary while loop, except that the condition is tested after the body of the loop has been executed, not before. Write an x86 assembly-language translation of the following loop.

    2. do

    a = a – c;

    while (a > 0);

    L : mov eax, [ ebp –8]

    sub eax,[ebp + 8]

    mov [ebp–8],eax

    cmp eax, 0 ; is optional

    jg L

     

     

     

     

     

     

     

     

  2. , when evaluating

condition1 || condition2

the expression condition2 is not evaluated if condition1 is true, because if condition1 is true, the entire logical or must be true and there is no reason to evaluate condition2.

Write an x86 assembly-language program that has exactly the same effect as the following code, including short-circuit evaluation of the logical or (||).

if (a > b || a == c)

b = 0;

else

c = a * b;

 

mov eax, [ebp–8] ; if (a > b || a == c)

cmp eax,[ebp+4]

jg L1

cmp eax, [ebp+8]

jne L2

L1:

mov eax, 0 ; b = 0

mov [ebp+4], eax ; mov [ebp+4], 0 also works

jmp L3

L2:

mov eax,[ebp-8]

imul eax, [ebp+4] ; else c = a * b

mov [ebp+8],eax

L3:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Question 7. (1 point) (circle correct answer) CSE413 was a great course!!!!

  1. True
  2. False
  3. Not enough information to answer the question
  4. None of the above
  5. All of the above

Have a great summer!