Fall 2003

1. Consider a Binary Search Tree (BST) with integer keys. Assume these integer keys are inserted into the tree in this order: 10, 4, 7, 15, 12, 13, 5.

a) Draw the BST after the insertion of the keys.

b) Code an ITERATIVE function called "find" in the language of your choice. The function should return a pointer to the node containing a specified key. If the key is not found, then return NULL. Also, declare your data structure. The signature (prototype) in C: tree_ptr find(int x, tree_ptr p).

c) Code a RECURSIVE version of the function.

2. For each of the algorithms listed below, state the average-case BIG-THETA (Q) running time. In general, assume n is the size of the data set and, in particular for graph algorithms, assume n is the number of vertices and m is the number of edges. For graphs, assume the adjacency list implementation. On your answer sheets, number your answers 1..20.

Warning: do NOT guess, just leave blank (+1 point for correct answers, 0 point for blanks, -1/2 point for incorrect answers).

3. Let G be a connected graph with n vertices and m edges. The edges are stored using the adjacency list implementation.

a) Write a routine to perform a breadth-first-search traversal on G. Code in the language of your choice. For fundamental local data structures (stack, queues, etc.), you may call functions for the basic operations without writing the actual code.

b) State in BIG-THETA (Q) terms the runtime of your routine. Your answer should be the best description as a function of n and m. Justify your answer.

4.a) Define "NP-Complete decision problem".

Consider these six classic NP-Complete problems: 3-SATISFIABILITY, 3-DIMENSIONAL MATCHING, VERTEX COVER, CLIQUE, HAMILTONIAN CIRCUIT, PARTITION.

b) Define precisely and concisely any ONE of the above problems.

c) Give a yes-instance, explaining WHY it is a yes-instance.

d) Give a no-instance, explaining WHY it is a no-instance.

1. Consider the following faulty code for a Producer-Consumer pair sharing a bounded buffer [0..N-1]:

Producer:                                      Consumer:
  while (true) {                                 while (true) {
    while (counter == N) {} // empty loop body     while (counter == 0) {} // empty loop body
    buffer[in] = ch;        // produced character    ch = buffer[out];  // consumed character
    in = (in + 1) % N;                               out = (out + 1) % N;
    counter = counter + 1;                           counter = counter - 1;
  }                                              }

Assume that global shared variables have current values: N=2, counter=1, out=0, in=1. Describe an execution sequence such that the Producer thinks the buffer is full when, in fact, the buffer is not full, thus illustrating the faulty code. Use any combination of description, diagrams, charts, etc. to help describe the execution sequence.

Note: this should not be just a temporary misalignment, which rights itself. This should be an extreme fault to the system.

2. Consider resource allocation graphs with a set of processes P = {P₁, P₂, P₃}, a set of resources R = {R₁, R₂, R₃}, and a set E of request (P_j®R_i) or assignment (R_i®P_j) edges. R₁, R₂, R₃ have 1, 2, 1 instances, respectively.

In each of the following, draw the graph and state whether deadlock exists or not. Briefly explain each answer.

a) E = {P₁®R₁, P₃®R₂, R₁®P₂, R₂®P₂, R₂®P₁, R₃®P₃, P₂®R₃}
b) E = {P₁®R₁, P₃®R₂, R₁®P₂, R₂®P₂, R₂®P₁, R₃®P₃}
c) E = {P₁®R₁, R₂®P₃, R₁®P₂, P₂®R₂, R₂®P₁, R₃®P₃}

Note: the bold edges are intended to highlight the differences between the graphs.

3. A simple ALU performs ADD, SUB, AND, OR, and XOR.
Draw a diagram for a 1-bit slice of the ALU.
You should assume decoded control lines.
Use a block diagram for the full adder.

4.Show the circuit diagram for a 5-bit counter that increments the stored value on each clock pulse. It should use JK flip-flops and be a lookahead counter that minimizes gate delay.

1.

a) Describe the important differences between interpretation versus compilation.

b) What are the particular advantages or disadvantages of interpretation versus compilation?

c) Are all languages either compiled or interpreted? Explain.

d) Some languages support multiple-inheritance and others (like Java) do not. Explain the advantages and disadvantages of multiple inheritance.

2. Consider these following examples of a Uniform Resource Locator (URL):

http://server
http://server.company.com
http://server.company.com/
http://server.division.com/dir1/dir2/myfile
http://server.division.com/myfile.cgi
https://server.division.company.com:80/dir1/dir2/myfile.html
rmi://server.company.com/dir1/myobject

where the terminal symbols (tokens) are: http https rmi html cgi : / . id num

Notes:

1. server, division, company, com, dir1, dir2, myfile, myobject are examples of the terminal id.
2. Port number (e.g. 80) is an optional num (introduced by a ":"), with at most one number following the server name.
3. Protocol (e.g. http) is mandatory.
4. Assume each server is one or more id, and is "." separated.
5. A list of directories is zero or more id, and is "/" separated, followed by an optional file name.
6. A file name may have an optional suffix (cgi or html) and, in this case only, would a "." appear in the file name.

Construct a grammar for this subset of the URL language.

3. Given the grammar

a) Prove the grammar is ambiguous using the string "aaabbaa".

b) Use standard transformations to remove the common prefixes in the grammar.

c) Is the revised grammar ambiguous? Prove/disprove.

4.Given this subset of standard intermediate code:

      [-]
     /   \
  [-]     [-]
  / \     / \
[a] [b] [c] [-]
            / \
          [-] [f]
          / \
        [d] [e]

a) Write the expression, using parentheses, which corresponds to the above DAG.

b) Write the optimized standard intermediate code assuming r=1 and count the number of statements. "Optimized" means that the number of statements should be minimal. The result should reside in register R₀.

c) What is the minimum value of r required to achieve the fewest number of statements? That is, increasing r has no effect on the the number of required statements. Briefy explain.