Final: Sample Questions

This page includes questions by the instructor (John Boyland) that may appear on the final.

The material on the exam will mainly come from Chapters 15-24 of the textbook, but you should be ready to answer questions from anywhere in the book. Consult the midterm study help. You should be ready to do any of the exercises from the book that do not require research. At least one of the exam questions will be an exercise from the book.

Conceptual Terms

You should be able to define and explain the following concepts:

Programming

Java

The interface Dictionary has the following methods: 

  int size();
  boolean isEmpty();
  Enumeration keys();
  Object get(Object key);
  Object put(Object key,Object value); // returns previous value (or null)
and the Enumeration interface has: 
    boolean hasMoreElements();
    Object nextElement();
Implement a class LinkedDictionary which implements this interface correctly using a linked list of key-value pairs. This may seem inefficient, but it is a well-known solution called an ``association list'' and is practical when the lists stay short.

Prolog

Suppose we represent a maze by a collection of facts such as: 

door(a,b).
door(b,c).
door(c,d).
door(d,e).
door(d,a).
Assume you can go either direction through a door.
  1. Write a predicate connected(X) that is true for any room X that has a door.
  2. Write a predicate path(X,Y,L) that is true of a list L if it represents a legal path from room X to room Y. (The fact that you can go either direction through a door makes this different from the lecture in week 11.) It is not required for path(X,Y,L) to unify L with all such paths if L is unbound. As in lecture, it may get caught making bigger and bigger paths going around cycles.
  3. Write a predicate path(X,Y,N,L) that unifies L with all paths of length =<N. It may assume that X,Y,N are all instantiated when the call is made, but cannot assume L is bound to anything.
  4. Write another routine shortest_path(X,Y,L) that unifies L with any shortest path from X to Y. There may be many such paths, or none at all. You may assume that any such path will have length =< the number of ``connected'' rooms; this can be proved easily in graph theory.

Language Concepts in Practice

Parameter Passing

(Questions on what the result of a program is using various parameter passing modes.)

Abstract and default methods

In Homework #8, you wrote an abstract class AbstractIntSet that had among its methods, one named ``find'' and an abstract method ``iterator''

  1. What does it mean to be an abstract class?
  2. Why do we have abstract classes?
  3. Why do abstract classes provide implementations (such as for find)?
  4. TreeIntSet inherits from AbstractIntSet and overrides find? Why does it inherit? Why does it override?
  5. LinkedIntSet inherits from AbstractIntSet but does not override find. Why not?
  6. Suppose we wrote a new implement of the IntSet interface that uses a sorted array of elements that grows as needed (using either an array or a java.util.ArrayList).
    1. Should it inherit from AbstractIntSet? Why or why not?
    2. Should it override find? Why or why not?
    3. Should it override toString? Why or why not?
    4. Why can't we inherit the add method from some other class?

Resolution and Unification

The basic engine in Prolog consists of solve, resolution and unify. Give the algorithm for the first two.

Answer: 

solve (goals) =
  if goals is empty then succeed()
  else 
    for each rule R
      solve(resolution(rename(R),goals))
    repeat on failure

resolution (head:conditions,first:rest)
  (unify (head,first))(conditions ++ rest)

optional:
succeed() =
  if user presses return then Done
  else if user presses ';' fail()

Suppose we have the following rules: 

parent(sandy,chris).
parent(pat,aidan).
parent(pat,sandy).
grandparent(X,Z) :- parent(X,Y), parent(Y,Z)
Show what happens when we run: 
solve([grandparent(A,B)])

Answer the following questions:

  1. Why does solve succeed when given an empty list of goals? What is the intuition?
  2. Why does solve rename the variables in the rule before passing it to resolution?
  3. Why does solve not rename the variables in the goals before passing it to resolution?
  4. Why does resolution only unify the head of the rule, not the whole thing?
  5. What happens in resolution when unify fails?
  6. Why do we apply the unifier to the rest of the rule and goal list?
  7. Why do we remove the first goal if unification succeeds?
  8. Why do we add the tail of the rule to the goal list?

More on Resolution and solving

In this section, we are working with a predicate for ``flattening'' a tree where internal nodes have the form branch(V,W) and leaves have the form leaf(X). The flattened form is a list of all the items that show up in leaves. The predicate uses a helper predicate flattenH that takes an extra accumulator list (for efficiency).
  1. Give the results of the following calls to unify:
    1. unify(flattenH(leaf(X1),L1,[X1|L1]),flattenH(T,[],[1,2,3]))
    2. unify(flattenH(branch(V2,W2),L2,N2),flattenH(T,[],[1,2,3]))
    3. unify(flattenH(leaf(X3),L3,[X3|L3]),flattenH(W2,[],M2))
  2. Using the previous calls, give the results of the following calls to resolution:
    1. resolution([flattenH(leaf(X1),L1,[X1|L1])], [flattenH(T,[],[1,2,3])]) 
    2. resolution([flattenH(branch(V2,W2),L2,N2),
            flattenH(W2,L2,M2),
            flattenH(V2,M2,N2)],
           [flattenH(T,[],[1,2,3])])

    3. resolution([flattenH(leaf(X3),L3,[X3|L3])],
           [flattenH(W2,[],M2), flattenH(V2,M2,[1,2,3])])
  3. Using the previous steps to give the whole proof tree trace up to the first success for the following call. Please trace every call to solve, resolution and unify, even ones that fail.
    solve([flattenH(T,[],[1,2,3])])
    Assume the program consists of only the following rules: 
    flattenH(leaf(X),L,[X|L]).
flattenH(branch(V,W),L,N) :- flattenH(W,L,M), flattenH(V,M,N).
  4. After this first success, the proof tree goes on forever without any more success. (Try it in Prolog!) Why?