Spring 2000
1. Given the root of a binary tree, write a function that returns TRUE (1) if the tree has no left children. That is, the tree is empty or is just a list of right children. Otherwise, return FALSE (0).
a) Write an ITERATIVE solution.
b) Write a RECURSIVE solution.
Declare your data structure and program your functions in the language of your choice.
2. Implement a FIFO queue of integers using a circular array, a[0]..a[n-1], where n is a constant. In the language of your choice, declare the data structure and give code for the following operations: initialize_to_empty, insert_at_rear, remove_from_head, is_empty, is_full.
3. Solve the recurrence relation T(n) = T(n/2) + lg(n) where T(1) = 1 and n = 2k for a nonnegative integer k. Your answer should be a precise function of n in closed form. Note that lg represents the log function base 2.
4. Choose ONE of the following polynomial reductions.
a) Carefully define the two problems involved.
b) Give the reduction and prove its validity.
Be concise, precise, and clear!
(1) 3-SATISFIABILITY <=P VERTEX-COVER
(2) SATISFIABILITY <=P 3-SATISFIABILITY
(3) VERTEX-COVER <=P [UNDIRECTED]HAMILTONIAN-CIRCUIT
(4) 3-SATISFIABILITY <=P SUBSETSUM
1. Consider ten dining philosophers seated around a circular table. Between each philosopher there is a fork which is protected by a semaphore: fork[0]..fork[9]. Each philosopher needs two forks to eat. Consider this solution for philosopher i (i=0,1,...,9):
process philosopher(int i) {
while (1) {
// thinking
wait(mutex);
wait(fork[i]);
wait(fork[(i+1) % 10]); // modulo operator: %
signal(mutex);
// eating
signal(fork[i]);
signal(fork[(i+1) % 10]);
}
}
All semaphores have been initialized to 1 (i.e., available).
a) Is deadlock possible?
b) Is indefinite postponement for an individual philosopher possible? (i.e., is the solution "unfair"?)
c) Describe any other undesirable aspects of this proposed solution, if any.
Explain your answers. The following is a table of equivalent notation for semaphores.
| Silberschatz | Dijkstra | Tannenbaum |
| wait(s) | P(s) | down(s) |
| signal(s) | V(s) | up(s) |
2. Consider a virtual memory paging system and the following two programs written in C:
Program A: Program B:
int A[128][128]; int A[128][128];
for (i=0; i<128; i++) for (j=0; j<128; j++)
for (j=0; j<128; j++) for (i=0; i<128; i++)
A[i][j] = 0; A[i][j] = 0;
Assume that each page of logical memory (and therefore each frame of physical memory) is 128 words. Note that the array A is 128 pages. Also assume that the compiler generates code to store array A by "row major", that is, A[0][0], A[0][1], ..., A[0][127], A[1,0], etc.
Consider how many page faults will occur with respect to the Least-Recently Used (LRU) and First-In First-Out (FIFO) page replacement algorithms (with pure demand paging). Also consider the effects of the number of available frames in physical memory.
Answer this problem by filling in the table with the number of page faults under eight (8) different circumstances. No other answers are required and none will be considered. Do not consider the pages necessary to hold the program code, just the pages for the array A.
| # OF FAULTS | # OF FAULTS | ||
| 1 Available Frame | 128 Available Frames | ||
| Program A | LRU | ____ | ____ |
| FIFO | ____ | ____ | |
| Program B | LRU | ____ | ____ |
| FIFO | ____ | ____ |
3. Are the following standard Boolean functions of 2 inputs associative?
a) NOR
b) equivalence (also called exclusive NOR).
Justify your answers.
4. Design a simplified circuit that will have the clock as input and the output will have the following timing diagram with respect to the clock.
CLK
+--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+
+--+ +--+ +--+
| | | | | |
-----------------------------+ +--------------------------+ +--------------------------+ +------------
Output
That is, the circuit's output will be 1 for the low portion of every fifth clock pulse. Use T flip-flops and additional gates as needed.
1. Consider this "basic block" of 3-address code statements. Note that this basic block came from a loop with variable i.
Assume variables a, i, x are programmer-defined (type int[], or int), C is a programmer-defined constant (also int), and that all ti are compiler-generated temporaries, not used outside this basic block.
Line #
1) t1 := i - 1
2) t2 := 4*t1
3) t3 := a[t2]
4) x := t3
5) t4 := 4*t1
6) t5 := a[t4]
7) t6 := C - 1
8) t7 := 4*t6
9) t8 := t7
10) a[t8] := x
List at least FOUR significant types of optimization that can be done to the block. For each, BRIEFLY:
a) define the optimization
b) list line number(s) where this optimization can be used
c) explain how the optimization improves this line (or lines)
2. Show the output of the program (in a language that is not C++ but has similar syntax) listed below if the language uses:
a) dynamic scope and call by reference
b) static scope and call by value-result
int a, b;
int f(int x) {
a++;
x++;
return (a+x);
}
void g(int y){
int a = 2;
int c = f(a);
b = 9;
y = y+a;
}
void main(){
a = 7;
b = 5;
g(b);
print (a, b);
}
3. Problem: Which of the following language features CAN and which CANNOT be described using a context free grammar (or Backus-Naur Form grammar). Explain your responses.
a) Multiplication has higher precedence than addition.
b) Boolean expressions are evaluated using short-circuit evaluation.
c) The index used in an array reference must be in the range with which the array was declared.
d) In a nested IF statement, an ELSE corresponds to the nearest IF.
4. "The C language uses structural type equivalence for arrays and name type equivalence for structs."
a) Clearly and concisely, explain the meaning of this sentence.
Give (if possible) type and/or variable definitions in C or C++ for:
b) Two arrays a1, a2 that are of equivalent types
c) Two arrays b1, b2 that are not of equivalent types
d) Two structs c1, c2 that are of equivalent types
e) Two structs d1, d2 that are not of equivalent types