Spring 2007

  1. A full node in a binary tree has either no children or exactly two children. Write a function which returns TRUE (1) if a tree is made up entirely of full nodes; otherwise return FALSE (0). An empty tree is FULL. Code in the language of your choice and include the declaration of your data structure (the element in the node should be of type integer).

    Special Note: Do not use any other functions or a counter (NO CREDIT will be assigned).

  2. Given a DOUBLY-LINKED list with integer elements sorted in ASCENDING order, write an EFFICIENT function which puts the data into DESCENDING order. Both head and tail pointers of the list are parameters. Do NOT modify any node pointers, just swap the integer elements. The running time of your algorithm should be linear with respect to the length of the list. Only constant local memory can be used. To make the programming cleaner, you may assume that the list has an ODD number of nodes. Code in the language of your choice and include the declaration of your data structure.
  3. Given a Binary Search Tree, write a RECURSIVE function to insert a new integer into the tree. The prototype in C is: 
    tree_ptr insert(int x, tree_ptr T)
    Note the return type of the function.
  1. Given this partial code of two processes: 
    Semaphore A = _____;  // initialization of semaphore, should be some integer value  Semaphore B = _____;  Semaphore C = _____;  P0:                       P1:    while (true) {            while (true) {      1:                        4:                     2:                        5:                 3:                        6:                   }                         }
    and this completed Gantt chart:
    Gantt chart:
    P0:
    W*(A)    		 P1:
    W(B)    		 P1:
    W(C)    		 P1:
    S(A)    		 P1:
    W*(B)    		 P0:
    S(B)    		 P0:
    S(B)    		 P0:
    W(C)    		 P0:
    W*(A)    		 P1:
    W*(C)
    0 1 2 3 4 5 6 7 8
    Note that the chart uses a short-hand notation: P1:W(A) indicates that process P1 executes wait(A) without blocking, and P1:W*(A) indicates that P1 blocks on the semaphore.

    a) Based on the Gantt chart, fill-in the code such that each process has three semaphore calls.
    b) Based on the Gantt chart and code, fill-in the initialization of the semaphores, that is, the initial value of the integer counter.

  2. Consider the classic page replacement strategies for virtual memory (except the OPTIMAL strategy). Assume the memory has exactly 3 frames (0..2), and this page reference string: 6, 2, 5, 2, 8, 3, 7. In each of the following parts, the contents of memory are displayed according to a particular replacement strategy. For each part, determine which strategy was applied.
    a) Page Reference
    6 2 5 2 8 3 7
    Frame 0 6 6 6 6 8 8 8
    Frame 1 _ 2 2 2 2 3 3
    Frame 2 _ _ 5 5 5 5 7

    b) Page Reference
    6 2 5 2 8 3 7
    Frame 0 6 6 6 6 8 8 8
    Frame 1 _ 2 2 2 2 2 7
    Frame 2 _ _ 5 5 5 3 3

    c) Page Reference
    6 2 5 2 8 3 7
    Frame 0 6 6 6 6 8 8 7
    Frame 1 _ 2 2 2 2 2 2
    Frame 2 _ _ 5 5 5 3 3

    d) Page Reference
    6 2 5 2 8 3 7
    Frame 0 6 6 6 6 6 6 7
    Frame 1 _ 2 2 2 8 8 8
    Frame 2 _ _ 5 5 5 3 3
  3. Design a state machine that outputs the sequence 0, 1, 2, 3, 7, 6, 5, 4, 0 ... Present your state-table, K-map reductions and a gate level schematic drawing. Use your choice of J-K, D, or T flip-flops. Limit your gates to NANDs, NORs, and XORs (and their demorgan equivalents).
  1. Consider the following program that uses C-style syntax: 
    int a[2];  void z(int b[], int i, int j) {      int k;    a[0] = 2;    k = b[i];    b[i] = b[j];    b[j] = k;    i = j;    print(a[0], a[1], i, j);  }  main() {    int i = 0; int j = 1;    a[0] = 2;    a[1] = 3;    z(a, i, j);    print(a[0],a[1], i, j);  }

    For each of the following parameter mechanisms, briefly describe the mechanism, and show the output from the program.

    a) call by value (for all types, including arrays)
    b) call by reference
    c) call by value-result

  2. Determine the precise number of "fundamental operations" in the following algorithm where n>0. Your answer should be a function on n in closed form (an asymptotic answer is not acceptable). 
    //START CODE  for (int i = 1; i < n; i++) {                     //OUTER LOOP ONE    Perform 2 fundamental operations;    for (j = i+1; j <= n; j++)                  //INNER LOOP      Perform 3 fundamental operations;    //endfor  }//endfor    for (int k = n; k > 0; k = k/2)                        //OUTER LOOP TWO    Perform 1 fundamental operation;  //endfor  //END CODE
  3. If G = (V, E) is an undirected graph,
    • A vertex cover of G of size K is defined as a subset V' ⊆ V such that |V'| ≤ K, and for every edge {u,v} ∈ E, at least one of u and v belongs to V'.
    • A edge cover of G of size K is defined as a subset E' ⊆ E such that |E'| ≤ K, and for each v ∈ V, there is some e ∈ E' for which v ∈ e.
    • VERTEX COVER
      Instance: Graph G = (V, E) and positive integer K
      Question: Does G contain a vertex cover of size K or less?
    • EDGE COVER
      Instance: Graph G = (V, E) and positive integer K
      Question: Does G contain an edge cover of size K or less?

    a) Show - carefully and completely - that VERTEX COVER is in NP.

    b) Suppose that you are told that EDGE COVER is in P, and also that EDGE COVER is polynomially reducible to VERTEX COVER,
    EDGE COVER ≤P VERTEX COVER. What does this tell you about VERTEX COVER? Why?