Department of Mathematics and Computer Science
Comprehensive Exam--Computer Science
Spring 2004

DATA STRUCTURES, ANALYSIS OF ALGORITHMS AND COMPUTATIONAL COMPLEXITY

  1. Consider a sorted array of n integers.

    a) Write a RECURSIVE function, in the language of your choice, which finds an integer key x within an array of n entries, and returns its index position. If the key does not exist, then return -1. Your algorithm should have a BIG-OH which is optimal.

    b) What is the tightest BIG-OH running time of your algorithm? Justify your answer.

  2. Given a character element x and a binary tree, write a function that returns a pointer to the parent of the node that contains x. The tree is NOT a binary search tree and a node does NOT contain a pointer to its parent node. The elements are in no particular order and x can appear at most once in the tree. If the element is not found in the tree, or the element happens to be at the root, then return NULL. Program in the language of your choice and include declarations for your data structure. The prototype in C would be: 

    tree_ptr find_parent(char x, tree_ptr p)

  3. Consider the following inefficient algorithm to sort a[0] .. a[n-1]: 
    void bad_sort(element a[], int first, int last)
  // The original call is bad_sort(a, 0, n-1).
{
  if (first < last) {
    int mid = (first + last) / 2;
    bad_sort(a, first, mid);
    bad_sort(a, mid+1, last);
    // The largest element is now the larger of a[mid] and a[last].
    if (a[mid] > a[last])
      Swap a[mid] & a[last];
    //endif
    bad_sort(a, first, last-1);
  }
}

    Let C(n) be the number of times the algorithm compares array elements.
    a) Write a recurrence relation for C(n) that is valid for any n > 0.
    b) Determine C(10).

  4. If L1 and L2 are two languages in NP, show that their concatenation, i.e., L = L1 L2, is also in NP.

COMPUTER ARCHITECTURE AND OPERATING SYSTEMS

  1. Consider the following code for N (>1) readers and a single writer. 
    // Global Variables, initialized once:
int readcount = 0;
boolean readOK = true;
boolean writeOK = false;

Readers:                                     Writer:
  while (true) {                               while (true) {
    readcount++;                                 while (readOK) {} // empty loop body
    if (readcount == 1) {                        writeOK = true;
      while (writeOK) {} // empty loop body
      readOK = true;                             // write data section
    }
    else                                         writeOK = false;
      while (!readOK) {} // empty loop body    }

    // read data section

    readcount--;
    if (readcount == 0) 
      readOK = false;
  }

    Answer the following questions YES/NO, with a description of the sequence of events leading to the described situation. There are good, brief explanations that will be acceptable. Note: in all cases, the CPU scheduler will give each process repeated access to the CPU.

    Is it possible (perhaps after an initial period) to get into a situation such that:

    a) data is read AND written at the same time (i.e. no mutual exclusion)?

    b) ONLY data is read (i.e. not fair to the writer, hence starvation)?

    c) ONLY data is written (i.e. not fair to the readers, hence starvation)?

    d) NO data is read or written (i.e. no progress)?

  2. Answer the following True/False questions concerning a system which uses the Banker's Algorithm to grant or deny resource requests.
    Warning: if you do not know the answer, do NOT guess, just leave blank (+2 point for correct answers, 0 point for blanks, -2 point for incorrect answers).
    On you answer sheets, just number 1..10 and put a "TRUE" or "FALSE" or blank for each.

    1. If there is a safe sequence, there cannot be deadlock.
    2. If there isn't a safe sequence, there will be deadlock.
    3. If a resource request is less than the current available resources AND the request is less than the process's current "need" of that resource, then the request can be granted.
    4. If a request comes in that is exactly the current available resources, then the request must be denied.
    5. If one process has no more "need", then the system is in a safe state.
    6. There can only be at most one safe sequence.
    7. It is possible to have a safe sequence but the system is not in a safe state.
    8. The safe sequence is the order in which the processes will execute.
    9. If there are more than one safe sequence, the Banker does not need to select one.
    10. If there is only one safe sequence, then each process must return it's resources before the next process can run.

  3. a) Construct a circuit diagram for a 4x1 multiplexer.

    b) Let F(a, b, c) be given by the following truth table:

    a b c | F
    ------------
    0 0 0 | 0
    0 0 1 | 1
    0 1 0 | 1
    0 1 1 | 0
    1 0 0 | 1
    1 0 1 | 1
    1 1 0 | 0
    1 1 1 | 0

    Implement F using only a 4x1 multiplexer and a single inverter. Use a block diagram for the multiplexer.

  4. Design a fully simplified 3-bit sequential circuit that goes through the sequence 000, 010, 100, 111, 000, 010, 100, 111, 000, 010, ...
    Use JK or D flip-flops. Show all work and draw the circuit diagram.

PROGRAMMING LANGUAGES AND COMPILER DESIGN

  1. Discuss the role played by activation records in programming languages and discuss possible implementation strategies for managing them. Your discussion should include the content of activation records, possible data structures for implementation, issues of language design that affect the design and implementation of activation records. Recommended: outline (list) the topics and then fill-in short descriptions.

  2. Multiple choice: CIRCLE all that apply (on your answer sheets, list all letters that apply for each numbered problem). There will be a penalty for guessing.

    1. Top-down parsers
       a) attempt to find the rightmost derivation.
       b) attempt to construct a parse tree from the root, creating nodes in "preorder".
       c) include predictive parsers.
       d) include SLR parsers.
       e) include recursive-decent parsers.

    2. Recursive-descent parsers
       a) may use backtracking.
       b) must use backtracking to avoid infinite loops on left-recursive grammars.
       c) include predictive parsers.
       d) do not require analysis of FIRST and FOLLOW sets.
       e) implement bottom-up parsing algorithms.

    3. LR parsers can
       a) parse all grammars that any predictive parser can, and more.
       b) NOT detect a syntactic error as soon as it is possible on a left-to-right scan.
       c) are more powerful than SLR.
       d) less powerful than LALR.

    4. LL(1) parsers are able to handle
       a) some left-recursive grammars.
       b) some right-recursive grammars.
       c) all unambiguous grammars.

    5. LR parsers are able to handle
       a) some left-recursive grammars.
       b) some right-recursive grammars.
       c) all unambiguous grammars.

  3. Consider the following C++ program. 
    void f(int a, int &b, int *c, int d[], int e) {
  b = 4*a;
  a = 5;
  *c = 8;
  d[0] = 7;
  e = 10;
}
int main () {
  int i = 1;
  int j = 2;
  int k = 3;
  int *p = &k;
  f(i, i, &j, &j, *p);
  cout << i << " " << j << " " << k << " " << *p << " " << endl;
}

    a) Briefly describe the interaction between the actual and formal parameters, including what is copied in to the function; and what restrictions, if any, are placed on their use"

    b) What is the output of the program?

  4. Consider an entire program which consists of two basic blocks where block B1 flows into block B2. There is also a shorter alternative to block B1 called B1'. Note: b and c are input values; f and g are required output values.
    B1:                               B1':
    1. a := b + c 8. a := b + c
    2. t1 := a + c 9. t2 := a + c
    3. d := t1 + b 10. e := a
    4. e := b + c 11. d := t2 + b
    5. d := d + c
    B2:
    6. f := b * c
    7. g := a * e

    a) Define "live" name.
    b) Using your definition, what names are live upon exit from B1?
    c) Define "equivalent" basic blocks.
    d) Are B1 and B1' equivalent?
    e) Describe the different types of structure-preserving transformations that have occurred from block B1 to B1'.