Spring 2002 Masters Exam: UNM Computer Science

Spring 2002 Masters Exam

Home > Degrees > Master's Degrees > Masters Examinations > Ms2002sp

In This Section:

University of New Mexico
Computer Science Department
Master's Examination
January 8, 2002
9 AM to 12 Noon

Answer exactly one question on each of the seven courses (451, 460, 461, 481, 500, 580). Do any two of the four 530 questions. Each question is labeled with the course it applies to. Write only on one side of the paper and answer each question on a different sheet of paper

451 Represent Scheme S-expressions in SML as follows:
For Scheme atoms, use
```
datatype Atom = Nil | Num of int | Id of string
```
For Scheme lists, use:
```
datatype 'a Sexp = Leaf of 'a | ConsNode of 'a Sexp * 'a Sexp
```
Write a function sexpprint to convert an S-expression into a character string in the standard Scheme output format.
451 Describe the basic tasks of an interpreter. Show the major modules of an interpreter, what each one does, and the data structures they share.
451 (Declarative languages)
1. Write the rules for a Prolog predicate palindrome(L), which means that the list L is a palindrome.
2. Write regular expressions and draw deterministic finite automata for the following two sets of strings over the alphabet 0, 1.
  1. The strings that do not end in 00.
  2. The strings containing exactly one occurrence of 00.
460 Consider the following description:
A class consists of a collection of students. Each student is represented by a name and a collection of scores. Each score has a weighting that is used to determine the final score for the class.
Identify the objects in this description and, using UML notation, draw a diagram that shows the relations between the objects.
460 Explain the relationship between software specification and software architecture. That is, describe the goals of these phases of software development and how that are inter-related.
461 Let f(x) be a function that computes a value of size in time.
Now consider the following function g(n) that makes calls to f(x).
```
   g(n)
   {
      if (n <= 1)
         return ( 7 )
      else
         return ( 3*g(n/2) + g(n/2) + f(n)*f(n) )
   }
```
Express each of the following as a function of .

a.

The growth rate of the running time of g(n).

b.

The growth rate of the value of g(n).

How can the implementation of g(n)--specifically the computation in the else clause--be rewritten to be more efficient? What is the running time of the new implementation?
461 Develop a linear-time algorithm to solve the following problem. Given a connected (undirected) graph , where each vertex is colored either red or green, and given vertices and , find a path from to that includes the fewest red vertices.
481 What is the purpose of a device driver? What hardware device does a device driver communicate with directly? Why are device drivers often structured with two levels? Give an example of a typical interface implemented by a device driver. Give the procedures in the interface, their arguments and a short explanation of each procedure and each argument.
481 Explain the difference between policy and mechanism in an operating system. Give two (substantially different) examples of the policy/mechanism split in an operating system.
500 The standard transition function for a Turing machine forces the machine to move its head left or right. Prove that allowing a Turing machine to leave its head stationary during some transitions does not increase its computational power.
500 What is wrong with this polynomial-time many-one reduction from Graph 3-Colorability to Minimum Vertex-Deletion Bipartite Subgraph (which, given a graph and a threshold , asks whether we can delete at most vertices from --and the associated edges--such that the resulting graph is bipartite)?
- Given an instance of G3C, just let the instance of MVDBS be itself, with bound $K=\lfloor\vert V\vert/3\rfloor$ .
Identify what makes the transformation fail and provide a specific instance of G3C that gets transformed into an instance with opposite answer.
530 The time at which a radioactive element decays is a continuous random variable with probability density function, . The half-life, , of an element is defined as the time required for one half of a sample to decay, .
1. Give an expression for the cumulative distribution function.
2. Give an approximate value for $\lambda$ .
[Hint: and .]
530 Let and be discrete random variables with marginal distributions, , and , and joint distribution, $p_{XY}(i,j)$ . Let $H_{XY} = -\sum_{i=1}^n \sum_{j=1}^m p_{XY}(i,j) \log p_{XY}(i,j)$ and $H_Y = -\sum_{j=1}^m p_Y(j) \log p_Y(j)$ . Prove that $H_{XY} = H_X + H_Y$ when and are statistically independent.
530 A two-state Markov chain has the following transition matrix:

$\displaystyle {\bf P}=\left[\begin{array}{cc} 1 - a & b\\ a & 1 - b \end{array}\right]$ "
1. Prove that P is stochastic when and .
2. Prove that $[b/(a+b), a/(a+b)]^{\rm T}$ is the limiting distribution for the Markov chain.
530 Let ${\bf c}=[-1,1]^{\rm T}$ and ${\bf b}=[1,1]^{\rm T}$ and

$\displaystyle {\bf A} = \left[\begin{array}{cc} 1 & 0\\ 0 & 1 \end{array}\right]$

Draw the feasible region and give the optimal basic feasible solution of the following linear programming problem: $\max {\bf c}^{\rm T}{\bf x}$ subject to ${\bf A}{\bf x} \leq {\bf b}$ and ${\bf x} \geq 0$ .
580 The idea of forces and the resolution of the forces is central to the idea of patterns. Explain what we mean by forces and the resolution of forces in the context of describing a pattern. Pick any pattern you are familiar with and describe the forces that apply and how the pattern resolves them.
580 Several patterns relate to the idea of a factory. Describe as many factory-related patterns as you know. A short explanation for each one is sufficient but you should be sure to describe how they are related and when you would use each one. Describe the general idea of a factory that unites them all. Some factory patterns can be considered variants of each other. For these patterns, just give them as separate patterns and explain in the text how they are actually variants of each other.