Fall 2007
1. Consider an application that requires a task,myTask, to perform the following sequence of operations on a single data structure:
i) find a specific value in the data structure
ii) delete this value from the data structure
iii) insert some other value, at the appropriate place, into the data structure
Consider each of the following data structures as a candidate for the above myTask, which involves performing all three operations. For each data structure, state the overall BIG-OH for myTask in terms of the average case and the worst case as a function of n, where n is the number of elements in the data structure. Do NOT guess: +2 points for correct answer, -2 points for incorrect answer, 0 points for no answer.
| myTask: Big-Oh | ||
| Average Case | Worst Case | |
| Unsorted Array | ||
| Sorted Array | ||
| Minheap (Priority Queue) | ||
| Binary Search Tree | ||
| Hash Table | ||
2. Given a DOUBLY-LINKED list and an integer search key, find the corresponding node in the list and replace it with another given node. The C prototype is:
void find_replace(node_ptr p, int key, node_ptr new_node);
where p is a pointer to the first node in the list (or NULL), key is the search key, and new_node is a pointer to the replacement node. Code in the language of your choice and include the declaration of your data structure. Do not worry about the memory storage for the node that is replaced. If the key is not present, then do nothing.
3. Given a binary tree of integer elements, return a copy of the same tree. Consider what the return value should be if the given tree happens to be NULL. Code in the language of you choice and include the declaration of your data structure.
1. Compare and contrast the long-term scheduler with the short-term scheduler. Be sure to include a discussion of the important resources and the strategies involved in each case.
2. Consider "working sets" in memory management.
a) Describe briefly the significance of a "working set window".
b) Given a working set window of 4, write a page reference string such that the size of the working set is 1 (as viewed from the end of the string).
c) Repeat, such that the size of the working set is 2.
d) Briefly, what are the effects of a high window versus a low window?
3. Let F(a,b,c,d) = a'bc'd' + a'bc'd + a'bcd' + ab'c'd' + abc'd' + abcd.
a) Use a 4x16 decoder and a minimal number of additional logic gates to implement F.
b) Use a 16x1 multiplexer (and no additional logic gates) to implement F.
1. a) In the C language, write five expressions as examples for following operator types: prefix, postfix, infix, binary, unary.
b) Independent of language, what operator type(s) would be best to handle an operation with three operands.
c) Program a function, in C, which is given three boolean parameters, and returns true (1) if at least two of the operands are "true".
The prototype is: int atLeastTwo(int a, int b, int c)
Use any C operators but NO other constructs (such as IF).
2.The following recursive algorithm calculates xn.
a) Write a recurrence relation for M(n), the number of multiplications performed. Do not solve the recurrence. Note that n can be any nonnegative integer.
int pow(float x, unsigned int n)
{
if (n == 0) return 1;
if (n == 1) return x;
if ( (n % 2) == 0 ) return pow(x*x, n/2); // n is even
return x*pow(x*x, n/2); // n is odd
}
b) Determine M(2007).
3.Let A = {0n1n : n ≥ 0} over Σ = {0, 1}. Give a context-free grammar for the language A*.