Spring 2008

  1. Given a BINARY SEARCH TREE (BST) of integer elements, write an ITERATIVE function that deletes the node with the minimum integer. Do not return the node to memory.

    There will be TWO default cases which require special treatment. Be sure to handle appropriately. Because of these special cases, the function should return a pointer to the node that should be the root of the BST, perhaps the original root, or some other pointer.

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

  2. Consider a HASH TABLE (size = 100) in which collisions are handled by separate chaining (closed addressing) with SINGLY-LINKED LISTS. Assume the keys are integers, and the existence of a hash function which determines the hashing index for a key:

    int hash(int key)

    a) Write a function which finds a specified key, and returns a pointer to that node (or NULL).

    b) Write a function which prints out all keys in the table in any order.

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

  3. a) Given a BINARY TREE of integer elements, write a function which performs a PREORDER traversal. When the function "visits" a node, print out the element.

    b) Repeat, but print out the elements only at every other layer, starting from the root. You decide on the appropriate parameters to your function. Also show the initial call to your function.

    As an example, this tree:

            5        /   \       4     9      / \   /       2   8 1        /       \  10         3    \       /     6     7
    would result in the following output: 5, 2, 6, 8, 1, 7.

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

  1. Consider N worker processes, each with a critical section where work is done. Each process knows its own process ID, mypid (0..N-1), and executes the following code:

    int p = -1;  // GLOBAL variable shared by all processes, initialized once    while (true) {    if (p == -1)      p = mypid;    else      if (p != mypid)        while (p != -1) {}     // empty loop body      // CRITICAL SECTION WHERE WORK GETS DONE      // Remainder Section is empty  }

    a) Discuss both MUTUAL EXCLUSION and FAIRNESS with respect to this solution.

    b) Repeat, but assume the following code in the Remainder Section:

        p = -1;

  2. Consider variable partition memory management. Assume the free list has a TOTAL of 1000KB, and that the following requests for memory arrive in this order: 100KB, 200KB, 300KB, 400KB. In the following, you get to decide the organization of the 1000KB free list, including both the order and the size of the partitions. For example, (1KB, 999KB) is a two-element list with 1KB at the front, followed by 999KB.

    a) Write a free list such that the First-Fit (FF) algorithm AND the Best-Fit (BF) algorithm exhibit NO external fragmentation.

    b) Repeat such that FF has the worst-case fragmentation possible in a situation where BF exhibits NO fragmentation.

    c) Repeat such that both FF AND BF exhibit worst-case fragmentation.

  3. Design a fully simplified combinational circuit as follows: There will be 3 inputs a2a1a0 and 3 outputs b2b1b0. Treating a=a2a1a0 as a signed integer, b=b2b1b0 is to be the 2's complement of a.

    Show your work and draw the resulting circuit diagram using only gates.

  1. Consider this example of a simpified Switch statement in a C-like language: 
    switch (varterm) {    case numterm : stmt; stmt; stmt;    case numterm :    case numterm : stmt;    default      : stmt; stmt;  }
    where the terminal symbols (tokens) are: switch case default : ; ( ) { } varterm numterm stmt

    Notes:

    1. () is used to enclose a varterm.
    2. {} is used to enclose a list of cases.
    3. There is always at least one case, not counting the default case.
    4. A case has a numterm followed by zero or more statements.
    5. The default case is optional but, if present, will appear at the end.

    Construct a Backus Naur Form (BNF) grammar for a switch statement in this language. Do not use Extended BNF (EBNF).

  2. Solve the recurrence relation T(n) = 2T(n/2) + (n-1) where T(1)=0 and n=2k for a nonnegative integer k. Your answer should be a precise function of n in closed form (an asymptotic answer is not acceptable). Show the work you did to obtain the solution.
  3. Let G = (V, E) be an undirected graph. A vertex cover of G is a set C ⊆ V such that every element of E touches at least one element of C.

    Let VERTEX-COVER = {G, k : G is an undirected graph with a vertex cover of k nodes}.

    Show that 3SAT ≤P VERTEX-COVER; that is, show that there is a polynomial reduction from 3SAT to VERTEX-COVER.