Spring 2001

Consider the following correct solution to the bounded-buffer producer-consumer problem, where there a N buffers, and the functions producer() and consumer() are run concurrently.

  1    semaphore mutex = 1;    // initial value of semaphore is 1
  2    semephore full = 0;     // # of occupied slots
  3    semaphore empty = N;    // # of available slots
  4
  5    void producer() {
  6      while (true) {
  7        produce();
  8        wait(empty);
  9        wait(mutex);
 10        append();
 11        signal(mutex);
 12        signal(full);
 13      }
 14    }
 15    void consumer() {
 16      while (true) {
 17        wait(full);
 18        wait(mutex);
 19        take();
 20        signal(mutex);
 21        signal(empty);
 22        consume();
 23      }
 24    }

Foe each of the following pairs of program line numbers, what would be the potential effects (if any) of swapping the two lines of the program?

a) 8 and 9

b) 20 and 21

2. Suppose a process is given 4 frames of memory. Consider the following reference srtring:

0,1,7,2,3,2,7,1,0,3,7,2

If the four frames are initially empty, show which references will cause page faults. Show the content of the four frames at the time of each fault.

a) Using LRU replacement

b) Using Optimal replacement

3. Design a 3-bit "up/down counter" that changes state (on clock pulses) as follows:

If an external input x is equal to 0, the 3-bit value is decremented.

If x is equal to 1, the 3-bit value is incremented.

For example (calling the flip-flops A, B, C), suppose ABC = 111.

If x is 0, the next state for ABC is 110.

If x is 1, the next state for ABC is 000.

Use T or JK flip-flops. Draw the logic diagram. Sufficient simplification is required .

4) A combinational circuit has three outputs F1, F2 and F3 defined as follows:

F1(x,y,z) = x'y'+xyz'

F2(x,y,z) = x' + y

F3(x,y,z) = xy + x'y'

Design the circuit using only one 3x8 decoder and minimal extra logic.

1. Swap 2 adjacent nodes in a doubly-linked list. Declare your data structure in the language of your choice and write a swap function which is given a pointer to the first of the two adjacent nodes. Assume that the 2 nodes have neighbors on the other side so you don't need to worry about NULL pointers. The routine should only modify the links.

2. Write a routine (with O(n*log(n)) average case runtime) to sort an array of ints a[0]...a[n-1] as follows:

Place the elements of the array into a dynamically allocated binary search tree.

Write the elements from the tree back into the array in ascending order.

3. For which real values of a is ln(n) e o(na)? (This is little-oh.) Prove that your answer holds for those values of a and only those values of a.

4. Consider the problem:

TRUE-SAT = {boolean expressions E in conjunctive normal form that

(1) are true when all variables are set true, AND ALSO

(2) have some other truth assignment that makes E true}

This can also be stated (in Garey-Johnson notation) as:

Instance: Set of clauses C1,C2,....Ck over the boolean variables u1,u2,....um

Question:

(1) are all Ci true when u1,u2,....um are set to true, and

(2) is there another satisfying truth assignment (not all variables set to true)?

a) Show that TRUE-SAT is in NP.

b) State clearly but briefly what one must show to prove that there is a polynomial time reduction (polynomial transformation) from problem X to problem Y.

c) The following is proposed as a reduction from SAT:

Given a set of k clauses over variables u1,u2,....um, construct k new clauses by adding a new variable z to each clause.

Prove or disprove: this is a polynomial transformation, SAT <=P TRUE-SAT

1. Four small grammars are given below:

a) For each grammar, show whether or not it is suitable for LL(1) parsing.

b) For each grammar, show whether or not it is suitable for LL(2) parsing.

c) Choose ONE grammar that is not suitable for LL(1), and using standard transformations, make it suitable for LL(1).

1. S--> a S b | S b a | S a b | e

2. S--> a b S | a c S | b a

2. S--> a S b | a S c | b a

4. S--> a S b | b S a | e

2. Consider the C-like function below.

 
  int f(int n) {
    if (n==0 || n==1)
      return 1;
    else
      return f(n-1) + f(n-2);
  }

a) What will an "activation record" for this function look like? Show ONE typical example of an activation record, including all necessary links, variables, and parameters.

b) What is the greatest height of the run time stack used during the evaluation of this function for f(100); (i.e., what is the maximum number of activation records needed)? Describe which activation records will be on the stack at the maximum.

3. Consider the code generated for the following while statement in a language that does short-circuit evaluation (Program has declared a,b integer variables, MAX as an integer constant).

  while (a<5 || b<=2*MAX) {
    a = a + b + 1;
    b = a + b + 1;
  }

a) Give the intermediate code generated for this block of code (you may invent a suitable form and operations for the intermediate code).

b. Briefy analyze your code for efficiency. State what optimizations should be done.

4) Consider the following program written in some new language that uses the keywords "IN OUT" for one method of passing parameters. This new language uses static scope rules.

  int b:=11; int c:=9;                 // declare and initialize b and c
  procedure first(IN OUT int x,y);
    begin
      =x-y;                          // := is the assignment operator
      b:=5;
      c:=6;
      if(x==b) then =7;              // == is test-for-equality operation
   end;

   begin {test}
     first(b,c);
     print("b and c are:",b,c);
   end;

What are the results of this program if:

a) IN OUT is implemented by call-by-copy.

b) IN OUT is implemented by call-by-reference.