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

In This Section:


UNM Computer Science Master's Examination

March 29, 1997

This test is in-class, closed book and closed notes. There are two questions on each of the seven courses: 451, 460, 461, 481, 500, 530, and 580. Answer one question about each course. You have 3 hours to complete the exam, which translates into 25 minutes per question.

  1. (451) Write PROLOG code to reverse a list and print it out.
  2. (451) Without using CLOS, how might you build an object-oriented environment on top of Scheme or Common Lisp?
  3. (460) What is the waterfall model of the software development process? Describe the main steps in the waterfall model. What is the major problem that has been found with the waterfall model? Describe one other model of the software development process and describe how it improves upon the waterfall model.
  4. (460) What does a configuration control system do? Why is configuration control important to software maintenance?
  5. (461) You are given a line and a set P of points in the plane. The problem is to decide whether the given line intersects any of the n(n-1)/2 segments formed by any pair of points in P.

    6. Show how to solve this problem in O(n log n) time by reducing it in linear time to a couple of standard problems in plane geometry.

  6. (461) Consider the following algorithm. 
    Rand_Perm(A[], N)
    for(i=1; i <= N-1; i++)
        u = random(i,N)
        swap(A, i, u) /* swap A[i] and A[u] */
    end_for
end

    Assume that random(a,b) produces a uniformly distributed random integer between a and b, inclusive.

    1. Assume that the array A passed to Rand_Perm is such that A[i]==i, 1 <= i <= N. Prove that Rand_Perm produces in the array A every permutation of the integers from 1 to N with equal probability.
    2. Use Rand_Perm to devise a procedure that generates uniformly at random a subset of {1,...,N} of size k; that is, your procedure should generate only subsets of size k and be such that every subset of size k is generated with the same probability.
  7. (481) Describe what it means for two processes to be in a producer-consumer relationship. Show the outline of the code for the producer and the consumer. You can make one of two assumptions: (1) that the producer and the consumer share memory and synchronize with semaphores or (2) that the producer and consumer communicate with messages. Give a realistic example of a producer-consumer relationship in an operating system.
  8. (481) What is a disk cache? What are its advantages? Compare the effectiveness of a disk cache in speeding up file reading and file writing. Compare a disk cache with a RAM disk: how are they related? How are they different?
  9. (500) It is known that the problem known as Digraph Reachability (DR) is complete (under logspace reductions) for NLOGSPACE. (An instance of this problem is given by a directed graph and two distinguished vertices, x and y; the question is whether there exists a path from x to y in the digraph.) Use DR to prove that 2-UNSAT is also (logspace)-complete for NLOGSPACE; that is, prove membership of 2-UNSAT in NLOGSPACE and show that you can reduce DR to 2-UNSAT in logspace. (An instance of 2-UNSAT is a collection of clauses of 2 literals each; the question is whether the collection is unsatisfiable.)
  10. (500) It is well known that Vertex Cover (VC) is NP-complete. (An instance of this problem is given by an undirected graph G=(V,E) and a bound B < |V|; the question is whether there exists a subset V' of V with at most B vertices such that V' is a cover for G, i.e., such that each edge in E has at least one of its endpoints in V'.) Does VC remain NP-complete if we modify it to require that the subset V' be an exact cover for G, i.e., be such that every edge in E has exactly one of its endpoints in V'?
  11. (530) Find 2 orthonormal polynomials on the interval, [1,2]
  12. (530) Assume you have a die with 6 sides numbered 1 - 6. And you have another die with 4 sides (a tetrahedron), numbered 1 - 4. Let X be the random variable that is the sum of the outcomes of the 2 dice.
    1. What is the density function for X?
    2. What is the mean of X?
  13. (580) Give three design patterns where indirection is a basic idea in the pattern.
  14. (580) What is the difference between implementation inheritance and interface inheritance? What is the main advantage of each one? Which one is most closely associated with object composition and why?


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