UNM Computer Science Department

Instructions: Answer exactly one question on each of the seven courses (451, 460, 461, 481, 500, 530, 580). Each question is labeled with the course it applies to. Answering five questions correctly is a sure pass.

1. (451) What does it mean when we say that a Prolog program can be run forwards or backwards? Write the Prolog program for list append and show how you can use it to append two lists or to find all the lists that are prefixes of another list.

2. (451) ML uses type inference. What does this mean? Consider this Scheme function:

(define mapcar
 (lambda (f lst)
   (if (null? lst)
       '()
       (cons (f (car lst)) (mapcar f (cdr lst))))))

Show what type inferencing can be done on this function.

3. (460) In very large software projects (hundreds of thousands of lines of code) less then 10% of the effort goes into writing code. How is the rest of the effort spent? Be specific and list all of the important activities that go into a software project. Also give a rough estimate of the percent of time spent on each activity (these numbers do not have to precise but we will look for ballpark correctness).

4. (460) What is the spiral model of the software development process? In what ways is it an improvement of the waterfall model?

5. (461) Consider the following sorting algorithm

void sort( int arr[], int size ) {
    if( size <= 2 ) {
        if( arr[0] > arr[1] ) {
            int temp = arr[0]; arr[0] = arr[1]; arr[1] = temp;
        }
        return;
    }
    ...
}

Answer these questions:

6. (461) Consider the following function.

int Lsum(int n) {
  int i, sum;
  sum = 0;
  for (i = 0; i < n; i++)
    sum = sum + i;
  return sum * sum;
}

int f(int n) {
  if (n < 5)
    return 2 * n;
  else
    return 3 * f(n-1) + Lsum(n);
}

Express as a function of n:

7. (481) We can link file blocks together or we can use an indirect block to figure out where the next block in the file is. Assume you have a file system with 4K byte disk blocks and physical disk block numbers are four bytes long. How many disk accesses will it take to access byte 250,000 in a file using an indirect block and using linked blocks. Show you work with comments so we can understand what you did.

8. (481) A protection matrix is often used as a model for protection in an operating system. We have objects to be protected and subjects that wish to perform operations on objects. In a protection matrix each column is labeled with an object and each row is labeled with a subject.

9. (500) The following problem, which when stated as a theorem is the famous four-color theorem, is considered by computer scientists to be "easy," even though its proof took over 100 years to discover, the proof is quite long, and even today some mathematicians have doubts about the correctness of the proof.

On the other hand, the problem:

is considered "hard," even though there is an (admittedly inefficient) computer program of less than 100 lines that solves the problem.

Explain why computer scientists consider the first problem "easy" and the second problem "hard".

10. (500) Let M₁ and M₂ be Turing machines. Is the question "Is L(M₁) Í L(M₂)" a question to which we can answer

Prove your answers.

How does your answer change, if it does change, if you are promised that the Turing machines M₁ and M₂ are guaranteed to halt on all inputs?

11. (530) Consider a set or "cloud" of N experimental data points in m-dimensional Euclidean space,

x₁, x₂, …, x_N.

You wish to see how these points are distributed in m-space, but your plotter only displays 2-dimensions. So you want to construct a 2´ m "projection" matrix such that:

[ y_i = Px_i ]

where:

x_i is m´1 and is the original data point

y_i is 2´1 and is the projected data point

P is 2´m

That is, let y_i

Now assume you know K which is the covariance matrix of the N experimental points in m-space.

12. (530) 3 horses run a race. A bookie offers 5-for-2 odds on each of the horses. That is: for every $2 you bet, he returns a total of $5 if your horse wins. Of course, if your horse loses, he keeps all the money. The true odds on the horses winning are: [P(h₁) = ½ P(h₂) = ¼ P(h₃) = ¼ ] But we don't know the real odds and we pick horses at random.

13. (580) Describe the Factory Method pattern. What does it do, when it is useful, what are the objects that take part in it and what are their interfaces?

14. (580) Java allows only single inheritance of implementation but allows multiple inheritance of interfaces. Give some reasons why you think they made the decision to do this.