Fall 2000
1. If necessary, use standard transformations to make the following grammar suitable for a topdown parse.
The six terminal symbols (tokens) in the grammar are: id number ( ) , :=
Write either
a) a complete recursive descent parser (in pseudocode, C++, or Java), or
b) the LL(1) tables and the LL(1) parsing algorithm.
STLST --> STMT STLST | e
STMT --> id := number | id ( VARLST )
VARLST --> VARLST , id | id
2. a) What would call-by-name return for the following function? (It is written in C-like syntax but does not use standard C parameter passing methods)
int i = 0;
int a[] = {1,2,3};
void f(int x, int y) {
y++; x++; y++; x++; y--;
}
f(i, a[i]);
print (i, a[0], a[1], a[2]);
b) Would the values at the print statement be different if call-by-reference is used? Explain any differences.
3. a) Define: eager (strict) evaluation and lazy (applicative) evaluation
A C-like language has:
(i) a standard binary operator + which returns the sum of two numbers
(ii) a ternary operator ?: which takes 3 arguments a,b,c and returns b if a is true; otherwise returns c
(iii) a function defined as
int f (int x){ return 42; }
Suppose that x,y,z are integers and have values: z = 10, x= 5, y = 0;
z + (y != 0 ? x/y : x); //LINE 1
x = f ( f(x) / y); //LINE 2
b) Choose ONE of the two lines in the above program, and explain how the language's use of lazy or eager evaluation (you are not told which is used) would affect its evaluation.
4. In a language (such as Ada) that allows static variables and nested functions, consider the following program
int a; //global variables
static int sb;
function f {
int fa;
static int sfa;
function g {
int ga;
int static sgb;
---- line inside g ----
} //end of g
} //end of f
Note that all six variables are visible from the "line inside g".
a) Concisely but completely, design and describe a storage mechanism for variables in this language.
b) Describe the steps (in the code generated by the compiler) to access each variable from the "line inside g". For each access, note the number of memory references (direct and indirect) necessary.
1. Consider the following sequential search algorithm:
int search(element x, element a[], int n)
// Return the index where x first occurs among a[0]..a[n-1].
// Return -1 if the search is unsuccessful.
{
for (int i 0; i < n; i++)
if (x == a[i])
return i;
//endif
//endfor
return -1;
}
Assume that
i) A search will be successful 90% of the time.
ii) When successful, it is equally likely that x will be found in any of the positions from 0 to n-1.
Determine the average number of times x will be compared with array entries. Your answer should be a function of n in closed form.
2. A degree-constrained spanning tree of degree K in graph G is a spanning tree in which no vertex has degree larger than K.
The "Degree Constrained Spanning Tree Problem" is:
Instance: Graph G (V,E), positive integer K <= |V|
Question: Is there a spanning tree for G in which no vertex has degree larger than K?
a) Give (clearly and concisely) a yes-instance
b) Give a no-instance
c) Prove: This problem is NP complete
3. Consider a sorted array of n non-negative integers.
a) Write an iterative function, in the language of your choice, which finds a key x within the array and returns its index position. If the key does not exist, then return -1. Your algorithm should have a BIG-OH which is optimal.
b) What is the tightest BIG-OH running time of your algorithm?
4. Consider a general tree where a node can have zero or more children. An efficient data structure, with respect to storage, is for each node to have a child pointer and a sibling pointer. For example, the tree below has a root A which has three children B, C, and D. Essentially, the sibling pointers form a linked list of children of one parent.
If the child pointer is NULL, then a node has no children.
If a sibling pointer is NULL, then this is the last child in the linked list.
The root does not have any siblings.
A
|
v
B---->C->D
| |
v v
E->F G
The data structure, in C, is declared as:
typedef struct tree_node *tree_ptr;
struct tree_node {
char element;
tree_ptr first_child;
tree_ptr next_sibling;
}
a) Write a recursive function, in the language of your choice, to print out the elements of the tree in a postorder traversal.
b) What would be the printout for the tree above?
1. Consider three processes (P1, P2, P3) accessing two semaphores (A, B) with the following code segments:
P1 P2 P3
-- -- --
1. wait(A); 5. wait(A); 9. signal(A);
2. signal(B); 6. wait(B); 10. wait(A);
3. signal(A); 7. wait(B); 11. signal(B);
4. wait(B); 8. signal(B); 12. signal(A);
The semaphores are not initially available (i.e., the counts are 0).
You can schedule these semaphore calls in any order you like by indicating the associated line number (1..12).
Of course, you cannot schedule line 2 before line 1, line 6 before line 5, etc.
If a wait blocks, don't list it again even if it unblocks later.
In both a) and b) below, your answers should be exactly 12 numbers.
In c), it should be less than 12 numbers.
a) Give a schedule such that all processes will eventually finish but NEVER block on any call to wait.
b) Give a schedule such that all processes will eventually finish but at least one call to a wait does block.
c) Give a schedule such that all processes become deadlocked.
Given: terminology for semaphore usage.
| Silberschatz | Dijkstra | Tannenbaum |
| wait(s) | P(s) | down(s) |
| signal(s) | V(s) | up(s) |
2. Let f(a,b,c,d) = a'b'c'd + a'b'cd + ab'c'd' + abcd' + abcd.
a) Use a 4x16 decoder and a minimal number of additional logic gates to implement f.
b) Use a 16-to-1 multiplexor (and no other gates) to implement f.
Use block diagrams for the decoder and multiplexor.
3. Consider the Banker's Algorithm in a system with two processes (P0, P1) and three types of resources (A, B, C), each in a quantity of N>1 units.
Initially, both P0 and P1 indicate that their maximum requirement is that they might need all the units in the system, that is, (N, N, N). In your descriptions below be sure to state whether the Banker would grant the actual requested resources.
Now the processes begin their work.
a) Describe what would happen, and why, if P0 asked for all the resources (N, N, N) followed immediately by the same request from P1.
Start the system over again and let the processes begin their work.
b) Describe what would happen, and why, if P0 asked for just one unit of resource A followed immediately by the same request from P1.
Start the system over again and let the processes begin their work.
c) Describe what would happen, and why, if P0 asked for just one unit of resource A followed immediately by a request from P1 for one unit of resource B.
4. An Intel processor instruction CMP AX,BX performs the subtraction AX - BX and affects the bits ZF, SF and OF as follows:
ZF <--- 1 if the result of the CMP subtraction is zero
ZF <--- 0 otherwise
SF <--- 1 if the result of the CMP subtraction is a negative number
SF <--- 0 otherwise
OF <--- 1 if the result of the CMP subtraction results in signed overflow
OF <--- 0 otherwise
Draw a diagram for a circuit that has 3 inputs (ZF, SF, OF) whose output will be 1 if and only if AX < BX (as signed integers). (This could be useful in deciding if the branch BLE label should be taken.)