Spring 2003

Example:

L1->[2]->[9]->[17]
L2->[3]->[9]->[12]->[17]->[20]
L3->[17]->[9]

There will no be duplicates within a list. Code in the language of your choice. The C version of the function prototype (signature) is:

node_ptr reverse_intersection(node_ptr L1, node_ptr L2)

a) Briefly explain the First-Fit algorithm.

b) Briefly explain the Best-Fit algorithm.

Given a variable partition memory management scheme with the following free list:

c) Show how memory is allocated using the First-Fit algorithm by filling in this table:

Producer:                          Consumer:
  while (true) {                     while (true) {
    wait(A);                           wait(B);
    wait(C);                           wait(C);
    /* put into the buffer */          /* take out of the buffer */
    signal(C);                         signal(C);
    signal(B);                         signal(A);
  }                                  }

The problem is to consider the effects of the initialization of the semaphores A, B, C with respect to i) a correct solution and whether the solution guarantees ii) mutual exclusion, iii) no deadlock, and iv) no starvation. The table below has five different initializations and for each initialization answer Yes/No to the previous four questions. Draw this table on your solution paper. Note: The definition of starvation here is that it is possible for only one of the two processes to make progress.

Warning: do NOT guess, just leave blank (+1 point for correct answers, 0 point for blanks, -1 point for incorrect answers).

The instruction format for "op rd, rs" is as follows: opcode(4 bits) rd(3 bits) rs(3 bits) plus other fields that are not needed for this problem.

Draw a diagram showing how such a scheme can be implemented. Clearly label the components and connections in your design and write a brief explanation of your approach. You may use block diagrams for standard components you may need, such as encoders, decoders, multiplexers, shifters, counters, etc. The following is the beginning of the diagram.

a) dynamic scope and call by value-result
b) static scope and call by reference
c) static scope and call by value

Show your work in terms of activation records.

int a, b, c;
int g(int x, int y) {
  c = 2;
  x++;
  y--;
  a = x + c;
  return (x-y);
}
void f(int x) {
  int a = x+3;
  b = g(a,c);
  x = x + b;
}
void main() {
  a = 3;
  b = 5;
  c = 7;
  f(b);
  print(a,b,c);
}

a) Describe the static storage-allocation strategy.
b) Describe the stack storage-allocation strategy.
c) Describe the heap storage-allocation strategy.

Be sure to compare the strategies and describe differences between the strategies (including lifetimes, visibility, efficiency, etc.).

struct y {             struct id {
  float x;       or      float id;
  int i;                 int id;
};                     };

a) Show the set of terminals belonging to FIRST(S), FIRST(L), FIRST(F), FIRST(T).
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 y, x, i 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).