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

DATA STRUCTURES, ANALYSIS OF ALGORITHMS AND COMPUTATIONAL COMPLEXITY

  1. Consider the hash table data structure. There are two fundamentally different storage declarations to implement a hash table. By "fundamental", we mean that the data structure for storage will be different, not just a different collision strategy.

    a) Describe in words and diagrams (with example data) the two different implementations. Discuss each one in general but also be sure to describe how each one handles collisions.

    b) For each of the two implementations, state in BIG-THETA (Q) terms the average case and the worst-case performance for the find operation.

  2. Consider two linked lists, L1 and L2, both sorted in DECREASING order of their integer elements. Write an efficient function called "eliminate" which is provided the two lists and will delete from the second list L2 those integers that are also found on the first list L1. You may assume there are no duplicates within a list; that is, all the elements within a particular list are unique. Code in the language of your choice and include declarations. Please state whether you assume your list data structure has a dummy header node or not.

    Example: 

                 L1: [25] [17] [10] [9] [2]
     before: L2: [17] [12] [9]  [3]
     after:  L2: [12] [3]

  3. Let G be a connected graph with n vertices. The edges are stored as an adjacency matrix int a[n][n] (or perhaps bool a[n][n]).

    a) Write a recursive routine to perform a depth-first-search traversal on G. Give the initial call and any data structures (including their initialization) that are used. Code in the language of your choice.

    b) State in BIG-THETA (Q) terms the runtime of your routine.

  4. Consider the following decision problem.

    INSTANCE: A polynomial p(x1, ... , xn) of degree k in n variables having integer coefficients.

    QUESTION: Do there exist integers a1, ... , an such that p(a1, ... , an) = 0?

    a) This problem has been proved to be "undecidable". Define "undecidable".

    b) Why does the following argument NOT prove that this problem is in NP?

    "Guess values for a1, ... , an and carry out the evaluation. Since the number of multiplications and additions required will be bounded by the size of the polynomial, this can be carried out in polynomial time."

COMPUTER ARCHITECTURE AND OPERATING SYSTEMS

  1. Consider a computer system with demand paging.

    a) Briefly explain the term "page fault".

    b) Briefly explain the term "page replacement policy"

    c) Briefly explain how the LRU policy works.

    d) In demand paged memory management that uses LRU, a process makes the following sequence of page references:

    1 3 4 2 1 1 2 3 4 3 5 1 4 6 1 4 3

    Calculate the number of page faults, assuming that only 3 page frames are available to the process. Assume that no pages are initially loaded. Show your work.

  2. Suppose there are N worker processes (0..N-1), each with a critical section where work is done. There is also a special process which executes the following code: 
         int p    = -1;    // GLOBAL variable shared by all processes, initialized once
     int lock = 0;     // GLOBAL variable shared by all processes, initialized once
     
     while (1) {
       while (lock == 1) {}   // empty loop body
       p = (p+1) % N;
     }

    Each worker process has its own process ID mypid, and executes the following code: 

         while (1) {
       while (p != mypid) {}   // empty loop body
       lock = 1;
       // CRITICAL SECTION WHERE THE PROCESS DOES WORK
       lock = 0;
     }
    Answer YES/NO to the follow questions and provide a brief description.

    a) Does the solution guarantee mutual exclusion?

    b) Does the solution guarantee that work will be done?

    c) Does the solution guarantee fairness?

  3. Design a combinational circuit that multiplies a 3-bit unsigned integer (a2 a1 a0) by a 2-bit unsigned integer (b1 b0) using only AND gates, half adders, and full adders. The product should be a 5-bit unsigned integer (p4 p3 p2 p1 p0).

  4. Derive the state table and the state diagram for the given sequential circuit.

PROGRAMMING LANGUAGES AND COMPILER DESIGN

  1. The following is a language X that uses C-style syntax for declarations. 
       void f() {
       int a[n];
       int b[m];
       ...}

    a) The language X should have a rule for when the values for n and m must be bound to actual values. List all possibilities for this binding time.

    b) Suppose that X allows assignment on arrays, as in a := b. It must have a rule that states when arrays are assignment compatible. List the possible rules that X could use and briefly explain each.

  2. Is the following grammar LL(1)? Is it SLR(1)? Explain completely.

    S --> A S | a A
    A --> b A | e

  3. Assume a language has C-style syntax. It uses static scope rules. Default parameter passing is by value. Functions may be passed as parameters. Consider the example below in this language. 
         int a = 32;

     int f(int x){
       return(x*a);
     }

     int g( int h(int); int z){  return h(z);}

     int main(void){
       int a = 64, b = 10;
       a = g(f, b);
       print(a);
     }

    a) Display the runtime stack when it is at its highest point. Include all important information.

    b) What does this program print? Explain.

  4. a) Translate the following source code into a standard intermediate code (not optimized).

    a = a+b+c*d*(a+b)

    b = a+b+c*d

    b) Write the DAG (directed acyclic graph) that corresponds to the intermediate code in a).