ÂÌñ»»ÆÞ

1. Consider a CAKE FACTORY, which makes N different types of cakes (Chocolate, Lemon, etc.) The cakes are produced on N PARALLEL lines with a MAKER at each line who knows how to make that specific type of cake.

When a cake is finished, the MAKER moves it to one COMMON work table. The table has slots for M SHIPPERS to receive the cakes and to put the cakes into shipping boxes (which are then tossed onto a big truck).

See attached diagram

Write the code to SYNCHRONIZE the MAKERS and the SHIPPERS. That is, what is the code for a MAKER and what is the code for a SHIPPER? You may assume these fundamental operations: put(cake), get(cake).

It is very important to show the INITIALIZATION of variables that you use.

2. Consider a system with three resources (A, B, C) in quantity (5, 10, 8). The Banker's Algorithm is used to allocate resources and it has the following current SAFE state:

Assume the following requests for (A, B, C) arrive in the order below. In each case, answer YES (request granted) or NO (request denied). Give a brief justification for each answer.

Assume that the problem is CUMULATIVE. For example, your answer for request 3 assumes that requests 1 and 2 have been processed (with results of granted or denied). At no time during this problem are any resources actually returned by any of the processes.

3. Rewrite F(a, b, c, d) = Σ(0, 1, 2, 3, 5, 8, 9, 11, 13, 15) in simplified product-of-sums form.

1. A DIFFERENT important concept is illustrated in each of the following C++ programs. In each problem, identify the concept and briefly explain (one good sentence would be sufficient).

a)
int main() {
 cout << (int) 14.7 / 2 << endl;
}
b)
class A {
  public:
    int calc(int num1) {
      return num1*num1;
    }
    int calc(int num1, int num2) {
      return num1*num2;
    }
}
c)
void myFunction(int i, int &j) {
  i++;
  j++;
}
int main() {
  int i = 1;
  int j = 1;
  myFunction(i, j);
  cout << i << " " << j << endl;
}
d) 
void myFunction(int &i, int &j) {
  cout << i << " " << j << endl;
}
int main() {
 int k = 1;
 myFunction(k, k);
}
e) // Be sure to consider other possible outputs
void  myFunction(int i, int j) {
  cout << i << " " << j << endl;
}
int main() {
  int k = 1;
  myFunction(++k, ++k);
}

2. a) In the following algorithm, determine the precise number of "fundamental operations" where integer n > 0. Your answer should be a function of n in closed form. (An asymptotic answer is not acceptable.)

for (int i = 2; i < n; i++) {
  for (int j = i; j <= n; j++)
    Perform 1 fundamental operation;
  //endfor
}//endfor

b) In the following algorithm, determine the asymptotic (i.e. BIG-THETA) number of fundamental operations where n can be any even positive integer.

for (int k = 2; k <= n; k = k+2) 
  Perform k fundamental operations;
//endfor

3. a) Define completely, but concisely, any TWO of the following. A decision problem X is in EXPSPACE, PSPACE, EXPTIME.

b) Describe the inclusion relationships among these classes (use <=): EXPSPACE, PSPACE, NP, EXPTIME, P.