Fall 2001 Masters Exam: UNM Computer Science

Fall 2001 Masters Exam

Home > Degrees > Master's Degrees > Masters Examinations > 2001xfallms

In This Section:

University of New Mexico
Computer Science Department
Master's Examination
9 AM to 12 noon on March 24, 2001

Instructions: Answer exactly one question on each of the seven courses (451, 460, 461, 481, 500, 530, 580). 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) Object-Orientation is an important design tool for modern programmers. Take four of the following languages (Lisp, SML-NJ, Prolog, Haskell, Beta, Smalltalk Java) and describe their utility as object-oriented tools. Be sure to cover issues such as single vs. multiple inheritance, type checking and inference, and the "naturalness" of the language for object-based design.
(451) Prolog is not a "true" logic language for a number of reasons. Give and explain three reasons why Prolog is not a true "logic programming" language. How would (or indeed, could) the semantics of Prolog need be changed to make it a true object-oriented language?
(460) Give some standard methods for finding objects in a system you are designing. Explain where these methods fit into the OO software development process. Do you only find objects in one step or is it spread over several steps?
(460) What is the methodology for testing, that is, what steps to you take, what constitutes each step, and what order do you do them in. By steps we means things like developing test cases. Give some methods for developing a good set of test cases.
(461) How many squares (of any integer size) are there in an NxN square grid? (e.g., a 1x1 grid has one square, a 2x2 grid has 5 squares, etc.) Give an exact, closed-form formula.
(461) With almost any data structure, it is possible to conduct an amortized analysis that shows that the cost of deletion amortizes to a constant. Give a specific example (use a simple data structure such as a priority queues, a BST, etc., where the real cost of deletion is larger than a constant) and discuss (i) why this will be true of just about any data structure and (ii) how one reconciles the obvious fact that deletion takes more than constant real time with the constant amortized time obtained in the analysis.
(481) A computer provides each process with 65,536 bytes of address space divided into pages of 4096 bytes. The compiler divides a program into 3 segments: a text segment of size 32,768 bytes, a data segment of size 16,386 bytes, and a stack segment of size 15,870 bytes. Will this program fit in the address space? If the page size were 512 bytes, would it fit? Show your work and explain what problems could arise.
(481) Suppose that a new disk technology makes disk access times so short that they are of the same order of magnitude as memory access times. What changes should we make to the OS, in the components listed below, to take advantage of the quicker access time? Contrast these changes with current implementations and be as specific as possible in your answers (i.e., identify what you would change, how, and why). Consider: Process scheduling Memory management The disk driver handling I/O requests to and from the device
(500) Any model of computation must obey two basic inequalities:
SPACE is O(TIME) and TIME is O(2SPACE).

Define your version of a RAM model (some versions do not have addressable memory, but only named registers; others use registers for addressing memory; pick whichever you are comfortable with). Then explore the consequences (with respect to the bounds above) of having constant-time operations for the following: Incrementing a register Adding two registers and storing the result into a third Multiplying two registers and storing the result into a third
(500) Prove that the following problem is NP-complete.
Instance: an undirected graph, G=(V,E)

Question: is there a subset of vertices, V' subset of V, such that No two vertices of V' are connected by an edge; and Every vertex in V-V' is connected to exactly one vertex in V'

Hint: use a 3SAT variation.
(530) Let Q be the set of all polynomials of degree up to 2. Consider the multiplication of each element of Q by 2 + 3t, to produce elements of C, a set of cubic polynomials. Prove that C is a vector space. What is its dimension? What is a basis for Q? Suppose that we represent elements of C by the 3-tuple of its coefficients so that 1+2t+3t2 is represented as (1, 2, 3) and we represent elements of C by 4-tuples. Give the matrix representation of the transformation from Q to C. Is the mapping from Q to C a linear transformation? Prove your result.
(530) Suppose that I have an unfair coin whose probability of a head is p. Now suppose that we enter the following game. You start with a fixed amount of money, say $100. You can bet any amount you like on the flip of the coin BUT you only win if it is a head. If you win, you keep the amount you bet and I give you the same amount more. If you lose, I keep the amount that you bet. If p is less than 1/2, how can you maximize your chances of winning $100? Prove your result. Repeat (a) for p greater than 1/2. Suppose it is a fair coin. Does it matter how much you bet each time?
(580) The Proxy pattern can be considered a template pattern, that is, it is not a pattern by itself with no qualification but the model for several patterns that all are types of proxies. State the overall principles that characterize Proxy patterns. Give some examples of different types of Proxy patterns. How does the Proxy pattern relate to the idea of indirection?
(580) The Mediator and Adapter patterns have some similarities. What is similar about them? What is different about them? Give an example of each. Can you come up with an example that could reasonably be considered both the Mediator and Adapter patterns, or are they different enough that no example could be considered as both? Either give such a common example and explain it or explain why no such common example can exist.

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 Computer Science Department

Fall 2001 Masters Exam

In This Section: