Fall 2008

1. Code any O(n log n) sorting algorithm (average case) in the language of your choice. Be sure to state the name of the algorithm. Assume that the data are integer elements stored in an array.

2. An "ONLY-CHILD" node in a BINARY TREE has exactly ONE child. Write a function which counts and returns the number of ONLY-CHILD nodes in the tree. In Question #3, below, the example tree has two ONLY-CHILD nodes: 13 and 9.

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

3. Given a BINARY TREE of integer elements, write a function to perform a BREADTH-FIRST SEARCH (BFS). Instead of printing an element, "visits" should create (and eventually) return a new LINKED LIST. Each node in the list should contain an element from a "visit" in the tree. However, the list should be in REVERSE order.

For example, this tree:

        5
      /   \
     2     1
    / \   / \
  14  13 9   6
     /    \
    10    12

would yield this list: 12, 10, 6, 9, 13, 14, 1, 2, 5

You do not have to write the code for any fundamental operations on local data structures you use. The function should return a pointer to the head of this new list.

Program in the language of your choice, and include declarations for both the tree and the list.

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.

Θ(1) Θ(log n) Θ(n) Θ(nlog n) Θ(n²)
Θ(n²log n) Θ(n³) Θ(n³log n) Θ(n⁴) Θ(n⁴log n)

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}.