University of New Mexico
Computer Science Department
Master's Examination
October 23, 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) What is "Horn Clause Logic", how does it relate to First Order Predicate Logic, and why (do you think) it was used as the implementation medium for PROLOG? Explain cut (!) in this context.
(451) What is the role of the "module system" (structures, functors, and signatures) in ML? Give an example using it.
(460) Explain how both the waterfall model and the prototyping model of software development can be accommodated in the spiral model.
(460) What is involved in estimating the size of a software project? What is the function point model of software estimation?
(461) Consider the following two (correct) programs for finding the height of a binary tree. (For this problem, height is defined to be the number of nodes on the longest path through the tree.) What are the running times of the two programs when run on binary trees with n = 2m-1 nodes, in which each node has either zero or two children and all the leaves are the same distance from the root (that is, on perfectly balanced trees).
Do this problem by counting something specific (state what you are counting). That is, don't just do the computation using Q(). Make sure to express your final answers in terms of n, the number of nodes in the tree, and not m, the height of the tree.
Algorithm 1:
int height(Node* p) {
if (p == NULL)
return 0;
else {
int lheight = height(p->left);
int rheight = height(p->right);
if (lheight > rheight)
return lheight + 1;
else
return rheight + 1;
}
} // int height(Node* p)
Algorithm 2:
int height(Node* p) {
if (p == NULL)
return 0;
else {
if (height(p->left) > height(p->right))
return height(p->left) + 1;
else
return height(p->right) + 1;
}
} // int height(Node* p)
(461) Design a data structure (start with a balanced binary tree structure such as an AVL or red-black tree) that stores pairs (key, value) and supports the following four operations in such a way that each runs in worst-case logarithmic time:
· add a new pair (k',v')
- remove a pair with key value k
- return the sum of the values of all pairs with a key between k1 and k2
- add the constant c to the value of each pair with a key between k1 and k2
(481) Explain the main conceptual differences between processes and threads. List at least 3 reasons why it is meaningful to have threads.
(481) How can we synchronize multiple threads to enter the next phase of computation after they all have finished the previous one? Describe briefly one way of performing this.
(500) The Binpacking problem is defined as follows: given a collection of items, each with a positive integer size, and given bins of equal size (a size larger than the size of any single item), find a way to pack the items into as few bins as possible -- no bin can be packed beyond its size and each item must be placed into one bin (i.e., no item can be chopped up). Prove that this problem is solvable in polynomial time when all the items are at least as large as one-third of the size of the bins.
(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, clique and closely related problems.
Reminders:
· Vertex Cover is {(G, k): Graph G has a subset of vertices S such that |S| = k and every edge in G includes/touches at least one of the vertices of S}
· Dominating Set is {(G, k): Graph G has a subset of vertices S such that |S| = k and every vertex in G-S is adjacent to one of the vertices of S}
· Clique is {(G, k): Graph G has a subset of vertices S such that |S| = k and every vertex in S is adjacent to every other vertex of S}
(530) In most literature about color perception, color is a triplet (T1,T2,T3) where each Ti is the amount of one of the primary colors red (R), green (G) or blue (B). In other words a color C can be represented as a vector expressed as a linear combination of the vectors R, G and B, C=T1R+T2G+T3B.
(a) Although the red-green-blue primary system is useful for much color work, the complimentary color system cyan-magenta-yellow (CMY) is used in the commercial printing industry. Cyan is the sum of blue and green, magenta is the sum of red and blue and yellow is the sum of green and red. Give a matrix which converts the color coordinates (T1,T2,T3) in the RGB system to coordinates in the CMY system.
(b) Often in color work, we are interested in the plane T1+T2+T3=1 which has approximately uniform brightness. Find an orthogonal basis in this plane starting with the RGB basis.
(c) Suppose a color has a representation (T1,T2,T3) in the RGB system, what is its projection on the plane T1+T2+T3=1?
(530) A binary symmetric channel has a probability p of sending a bit correctly. If p is not high enough, we can encode bits by repeating each 0 or 1 an odd number of times. For example, we send 000 and 111 or 00000 and 11111.
(a) How would you decode received strings of bits into messages?
(b) For k bits sent for each 1 or 0, what is the probability of an error in the received message?
(c) Can this scheme achieve an arbitrary low message error rate?
(d) Can this scheme be used to generate a code allows error-free communication at channel capacity? Explain your answer.
(580) Find two design patterns from the Gang of Four Design Patterns book where you create a second object with exactly the same interface as a previously existing object. By “previously existing object” I mean that this object and its interface is set by the conditions of the problem. The second object is a new object that is created as part of the pattern. For each pattern explain what the main goals of the pattern are and what is the role of the new object (the one described above as the “second object”) in relation to the first object.
(580) Describe how an event-based architecture is structured. Give some of the advantages and disadvantages of an event-based 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
