Spring 2000 Masters Exam
University of New Mexico
Computer Science Department
Master's Examination
9 AM to 12 noon on March 25, 2000
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)
Explain the byte-code implementation technique used for Java. What are the alternative implementation methods that might be used instead? What are the advantages and disadvantages of a byte-code implementation?
(451)
Discuss the trade-offs between dynamically typed and statically typed computer languages. Give an example of each. Are there languages that do not use types at all? Give an example (and explain it) or explain why there is not one.
(460)
Discuss the advantages and disadvantages of staged delivery lifecycles vs. evolutionary delivery lifecycles. Under what circumstances would you prefer an evolutionary approach to the staged approach? Under what circumstances would you prefer a strict waterfall? Why?
(460)
Object oriented design and object oriented analysis are terms often applied to software projects.
(a) Briefly define each term.
(b) Give a typical software project timeline and tell where each technique might be employed.
(c) Is there a boundary between the 2 techniques in time? Briefly describe the relationship between the 2 and their relationship to the overall project development flow.
(d) Is it possible to use one without the other? Explain.
(461)
Consider the following function.
int f(int n)
{
if ( n == 0 )
return 5;
else
return ( 7 * f(n-1) + 6 );
}
(a) What is the running time (big O) of f() as a function of input argument n?
(b) What is the growth rate (big O) of the value of f() as a function of input argument n?
(c) How are (a) and (b) affected if the statement
return ( 7 * f(n-1) + 6 );
is replaced with
return ( 700 * f(n-1) + 6 );
(d) How are (a) and (b) affected if the statement
return ( 7 * f(n-1) + 6 );
is replaced with
return ( f(n-1) + 4 * f(n-1) + 2 * f(n-1) + 6 );
(461)
Prove or disprove: the following algorithm sorts an array in increasing order from left to right; then analyze the running time of the procedure (write a recurrence and solve it).
procedure strangesort(array a, left, right) {
if (right == left) return
if (right == left+1) {
array[left] <- smaller(array[left,],array[right])
array[right] <- larger(array[left,],array[right])
return
}
mid = (left+right)/2 /* returns an integer */
quarter = (left+mid)/2
threequarters = (right+mid)/2
strangesort(a,left,mid)
strangesort(a,mid+1,right)
strangesort(a,quarter,threequarters)
strangesort(a,left,mid)
strangesort(a,mid+1,right)
strangesort(a,quarter,threequarters)
}
(481)
Consider the synchronization constructs mutex, semaphore, condition variable, and monitor. Explain how they work and when/why each of them is useful.
(481)
Why is it meaningful to perform certain functionality (fully or partially) in user-space libraries instead of calling the operating system kernel? Give two examples of standard functionality where user-space implementation is performed.
(500)
Let L = {M: Turing machine M accepts an even number of strings}. I.e. L = {M: |L(M)| is even}.
(a) Is L recognizable (recursively enumerable)? Prove your answer.
(b) Is L co-recognizable (co-r.e.)? Prove your answer.
(500)
What is the difference between a many-one reduction and a Turing reduction? Does that difference matter when proving that a problem is NP-hard? Why is it (correctly) claimed that a proof that polynomial-time Turing reductions are more powerful than polynomial-time many-one reductions for problems in NP would provide a proof that P is a proper subset of NP?
(530)
We want to send four messages over a communications line. Each message is sent as signal of one-second duration. During that second, each signal can take on only values of either +1 or -1. Thus, each signal looks like a sequence of bits with values of +1 and -1 rather than the usual 0 and 1.
(a) Give four simple signals that are orthogonal to
each other. That is 
if 
. Hint: use an orthogonal matrix.
(b) Suppose that some transmitter sends the sum of two or more of the signals. Find a way for a receiver to determine which ones were sent.
(530)
A simple network with n nodes is fully connected; that is there is a path from every node to every other node. Suppose that each node is connected to two other nodes, When a message arrives, the node keeps it if the message is addressed to it and sends it to the other node to which it is connected otherwise.
(a) What is the average number of nodes a message passes through before reaching its destination? Show your work.
(b) What happens if each node is connected to all other nodes and each node sends any message not addressed to it to a random node?
(580)
Give an example of a design where you could use either the Strategy pattern or the Decorator pattern to achieve the same effect. Describe the design requirements of the problem to be solved. Describe how each pattern could be used to solve the problem. Evaluate how each one worked.
(580)
Describe how a pipes-and-filters architecture is structured. Give some of the advantages and disadvantages of a pipes-and-filters architecture.
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
