ÂÌñ»»ÆÞ

1. Given the following four processes and main body:

int i = 0;     // GLOBAL VARIABLE, INITIALIZED ONCE

PROCESSES:
P1:             P2:             P3:             P4:
   i = i + 1;      i = i + 2;      i = i - 1;      i = i - 2;

MAIN BODY:
   start asynchronously P1, P2, P3, P4
   // AFTER ALL PROCESSES HAVE FINISHED
   print i

What are the possible values that the main body might print after all processes have finished? Give a brief justication for each of your answers.

2. Consider the deadlock problem and the avoidance technique. The following resource allocation graph shows the potential claims (needs) and the actual assignments for Processes P1, P2, P3, and for Resources R1, R2, R3.

See attached graph

For each of the following resource requests, how would the avoidance technique respond? Give a brief justification. Each question below is independent and starts from the graph above.

a) P2 requests R1.

b) P2 requests R2.

c) P2 requests R3.

d) P3 requests R3.

3. Design a synchronous state machine capable of producing the repetitive pattern in the waveform given below. Show your work, including a state table, Karnaugh maps, and a schematic using J-K or D or T flip-flops and gates to implement the state machine.

See attached wafeform

1. Multiple choice. On your answer sheets, list the letters that apply for each numbered problem. Note on scoring: -1 point for each extra letter, -1 point for missing letter; hence, 20 points maximum for this problem.

1. Considering languages in general, the size of an array may be determined at:
     a) compile-time;
     b) run-time during object creation;
     c) run-time in general.

2. A language is "strongly typed" if type checking can be done
     a) statically;
     b) at compile-time;
     c) at run-time;
     d) dynamically.

3. With respect to type compatibility:
     a) name equivalence requires pattern-matching;
     b) actual and formal parameter types can never be compared based on name equivalence;
     c) name equivalence is simpler to implement;
     d) structural equivalence is more restrictive;
     e) name equivalent must be structurally equivalent.

4. BNF
     a) and syntax diagrams are equivalent techniques for describing the semantics of a language;
     b) presents a consistent representation of a context-sensitive grammar;
     c) uses recursion to achieve repetition;
     d) is useful in describing the meaning of valid sentences in a language.

5. An Activation Record
     a) has a size that is always known at compile-time;
     b) has either a static link OR a dynamic link, but not both;
     c) with a static link is inefficient because all links must be followed until a binding occurs;
     d) with a dynamic link is efficient because the linkage can be established at compile-time.

2. For each part, determine the worst case runtime as a function of n. Choose each answer from among the following.

a) Apply Quicksort to an array of n elements.

b) Apply Heapsort to an array of n elements.

c) Let G be a dense weighted graph with n vertices with its edges already placed in an array. Apply Mergesort to sort the edges by weight.

d) Apply Breadth-First-Search to a dense graph of n vertices.

e) Apply Binary Search on an ordered array of n elements.

3. Give the state diagram for a pushdown automaton that recognizes the language {w : w contains more 0's than 1's} over Σ = {0, 1}.