Spring 2004

a) Write a RECURSIVE function, in the language of your choice, which finds an integer key x within an array of n entries, 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? Justify your answer.

void bad_sort(element a[], int first, int last)
  // The original call is bad_sort(a, 0, n-1).
{
  if (first < last) {
    int mid = (first + last) / 2;
    bad_sort(a, first, mid);
    bad_sort(a, mid+1, last);
    // The largest element is now the larger of a[mid] and a[last].
    if (a[mid] > a[last])
      Swap a[mid] & a[last];
    //endif
    bad_sort(a, first, last-1);
  }
}

Let C(n) be the number of times the algorithm compares array elements.
a) Write a recurrence relation for C(n) that is valid for any n > 0.
b) Determine C(10).

// Global Variables, initialized once:
int readcount = 0;
boolean readOK = true;
boolean writeOK = false;

Readers:                                     Writer:
  while (true) {                               while (true) {
    readcount++;                                 while (readOK) {} // empty loop body
    if (readcount == 1) {                        writeOK = true;
      while (writeOK) {} // empty loop body
      readOK = true;                             // write data section
    }
    else                                         writeOK = false;
      while (!readOK) {} // empty loop body    }

    // read data section

    readcount--;
    if (readcount == 0) 
      readOK = false;
  }

Answer the following questions YES/NO, with a description of the sequence of events leading to the described situation. There are good, brief explanations that will be acceptable. Note: in all cases, the CPU scheduler will give each process repeated access to the CPU.

Is it possible (perhaps after an initial period) to get into a situation such that:

a) data is read AND written at the same time (i.e. no mutual exclusion)?

b) ONLY data is read (i.e. not fair to the writer, hence starvation)?

c) ONLY data is written (i.e. not fair to the readers, hence starvation)?

d) NO data is read or written (i.e. no progress)?

1. If there is a safe sequence, there cannot be deadlock.
2. If there isn't a safe sequence, there will be deadlock.
3. If a resource request is less than the current available resources AND the request is less than the process's current "need" of that resource, then the request can be granted.
4. If a request comes in that is exactly the current available resources, then the request must be denied.
5. If one process has no more "need", then the system is in a safe state.
6. There can only be at most one safe sequence.
7. It is possible to have a safe sequence but the system is not in a safe state.
8. The safe sequence is the order in which the processes will execute.
9. If there are more than one safe sequence, the Banker does not need to select one.
10. If there is only one safe sequence, then each process must return it's resources before the next process can run.

b) Let F(a, b, c) be given by the following truth table:

Implement F using only a 4x1 multiplexer and a single inverter. Use a block diagram for the multiplexer.

1. Top-down parsers
a) attempt to find the rightmost derivation.
b) attempt to construct a parse tree from the root, creating nodes in "preorder".
c) include predictive parsers.
d) include SLR parsers.
e) include recursive-decent parsers.

2. Recursive-descent parsers
a) may use backtracking.
b) must use backtracking to avoid infinite loops on left-recursive grammars.
c) include predictive parsers.
d) do not require analysis of FIRST and FOLLOW sets.
e) implement bottom-up parsing algorithms.

3. LR parsers can
a) parse all grammars that any predictive parser can, and more.
b) NOT detect a syntactic error as soon as it is possible on a left-to-right scan.
c) are more powerful than SLR.
d) less powerful than LALR.

4. LL(1) parsers are able to handle
a) some left-recursive grammars.
b) some right-recursive grammars.
c) all unambiguous grammars.

5. LR parsers are able to handle
a) some left-recursive grammars.
b) some right-recursive grammars.
c) all unambiguous grammars.

void f(int a, int &b, int *c, int d[], int e) {
  b = 4*a;
  a = 5;
  *c = 8;
  d[0] = 7;
  e = 10;
}
int main () {
  int i = 1;
  int j = 2;
  int k = 3;
  int *p = &k;
  f(i, i, &j, &j, *p);
  cout << i << " " << j << " " << k << " " << *p << " " << endl;
}

a) Briefly describe the interaction between the actual and formal parameters, including what is copied in to the function; and what restrictions, if any, are placed on their use"

b) What is the output of the program?

a) Define "live" name.
b) Using your definition, what names are live upon exit from B1?
c) Define "equivalent" basic blocks.
d) Are B1 and B1' equivalent?
e) Describe the different types of structure-preserving transformations that have occurred from block B1 to B1'.