Fall 2000 Masters Exam
University of New Mexico
Computer Science Department
Master's Examination
9 AM to 12 noon on October 21, 2000
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.
(451)
What is a Turing Machine? What is a Universal Turing Machine? Name and describe another formal model for computation. What is the Church Turing Hypothesis? Why is it an hypothesis?
(451)
Describe, compare, and contrast inheritance schemes for PROLOG, Common Lisp, Java, and ML.
(460)
Discuss the strengths and weaknesses of the following metrics: physical lines of code, logical lines of code, and function points. What does each measure? How is each metric computed? Which measure would you select when estimating the size or duration of a software project. Why?
(460)
Object oriented design is fundamentally different from top down structured design.
a) Define, compare and contrast the 2 methods.
b) Tell which method you think is preferable most of the time and why.
c) Give an example of an application where object oriented design is preferred.
d) Enumerate and briefly describe the major steps one might take in an object-oriented design.
(461)
Consider the following C-like functions.
pow(int x, int y) {
if (y == 0)
return 1;
else
return x*pow(x,y-1);
}
f(int n) {
s = 0;
for (i = 0; i <= n; i++)
s = s + i/pow(2,i);
return s;
}
(a) Ignoring arithmetic precision, what is an exact
closed form for 
as a function of 
?
(b) Again ignoring arithmetic precision, what is the
time complexity of 
as a function of 
?
(c) How can the running time of this computation be improved significantly?
(461)
Given a graph, G=(V,E), and an integer k, find the largest induced subgraph G' = (V',E'), where all the vertices of G' have degree k or more.
Develop an algorithm that solves this problem. Analyze the efficiency of your algorithm.
(481)
Explain in words the concept of a working set. Then give a formal definition of a working set in terms of the page reference string of a process. State the working set algorithm for page replacement.
(481)
We often divide the file system implementation into two levels: the logical file system and the physical file system. Describe the tasks that are done by each of these levels.
(500)
Give a deterministic finite automaton that accepts the set of all strings over {0,1}* 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 e, 11, 110, 1001, 1100, 1111, 10010, 10101, etc.)
(500)
Prove that the following problem is NP-complete. An instance of the problem is given by a graph, G=(V,E), and a positive integer, k £ |V|. The question is whether the vertices of G can be colored in red and blue such that (i) each red vertex has at least one blue neighbor; and (ii) there are at least k red vertices.
Hint: known NP-complete problems you may want to use include vertex cover, dominating set, and closely related problems.
(530)
Given the point, {1, 2, 3 }. What is the projection of this point onto the plane determined by the origin and the points {1, 1, 0 } and { -1, 2, 1 }?
(530) Zipf’s Law states that the frequency of a word in English is inversely proportional to it’s rank. That is, the most frequent word occurs with frequency, C/1, the 2nd most frequent word occurs with frequency, C/2, the 3rd most frequent word occurs with frequency, C/3, ... etc. C is calculated to make the “frequencies” add to 1.
- How can you use this model to estimate the entropy of English?
- What would be some of the advantages of doing the analysis this way?
- What would be some of the disadvantages of doing the analysis this way?
(580)
Describe how the model-view-controller architecture is structured. What are the advantages and disadvantages of this architecture? Give an example of a situation where this would be a good architectural choice.
(580)
Compare the Bridge and Adapter architectural patterns. How are they the same and how are they different? Give an example of a typical use of each one.
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
