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.

(451)

Standard ML of New Jersey claims to be a language where run-time crashes are eliminated. It attempts to accomplish this security by strong typing and type inference.

1. What is strong typing in ML? Give examples, including showing things that cannot be done in ML.
2. What is type inference and how can it be used to eliminate potential runtime problems? Give examples.
3. Describe operator-overloading in ML (give at least two examples). How does operator-overloading relate to the notion of strong-typing in ML?

(451)

PROLOG is named for PROgramming in LOGic and is often cited as an instance of "declarative programming".

1. Describe the notion of "declarative programming".
2. Describe the "procedural semantics" of PROLOG (including the use of "!", the "cut" predicate).
3. Contrast a and b.

(460)

Discuss why it is important that professional societies such as the ACM should have a code of professional conduct which members should follow.

(460)

Coupling and cohesion are often considered to be fundamental design criteria independent of whatever design methodology (e.g. object-oriented design or top-down structured design) is used. Define what is meant by coupling and cohesion, list the advantages and disadvantages of each and tell why they are more fundamental criteria than any particular methodology.

(461)

Consider the following two (correct) programs for finding the height of a binary tree. (For this problem, height is defined to be the number of nodes on the longest path through the tree.) What are the running times of the two programs when run on complete binary trees with n = 2^m-1 nodes, in which each node has either zero or two children and all the leaves are the same distance from the root (that is, on perfectly balanced trees).

Do this problem by counting something specific (state what you are counting). That is, don't just do the computation using Q (). Make sure to express your final answers in terms of n, the number of nodes in the tree, and not m, the height of the tree.

Algorithm 1:

int height(Node* p) {
  if (p == NULL)
      return 0;
  else {
      int lheight = height(p->left);
      int rheight = height(p->right);
      if (lheight > rheight)
          return lheight + 1;
      else
          return rheight + 1;
  }
} // int height(Node* p)

Algorithm 2:

int height(Node* p) {
  if (p == NULL)
      return 0;
  else {
      if (height(p->left) > height(p->right))
          return height(p->left) + 1;
      else
          return height(p->right) + 1;
  }
} // int height(Node* p)

(461)

Consider the following function.

   int Lsum(int n){
      int sum;
      sum = 0;
      while (n > 0) {
         sum = sum + n;
         n = n / 5;        // integer divide
      }
      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:

a. The exact number of multiplications executed for a call to f;

b. The growth rate (big O, or Q ) of the value of the function f; and

c. The running time of the program that computes the value of the function f.

(481)

1. Explain the least-recently-used (LRU) page replacement algorithm.
2. Explain why it is hard to implement.
3. Describe a page replacement algorithm that is an approximation of LRU but the only hardware assistance it uses is a used bit. (Note: A used bit is a bit in each page table entry to tells if the page has been accessed since the last time you reset the bit. There are instructions to test, set and reset the used bit.)

(481)

1. Describe the scan algorithm (also called the elevator algorithm) for disk head scheduling.
2. Explain what advantage it has over the shortest-seek-time-first disk-head-scheduling algorithm.

(500)

1. Show that the following statement is false: If L is not regular, then: for all integers n, there exists a string w in L with |w|>n, such that for all decompositions of w = xyz with |xy|<n and |y|>0 there exists a non-negative integer i such that xyⁱz is not in L
2. Let L be the language of all Turing machines M such that M never attempts to move M’s head to the left off the left end of the tape on any input. Show that L is not recursive (that is, decidable). (that is, show that {<M> | M never moves its head to the left of where it starts on the tape} is a not a recursive (that is, decidable) language).

(500)

R is the class of decision problems that can be solved in polynomial time by a one-sided probabilistic algorithm. Formally, a problem is in R if there exists a probabilistic algorithm (e.g., a random Turing machine) A, a polynomial p(), and a constant e£ 1 such that, for any instance x of the problem:

• if x is a yes instance, then A accepts x in at most p(|x|) steps with probability at least e; and
• if x is a no instance, then A always rejects x in at most p(|x|) steps.

Prove that the class R is closed under intersection; that is, prove that, if problems P1 and P2 both belong to R, then problem P3=(P1 intersect P2) also does, where (P1 intersect P2) is defined as having yes instances that are yes instances of both P1 and P2, and having no instances that are no instances of P1 or of P2 (or both).

(530)

Consider a 2-class pattern recognition problem with classes A and B and the following class-conditional probability density functions [ p(x|A) = 1/L for 0 £ x £ L ] and [ p(x|B) = K· ( 1 - x/L ) for 0 £ x £ L ] Let P(A) = 2P(B) be the a-priori probabilities.

1. What does K have to be?
2. What is your maximum likelihood estimate for L? Is there something a bit unusual about this estimate?
3. What is P(A)?
4. What is the optimum decision function?
5. How will the sample x_i = 0.5 be classified?

(530)

Consider Q to be the set of all real quadratic polynomials in t on the interval, [0,1]. Consider normal polynomial addition and multiplication. We can consider Q to be a vector space.

1. What is the field Q is defined over?
2. What is the dimension of Q?
3. Give a basis for Q.
4. Is your basis orthogonal? normal?

Consider the multiplication of each element of Q by 2 + 3t, to produce elements of C, a set of cubic polynomials.

1. Is C a vector space?
2. If so, what is its dimension? What is a basis?
3. Can this mapping from Q to C be represented as a matrix multiplication?
4. Is the mapping from Q to C a linear transformation?

(580)

Consider parameterized types (like Ada generics or C++ templates) and inheritance. They both accomplish some of the same goals.

1. What are the similarities between parameterized types and inheritance?
2. What are the differences?
3. What are the advantages of each? How would you decide, in a particular situation, which one to use?
4. Give an example of a pattern that can be implemented with either parameterized types or inheritance. Sketch out the two implementations.
5. Describe in which situations you would use each implementation.

(580)

The C++ Standard Library defines several container classes. There are three sequence containers: vector, deque, and list. A vector is implemented with a C++ array, which is expanded dynamically as needed. A deque is implemented with a linked list of fixed-size arrays where new arrays are added to the list as needed. A list is implemented as a doubly linked list. There are four associative containers (set, multiset, map, and mulitmap) all implemented as red-black trees. A set can tell you if an object is contained in the set. A multiset is similar but allows duplicates so can tell you how many of an object it contains. A map allows you to lookup arbitrary objects using a key object (hence is essentially a set of <key,value> pairs). A multimap is like a map but allows multiple values for a single key. In addition, the Standard Library defines the stack, queue, and priority queue containers which are implemented using the other sequence containers.

Create a reasonable class hierarchy from these containers and their implementations. Use inheritance where it makes sense and include abstract classes where necessary. Be sure you indicate which classes are abstract and which are concrete. Show the basic interface of each class (just the essential operations). Point out the design patterns you are using.