Fall 2009

1. Given N integers, which arrive ONE AT A TIME, and a SINGLE array as a data structure, consider the following two objectives:

i) INSERT the N integers into the array one-by-one
ii) afterwards, do N searches (FINDS) for specific values within the array

Consider the following algorithms:
a) N inserts into the array using a hash function, then N finds according to the hash function
b) N inserts, incrementally, into unsorted array, then N sequential finds
c) N inserts, incrementally, into unsorted array, heapsort the array, then N binary searches of the array
d) N inserts into the array but keep the array sorted, then N binary searches of the array

Fill-in the following table with 8 BIG-THETAS for the Inserts/Finds for these 4 algorithms, and also the 4 BIG-THETAS for the overall performance of each of these algorithms.

	N INSERTS	BIG-THETA	N FINDS	BIG-THETA	OVERALL BIG-THETA
a)	Hash		Hash
b)	Unsorted		Sequential
c)	Unsorted (then Heapsort)		Binary
d)	Sorted		Binary

Notes for a): assume the average case performance for hashing.
Notes for b) and c): an "incremental" insert means to take the next available slot in an unsorted array.
Notes for c): assume the performance of the subsequent heapsort is included with the insertion process.
Notes for d): a "sorted" insert means that the new element is inserted into correct slot, and the trailing elements shifted.

2. Given a MINHEAP (PRIORITY QUEUE) implemented, as usual, as an ARRAY, write an ITERATIVE function that scans along the extreme left side of the tree. During this scan, create (and eventually return) a new LINKED LIST that contains nodes with the same elements as the left side of the tree. The new list should be in the SAME order of the scan of the left side.

For example, this MinHeap:

would generate this list: 3 -> 4 -> 7 -> 10

The return value would be a pointer to the head node containing "3". Code in the language of your choice and include declarations of your data structures (plural). Assume that the array index of the root is 1 (do not worry about the "sentinel" stored at index position 0). Be sure to consider default conditions.

3. Given a BINARY SEARCH TREE (BST), write a RECURSIVE function that finds the parent of a specifed integer key. The function returns a pointer to the parent node. If key does not exist, or key is the root, then return NULL.

The prototype in C: tree_ptr find_parent(int x, tree_ptr p)

Code in the language of your choice, and include a declaration of your data structure.

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:

Process	Allocation			Max			Need			Available
	A	B	C	A	B	C	A	B	C	A	B	C
P0	0	1	0	2	6	5	2	5	5	4	7	5
P1	1	0	1	1	2	2	0	2	1
P2	0	0	2	3	4	2	3	4	0
P3	0	2	0	2	3	2	2	1	2

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.

Request#	Process	Request			Banker Response (YES/NO)
		A	B	C
1	P1	0	1	2	YES/NO
2	P0	2	2	4	YES/NO
3	P3	1	0	2	YES/NO
4	P2	2	4	0	YES/NO

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.