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

In This Section:


Spring 1996 CS Master's Examinations

This test is in-class, closed notes. There are 6 groups of two questions each and 1 group of four questions; you are to solve one question in each group, for a total of 7 questions. (The groups are tex2html_wrap_inline27 for tex2html_wrap_inline29 and tex2html_wrap_inline31 .) \ You have 3 hours to complete the exam, or 25 minutes per question.

  1. A ``container'' object is an object that contains other objects. Examples include: lists, trees, sets, maps, etc. Container objects can cause typing problems in strongly typed languages. What is the C++ mechanism intended to solve the typing problem for container objects and how does it solve the problem?

    Most container objects have an ``iterator''; what is an iterator and what is it used for? Give an example of an iterator interface.

  2. Show how to represent sets as s-expressions and write functions to: create an empty set, add an element to a set, remove an element from a set, find the union of two sets and find the intersection of two sets.
  3. What is the waterfall model of the software development process? Describe its main steps. What is the major problem that has been found with the waterfall model? \ Describe another model of the software development process and how it improves upon the waterfall model.
  4. Your software company is about to switch to object-oriented design and analysis methodology from its current, presumably outdated, methodology. Everyone can list what the advantages of such a switch might be, but what might be the costs incurred in such a switch and what might your company lose in the process?
  5. Dijkstra's algorithm (for shortest path) and Prim's algorithm (for minimum cost spanning trees) are very similar. Both start with a set containing a single vertex and at each iteration add the ``best'' new vertex to the set. Both algorithms generate a spanning tree for the original undirected graph (consider the union of the edges selected at each iteration).

    Although very similar, the two algorithms differ in a significant way. Draw a graph (undirected and connected) and indicate a start vertex such that Dijkstra's algorithm does not produce a minimum cost spanning tree.

    Now suppose that we want to produce the minimax spanning tree, i.e., the spanning tree that minimizes the length of the longest edge present in the tree. (In other words, instead of summing up the lengths of all the edges in the tree to evaluate it, we simply take the length of the longest edge in the tree.) \ Show that Prim's algorithm, with no changes, returns the optimal spanning tree under this new measure; then revisit your example for Dijkstra's.

  6. Describe a linear-time algorithm that takes a binary search tree of arbitrary shape and constructs a perfectly balanced binary search tree. For simplicity, you may assume that the number of nodes in the tree is tex2html_wrap_inline35 , for some integer k ;SPMgt; 0.
  7. Compare and contrast: procedure call, system call, and context switch.

    What does it mean to dispatch a process? Describe in some detail what happens during a dispatch. How is a dispatch different from a context switch?

  8. Describe the layout of a page table entry (PTE) in a typical paging system. Make a reasonable assumptions about page size. Give the algorithm the hardware uses for each memory reference in this paging system. Be sure to describe the use of the translation look-aside buffer.
  9. Consider the set S of all r.e. languages. Which of the following subsets of S are also r.e.? (Prove your anwers.)
    1. The set of all r.e. languages that contain at least 10 strings.
    2. The set of all infinite r.e. languages.
  10. Consider the following version of the satisfiability problem. An instance of the problem is given by n variables and a set of 3-clauses over these variables, i.e, a set of triples of literals where each literal is either a variable or its complement; no variable appears more than once per clause. The question is whether there exists a truth assignment for the n variables such that every clause has 1 or 3 true literals.

    Either prove that this problem is NP-complete or give a polynomial-time algorithm to solve it.

  11. A deck of cards contains exactly 16 Aces, 8 Kings, 4 Queens, and 4 Jacks.
    • On the average, how many Yes/No questions must be answered to know the rank (J, Q, K, or A) of the first card drawn?
    • What is the probability the first card is an Ace, given that the second card (drawn without replacement) is a Jack?
    Now replace the first card drawn and reshuffle.
    • What is the probability the second card is of the same rank as the first?
    • What is the probability the second card is of higher rank than the first?
    • What is the probability the first card is an A, given that the second card is a J?
  12. Find a function on the interval [0,1] that is orthonormal to tex2html_wrap_inline49 .
  13. In the context of formal specifications, what do the terms ambiguity and contradiction mean? Give an example to illustrate each term.
  14. Consider the following code excerpt:

    excerpt19

    Develop a useful invariant for this code excerpt and show how to use it.

  15. Compare and constrast: a class library, a design pattern, and a framework.
  16. Describe the Observer design pattern. What are the components and their operations? When is it useful? \ What consequences does it have, that is, what is good and bad about using it?



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