UNM Computer Science

Home > Degrees > Master's Degrees > Masters Examinations > Fall96

In This Section:

Fall 1996 CS Master's Examination

This test is in-class, closed book and closed notes. There are seven groups (one for each of the core courses) of two questions each for a total of 7 questions. You have 3 hours to complete the exam, which translates into 25 minutes per question.

(451-Scheme) What is a "higher order function" in Scheme? Why do they depend on static scoping to be really useful? What is currying and why is it an example of the use of higher order functions. Give another example of a good use of higher order functions. Why are they not possible in C or C++?
(451) Write a Scheme function "traverse" that will take three arguments: an "atom-function", a binary "adder" function and a "zero" value. It will return a function that takes an s-expression as an argument. This function will traverse the s-expression in depth-first order, apply the atom-function to each atom it finds, and apply the adder function to each atom and the result of the adder function for the rest of the traversal. The zero value is used as the result of the adder function for the null list. (If you are hesitant about Scheme syntax, use Lisp with reasonable extensions as needed.) The definition will begin like this:
```
(define (traverse atom-function adder-function zero) ... )
```
(460) What is cohesion and coupling in a system of modules? How do they help you decide if a modularization is a good one?
(460) Describe what a code review is. How do you prepares for one? How do you run one? What do you do after one is finished? Why are they useful? How do they relate to testing?
(461) Given a (garden variety) binary tree, we associate with each edge, , a non-negative capacity, , the amount of water (gas, data, etc.) that can flow from to v. We assume that an infinite supply of water (gas, data, etc.) is available at the root. Define a flow to be a non-negative function f on edges such that

and

(You can think of the root as a source and of the leaves as sinks.) The value of a flow is defined as the total flow through the root; a flow is maximum if its value is the largest possible.
1. Assume that the tree is given in the usual representation (data field, here with capacity, left and right children pointers--no tags or other pointers). Devise a linear-time algorithm (not a program: write up your algorithm in pseudo-code; use recursion if it helps) to compute the value of a maximum flow for the tree.
2. Devise a linear-time algorithm to compute the values of for a maximum flow. (In part (a) above, you only computed the value of the maximum flow, not how it actually flowed through the tree; now assume that each node v in the tree has an extra data field, in which you must store .)
(461) A partition of the integers is a collection of disjoint subsets (called partition cells) of whose union is . Describe in pseudo-code a C++ class that implements a partition, supporting the following two operations:
- same_cell(i,j) returns true iff i and j are in the same cell of the partition; must run in constant time.
- neighbors(i) lists the integers in the same partition cell as i; must run in time proportional to the number of integers in the partition cell of i.
(481) Explain what threads are. Explain the difference between kernel level (OS-level) threads and user-level threads. What are the advantages and disadvantages of each.
(481) Two methods of implementing protection in an operating system are access lists and capabilities. Explain how each one works and give the major advantages and disadvantages of each method.
(500) The k-Partition problem ( ) is given by a set of kn elements, S, and a positive integer size for each element, , such that: (i) the sum of all the sizes equals Bn for some positive integer B; and (ii) the size of each element x obeys the inequality B/(k+1);SPMlt;s(x);SPMlt;B/(k-1). The question is whether the set S can be partitioned into n subsets such that the sum of the sizes of the elements in each subset equals exactly B.
The Binpacking problem is given by a set of n elements, S, a positive integer size for each element, , a positive integer bin capacity C, and a positive integer bound B. The question is whether it is possible to pack all items in S into at most B bins such that the sum of the sizes of the elements in each bin does not exceed C.
Show how to reduce k-Partition to Binpacking in polynomial time.
(500) The Minimum Set Cover problem is given by a graph, G=(V,E). The problem is to find the smallest subset of vertices that covers the graph, i.e., such that every edge in E has at least one endpoint in V. This problem is known to be NP-hard. Show that approximating the solution to the problem of Minimum Set Cover within arbitrary ratio (i.e., such that the ratio of the size of the approximate cover to the size of the minimum cover is at most for arbitrary is just as hard as obtaining the optimal solution.
(530)
- What is the distance from the point (2,3,1) to the plane of equation x+y+z=0?
- What is the angle between the vectors (2,3,1) and (5,-1,2)?
(530) A binary symmetric channel has error rate of 0.2. On the average how many error correcting bits do we need to send to get each bit through correctly?
(580) Describe the Decorator pattern. What does it do, when it is useful, what are the objects that take part in it and what are their interfaces?
(580) What is delegation and how does it differ from inheritance? What are the advantages of delegation over inheritance?