Spring 2005

DATA STRUCTURES, ANALYSIS OF ALGORITHMS AND COMPUTATIONAL COMPLEXITY

Consider 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 operation: search the queue for a given integer, returning TRUE if found, otherwise FALSE. The search should only scan locations with legitimate data. You may assume the existence of an isEmpty() function, and this is the prototype in C for the new search function:
```
int inQueue(int x);
```
In addition, briefly describe in words the issues involved with isEmpty() and isFull() functions. You do not need to code isEmpty() or isFull().
Write a function which is provided a pointer to the root of a (possibly empty) binary tree, and performs this operation: swap the character element of the given node with the element of the node of the left child. The entire tree should undergo this transformation, starting from the root. Do not move any pointers, just move elements. If the node does not have a left child, then a swap does not occur. Obviously, if the tree is empty, there is nothing to do. Note that the function does not have a return type. Code in the language of your choice and include the declaration of your data structure.
Example of "swap with left":
```
       A                        B                        B
      / \                      / \                      / \
     /   \                    /   \                    /   \
    B     G   ... ===> ...   A     G   ... ===> ...   C     G
   / \     \                / \     \                / \     \
  C   D     H              C   D     H              A   E     I
     / \   /                  / \   /                  / \   /
    E   F I                  E   F I                  D   F H

 Initial Tree           Intermediate Tree           Final Tree
```
In the following, f(n) and g(n) have the same "order" if f is in Q(g).
a) List the following functions from lowest (asymptotic) order to highest (asymptotic) order. On your paper, circle any groups which are of the same order.

2ⁿ nÖn n(log n)+n² 68log(17n) (n³+n)/(2n+1) 3ⁿ

b) Copy the list below onto your paper, then circle each of the following algorithms which are in-place (i.e., those whose additional storage requirements are independent of array size). Standard efficient implementations are assumed.

Insertion sort Quicksort Heapsort Mergesort

c) Copy the list below onto your paper, then circle each of the following algorithms for which the order of the number of comparisons it does in the worst case is the same as the order of the number of comparisons it does for the average case.

Insertion sort Quicksort Heapsort Mergesort
Give a precise description (state diagram or entire delta function) for a deterministic one-tape Turing machine that decides the language L = {w | w = w^r} over the alphabet {a,b} (where w^r means w with the characters reversed).

COMPUTER ARCHITECTURE AND OPERATING SYSTEMS

Consider this variation of the Readers-Writer Problem. There is an intersection of two roads: along one road, automobiles (processes) drive North-or-South; along the other road, automobiles drive East-or-West. At the intersection, there is no traffic light. Instead, the following rules apply to automobile A approaching the intersection:
a) if the intersection is empty (available), then it is OK for A to proceed
b) if an automobile B is already in the intersection then
i) if automobile A is going along the same road (e.g., A and B are both going North-or-South, independent of direction) then it is OK to proceed
ii) if automobile B is going along the other road (e.g., A is going North-or-South but B is going East-or-West), then it is NOT OK to proceed.

Assume the existence of these global variables:

int NS: number of North-or-South bound automobiles in the intersection, initially 0.
int EW: number of East-or-West bound automobiles in the intersection, initially 0.
Semaphore NSmutex: to protect NS variable, initially available.
Semaphore EWmutex: to protect EW variable, initially available.
Semaphore intersectionAvailable: initially available;

Write the code for the North-or-South bound automobile process.

Be sure to include this comment at the appropriate place in the code:

/*driving in the intersection */
Consider the deadlock problem in resource allocation and answer the following questions.
a)What are four standard necessary conditions for deadlock? For each condition, briefly describe a way to prevent this condition.

b) Answer the following TRUE/FALSE questions with +1 point for correct answer, 0 point for no answer, -1 point for incorrect answer.
1. If a system is deadlocked, there must be a cycle: TRUE/FALSE
2. If a system has a cycle, then it must be deadlocked: TRUE/FALSE
3. If there is no cycle, then there cannot be deadlock: TRUE/FALSE
4. If a system is not safe, then it is deadlocked: TRUE/FALSE
5. If a system is deadlocked, then it is not safe: TRUE/FALSE
6. The Banker's Algorithm is the efficient choice in single instance cases: TRUE/FALSE
7. Detection/Recovery is slow because each request for resources requires a cycle check: TRUE/FALSE
8. In Avoidance, it is never possible to have deadlock: TRUE/FALSE
Design a fully simplified 3-bit mod 6 up counter with T flip-flops. The circuit increments with each clock pulse, going through the sequence 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, ..., repeatedly. Show the circuit diagram.
Design a combinational eight bit wide barrel arithmetic right shifter. The shifter is controlled by a three bit shift count. You may implement this using a combination of gate level and higher level (adder, multiplexor, decoder, etc.).

PROGRAMMING LANGUAGES AND COMPILER DESIGN

Consider the following C-like program:
```
int a[2];
void z(int i, int j) { 
  i = a[i];
  j = a[j];
  a[j] = a[i];
  a[i] = j*2;
}
main() {
  a[0] = 1;
  a[1] = 0;
  z(a[0], a[1]);
  print(a[0],a[1]);
}
```
For each of the following parameter mechanisms, describe the mechanism and show the output from the program.

a) call by value
b) call by reference
c) call by value-result
Describe top-down parsing and bottom-up parsing. Discuss issues and the various techniques within each category.
Multiple choice. On your answer sheets, list the letters that apply for each numbered problem. Note on scoring: -1 point for each extra letter, -1 point for missing letter; hence, 4 points per problem.
1. A variable's
a) scope must be determined by the lexical structure of the program;
b) type must be known at translation time;
c) lifetime must be determined by the variable's type;
d) value may be determined at translation time.

2. Associating storage to a variable name
a) is called ``binding'';
b) may be at translation time;
c) may be at run-time;
d) can never change.

3. An alias
a) occurs when two variables share the same type;
b) occurs when two variables share the same memory address;
c) can only occur in languages with pointers;
d) cannot occur with call-by-value parameters.

4. Parameter passing by
name copies the value of the actual parameter;
b) value is usually the default for arrays;
c) reference insures that aliases will not arise;
d) value-result can be considered macro-expansion.

5. Garbage
a) exists when deallocation occurs before the last reference;
b) exists when the last reference occurs before deallocation;
c) is collected in all languages which use heaps;
d) is found in static languages.
Consider the following declaration of a subset of the syntax for a C prototype:
```
int z(int i, const float x)      or      int id(int id, const float id)
```
The following LL(1) grammar can be used to define this part of the C language:
S -> T id ( A )
A -> L | e
L -> F M
M -> , F M | e
F -> C T id
C -> const | e
T -> int | float
where the terminal symbols (tokens) are: id , ( ) const int float and the nonterminals are: S, A, L, M, F, C, and T.
a) Compute the value of FIRST for each of the non-terminals in this grammar.
b) Compute FOLLOW of these non-terminals.
c) Using your results from a) and b), construct an LL(1) parsing table.
d) Using your result from c), begin the parse of the example above assuming that z, i, x are all replaced with the terminal id. Show the contents of the stack and how the input is consumed (show at least the first five steps).