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

In This Section:


Fall 1997 CS Master's Exam

October 25, 1997

Instructions: This test is in-class, closed book and closed notes. Each question is labeled with the course it applies to. Answer exactly one question on each of the seven courses (451, 460, 461, 481, 500, 530, 580). You have 3 hours to complete the exam, which translates into about 25 minutes per question.

  1. (451) PROLOG is named for PROgramming in LOGic. This suggests we ask in what sense PROLOG is a predicate calculus based theorem prover.
    1. In what ways is PROLOG a theorem prover for predicate calculus expressions?
    2. In what way does PROLOG fail to be a theorem prover?
  2. (451)
    1. Java claims to provide platform independence. How does Java accomplish this? Be specific and describe all the parts of the Java system that help to provide platform independence.
    2. Describe the Abstract Windowing Toolkit for Java. How does it provide platform independence?
  3. (451) Write an EBNF grammar that accepts a comma-separated sequence of one or more Social Security Numbers, allowing possible extra spaces surrounding commas. The grammar should reject numbers that aren’t formatted like SSN’s. Is your grammar suitable for predictive parsing? Why or why not?
  4. (451) Write, in Curried form, an ML function applyList that takes a list of functions and a value and applies each function to the value, producing a list of the results. What is applyList’s type?
  5. (460) Describe the concept of software quality. Many people believe the answer to improving software quality is testing. Why is this premise flawed? What is the correct way to improve software quality?
  6. (460) What is a CASE tool? What tasks typically are performed by a CASE tool? Ideally, what tasks should be performed by a case tool?
  7. (461) Consider the following algorithm. 
    function maxmin(S,k)
   if |S| <= k then return (max(S), min(S))
   else {S1,...,Sk} = partition(S,k)
   for i=1 to k do (mx(i),mn(i)) = maxmin(Si,k)
   return (max(mx(1),...,mx(k)),min(mn(1),...,mn(k)))

    The functions max (which returns the maximum of a set of no more than k elements), min (which returns the minimum of such a set), and partition (which divides a set into k subsets, as nearly equal in size as possible) are predefined.

    Express as a function of |S| and k:

    1. the number of calls to max and min;
    2. the number of calls to partition;
    3. the space used, assuming that each subset Si requires |Si| space and that all local storage is kept until return from the call.
  8. (461) Propose an algorithm that, given any simple (but non-convex) polygon, will partition it into convex pieces. It does not matter here how many convex pieces are produced nor what their shape is; your algorithm may add vertices on the boundary of the polygon or anywhere else. Your algorithm should run in time polynomial in the number of vertices of the original simple polygon (but the degree of the polynomial is unimportant).
  9. (481) Each file in an operating system will have a file descriptor. Explain the purpose of a file descriptor and list as many fields as you can think of that would be in a file descriptor. Be sure to explain what each field is used for.
  10. (481) Describe the low-level synchronization primitive called the spin lock. Show how to implement a spin lock using a hardware instruction called test and clear which tests a word in memory (to see if it is positive, negative or zero) and clears the word to zero in a single, uninterruptible atomic action.
  11. (500) The busy beaver problem is well known to be undecidable. (Recall that the busy beaver problem is the problem of designing, for each n, a Turing machine of n states—or a program of n instructions—that, on input 0, will eventually halt and will have run for the largest number of steps that any such TM can run. The TM is, for its size, the "busiest" TM we can design.) Yet it cannot be proved undecidable with Rice’s theorem. Carefully explain why that is the case.
  12. (500) Reductions normally used to prove NP-completeness are polynomial-time many-one transformations; yet some authors have use logarithmic-space many-one transformations and others have given reductions that use polynomial-time isomorphisms (bijective transformations). Explain why, under the current state of uncertainty regarding the complexity classes L (logarithmic space), P (polynomial time), and NP (nondeterministic polynomial time), we cannot hope to distinguish between the power of logarithmic-space reductions, polynomial-time many-one reductions, and polynomial-time isomorphisms.
  13. (530) Let x1 = [1,1,0], x2 = [0,1,1] and x3 = [1,0,1]. Express the vector z = [2,3,4] in terms of the basis set of x vectors.
  14. (530) A deck of 5 cards contains 2 red cards, 1 green card, 1 blue card and 1 black card. The deck is shuffled and dealt out one card at a time without replacement. Let Xi be the color of the ith card.
    1. How much information is there in knowing X1?
    2. How much information is there in knowing X2?
    3. Is H(X2|X1) > H(X3|X1,X2)? Why?
    4. What is H(X1,X2)?
  15. (580) A basic rule of software engineering is "Encapsulate what changes." Explain what this means and why it is true. Give an example of a design pattern that exemplified this rule.
  16. (580) Describe the Strategy pattern. What does it do, when it is useful, what are the objects that take part in it and what are their interfaces?


Home | Colloquia | Research | People
Current Students | Prospective Students | Companies | Visitors
Scholarships | Courses | Degrees | PIBBS
Computer Facilities | Jobs | Links

Contact Info:
(505) 277-3112 (phone)
(505) 277-6927 (fax)
Web site questions:
All other questions:

University of New Mexico
Department of Computer Science
Mail stop: MSC01 1130
1 University of New Mexico
Albuquerque, NM 87131-0001

UNM Home Page