University of New Mexico
Computer Science Department
Master's Examination
March 27, 1999
Instructions: 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).
(451) Give programs to do list reverse and insert-sort in Prolog.
(451) Write a Lisp function "flatten" that will take an arbitrary s-expression and return a list of the atoms in the s-expression as you would encounter them if you traversed the tree depth first.
(460) How could experimentation be used in the study of software engineering. Describe what you think would be a good experiment. Describe what you would measure, how the control groups would work, how you would be sure you were measuring what you wanted to measure, how you would take account of differences in programmers, etc.
(460) Consider the problem of choosing a language in which to write the User Requirements. What are the possible languages and/or kinds of languages one might choose? What are the main considerations in choosing this language. What are the strengths and weaknesses of the languages you propose?
(461) Consider a nonempty binary tree with two types of nodes, a min node and a max node. A node of either type has an integer value associated with it. Define the value of a tree as follows:
- If the root is a min node, then the value of the tree is the minimum of the value in the root and the value of each nonempty subtree.
- If the root is a max node, then the value of the tree is the maximum of the value in the root and the value of each nonempty subtree.
- Write an algorithm to compute the value of such a tree.
- Analyze the efficiency of your algorithm.
- Prove your algorithm correct.
(461) As you know, the critical part of the quicksort algorithm is the choice of the partitioning element—if it is well chosen, the algorithm runs in O(n log n) time with very low coefficients, but if it is poorly chosen, the algorithm takes quadratic time.
Consider the following two strategies:
- the partitioning element is picked to be the element in the middle position in the (portion of the) array under consideration (a standard refinement is picking the median of the first, middle, and last elements); or
- the partitioning element is chosen uniformly at random among the elements of the (portion of the) array under consideration.
In case (1), one can show that the average-case running time (assuming that all input permutations are equally likely) is O(n log n); in case (2), a very similar proof shows that the expected running time (regardless of the input) is O(n log n).
In one sentence, characterize the difference between these two results; in a second sentence, state which of the two you would prefer and why.
(481) What is load control in a virtual memory system? What is its purpose and what problem does load control solve? Give a description of a load control algorithm. Be sure to explain how it makes its decisions as well as what it does.
(481) Explain what a remote procedure call (RPC) is. Sketch how RPCs can be implemented using an underlying message system.
(500) Let L = {M: M is a Turing Machine and (|L(M)|=0 or |L(M)|=2)}
- Without referring to parts (b) or (c), state in two words why L is not decidable (recursive).
- Is L recognizable (recursively enumerable)? Prove your answer
- Is L co-recognizable (co-r.e.)? Prove your answer.
(500) Let L = {w: $ integers n, p: w = 0n1p and p is prime}. Prove that L is not regular.
(530) You are given the following information about a series of opaque (non-transparent), closed bottles. 40% of the bottles contain lemonade and 60% of the bottles contain grape juice. Of the lemonade bottles, 50% are red, 20% are green and 30% are blue. Of the grape juice bottles, 20% are red, 20% are green and 60% are blue. For what % of the bottles can I correctly guess the contents, knowing the color. What is my guessing strategy?
(530) Consider Q to be the set of all real quadratic polynomials in t on the interval, [0,1]. Consider normal polynomial addition and multiplication. We can consider Q to be a vector space.
- What is the field Q is defined over?
- What is the dimension of Q?
- Give a basis for Q.
- Is your basis orthogonal? normal?
(580) Consider a web browser (like Netscape or Internet Explorer). Design two different architectures for a web browser, each using a different architectural pattern. For each architecture show the major modules, indicate what their functions are and how they interact.
(580) Some OO systems do not have inheritance. Does this imply that inheritance is not an important part of OO programming? How do these languages get the same effects as we usually get from inheritance?
Home | Colloquia | Research | People
Current Students | Prospective Students | Companies | Visitors
Scholarships | Courses | Degrees | PIBBS
Computer Facilities | Jobs | Links
(505) 277-3112 (phone)
(505) 277-6927 (fax)
Web site questions:
All other questions:
Department of Computer Science
Mail stop: MSC01 1130
1 University of New Mexico
Albuquerque, NM 87131-0001
