Spring 2011

Answer ANY TWO of the following three questions.

  1. Consider a HASH TABLE of size N = 10. Given this arrival of integer keys: 10, 44, 13, 7, 89, 73, 12, 23, 36, and the following hash function: 
    int hash(int key, int N) {
  return key % N;          // modulo
}
    a) [Points: 9] Assuming Closed Hashing (Open Addressing, Array Only), show the hash table using LINEAR PROBING.
    b) [Points: 5] Starting with an empty array, repeat using QUADRATIC PROBING.
    c) [Points: 6] Starting with an empty array, repeat assuming Open Hashing (Separate Chaining, Additional Lists).
  2. a) Given a BINARY TREE of integer elements, consider a function which performs a POST-ORDER traversal. When the function "visits" a node, do NOT print out the element. Instead, create a new list of integer elements. Therefore, each "visit" to a tree node should cause the insertion of a new node into the list, with the same integer value.

    The resultant list should be the REVERSE of the visitations.

    The function may return the list, or the function may operate on a global list structure.

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

  3. Each of the following is worth 3 points, except a) is only 2 points. There is no penalty for guessing.

    Given a connected, undirected graph G = (V, E),

    a) TRUE or FALSE: Summation over all v in V of degree(v) is ODD?

    b) TRUE or FALSE: |E| >= |V| - 1?

    c) TRUE or FALSE: G has at least one vertex with degree 1?

    d) For SPARSE graphs, |E| = BIG-THETA( )?

    e) For DENSE graphs, |E| = BIG-THETA( )?

    f) For Prim's MST using Adjacency Matrix, performance = BIG-THETA( )?

    g) For Kruskal's MST using Disjoint Sets, performance = BIG-THETA( )?

Answer ANY TWO of the following three questions.

  1. Consider the following solution to the mutual exclusion problem: 
    int count = 3;  // Global variable, initialized once

  Process0:                                    Process1:
    while (true) {                               while (true) {
1:    while (count != 0) { /* SPIN */}             while (count == 0) { /* SPIN */ }
2:    // critical section (DO WORK)                  // critical section (DO WORK)
3:    count = 3;                                   count = count - 1;
    }                                           }

    In the following, answer YES/NO with a short description.

    [POINTS: 7] a) Does the code guarantee mutual exclusion?

    [POINTS: 6] b) Does the code guarantee that work will be done?

    [POINTS: 7] c) Does the code guarantee fairness?

    In all cases, assume that the processes do NOT have a "remainder" section and do NOT crash. That is, the code executes exactly as shown above.

  2. [POINTS: 6] a) Define internal fragmentation and how it arises.

    [POINTS: 7] b) Define external fragmentation and how it arises.

    [POINTS: 7] c) What solutions to external fragmentation are available and how do they work?

  3. A logic circuit has three input bits: x0, x1, x2, where x0 is the least significant bit and x2 is the most significant bit. The output from the circuit is 1 when its input is any of the 3-bit numbers 1, 4, 5, or 6; otherwise, the output is 0. Write an expression as a function of x0, x1, x2 that represents the output from this circuit. Show your work.

Answer ANY TWO of the following three questions.

  1. a) [POINTS: 3] In English, describe as simply as possible the language corresponding to the regular expression a*b(a*ba*b)*a*.

    b) [POINTS: 7] Draw a Nondetermistic Finite Automaton (NFA) for the same expression.

    c) [POINTS: 3] In English, describe as simply as possible the language corresponding to the regular expression ((a+b)3)*(a+b). Note that "+" is the symbol for set union.

    d) [POINTS: 7] Draw a Nondetermistic Finite Automaton (NFA) for the same expression.

  2. Consider the definition (syntax) of a SIMPLE PROGRAMMING LANGUAGE. The language consists of zero or more variables at the start, followed by zero of more functions. Each function has a heading, followed by zero or more variables, followed by zero or more statements. Note the repetition of "zero or more", this is key. There is nothing else in this language, do NOT consider any more detail of the language.

    Construct a Context-Free Grammar (CFG) for this language.

    Assume the existence of ONLY these terminal symbols (tokens): variable, heading, statement
    This can be solved with just a few productions.

    Here is an example program:

    i j k
myFunction1
 a b 
 incr_i
 decr_b
myFunction2
myFunction3
 decr_k
    where the above fall into these categories:

    variable: i, j, k, a, b
    heading: myFunction1, myFunction2, myFunction3
    statement: incr_i, decr_b, decr_k

  3. Suppose Q and R are languages. Assuming P <> NP, which of the following implies that R is NOT in P? That is, answer TRUE or FALSE for each question.

    Do NOT guess: +4 points for correct answer, -2 points for incorrect answer, 0 points for no answer.

    a) R is in NP.

    b) Q is in NP and Q is polyomial-time reducible to R.

    c) Q is in NP and R is polyomial-time reducible to Q.

    d) Q is NP-complete and Q is polyomial-time reducible to R.

    e) Q is NP-complete and R is polyomial-time reducible to Q.