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

In This Section:


Fall 1995 CS Master's Examinations

This test is in-class, closed book and closed notes. There are 6 groups of two questions each; you are to solve one question in each group. (The groups are simply questions tex2html_wrap_inline41 for tex2html_wrap_inline43 .) \ You have 3 hours to complete the exam, which translates into 30 minutes per question.

  1. (Algorithms/Data Structures) \ Consider the following algorithm for traversing a graph (directed or undirected) from a given start vertex v. The algorithm uses a queue with the ordinary Create(), Add(), Remove(), and IsEmpty() operations.

    excerpt9

    Assuming an adjacency list representation of the graph, do a worst-case analysis (time and space) of this algorithm. Note that this is not a standard breadth-first search traversal of the graph: how does it differ from one and what can you do to turn it into a standard breadth-frist search?

  2. (Algorithms/Data Structures) \ Consider the following C-like functions.

    excerpt14

    excerpt21

    1. Ignoring arithmetic precision, what is an exact closed form for f(n) as a function of n?
    2. Again ignoring arithmetic precision, what is the time complexity of f(n) as a function of n?
    3. How can the running time of this computation be improved significantly?
  3. (Theory of Computation) Give a deterministic finite automaton that accepts the set of all strings over tex2html_wrap_inline55 such that
    (i) the string has no leading 0s; and
    (ii) when considered as an integer, the string represents a multiple of 3.

    (The language consists of the strings tex2html_wrap_inline57 , 11, 110, 1001, 1100, 1111, 10010, 10101, etc.)

  4. (Theory of Computation) \ What is wrong with this reduction from G3C (graph 3-colorability) to Minimum Vertex-Deletion Bipartite Subgraph (delete at most K vertices such that the resulting graph is bipartite)?
    • Given an instance of G3C, i.e., a graph G=(V,E), just let the instance of MVDBS be G itself, with bound tex2html_wrap_inline65 .
    Identify what makes the transformation fail and provide a specific instance of G3C that gets transformed into an instance with opposite answer.
  5. (Operating systems) \ Assume that an operating system uses a typical paging system. Describe the steps that the system must take (in terms of the virtual memory subsystem) for each of these four events: process creation, process dispatch, page fault in a process, and process destruction.
  6. (Operating systems) \ A file system must, for each file, keep track of which blocks on disk contain the file data; this information is used in mapping logical block numbers to physical block numbers.
    1. What are logical and physical block numbers (in a single file)? What do we mean by mapping logical block numbers to physical block numbers?
    2. What is an indirect block in this context? a double indirect block?
    3. Make (and state) some reasonable assumptions about the disk system and figure out how many blocks would be mapped by a double indirect block.
  7. (Languages) \ Write a Lisp function that will traverse an arbitrary rooted, ordered tree in inorder. Define your own representation of trees as s-expressions.
  8. (Languages) \ What is ``currying'' in Scheme? Give a definition of a function curry that will curry any function of two arguments. Use curry and mapcar to write a function that adds 5 to each item in a list.
  9. (Software Engineering) \ Suppose that a word-processing system is to have the capability to create mathematical expressions (with square root signs, fractions, exponents, integrals, etc). Use this problem to illustrate the three stages of requirements, specifications, and architectural (high-level) design, clearly distinguishing between the three.
  10. (Software Engineering) \ What is regression testing? What is black box testing? What is white box testing? \ Explain the differences between unit testing, integration testing and acceptance testing.
  11. (Formal Specifications) \ Using any formal specification system you want, write a formal specification for a function that returns the greatest common divisor of two positive integers.
  12. (Formal Specifications) \ Write a meaningful invariant for this loop; of what use is your invariant? 
    for( i=0 ; i<n ; i++ ) {
    if (x > arr[i]) arr[i] = x
}



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