Department of Mathematics and Computer Science
Comprehensive Exam--Computer Science
Sample Exam for Fall 2006

DISCLAIMER: This is a sample exam to show the new structure, and is not an indication of the actual problems that will appear on an exam. The problems are from past exams, with the exception of Automata Theory.

DATA STRUCTURES (1.5 hours)

Given 3 Data Structure problems, choose 2 out of 3:

  1. Consider a single-linked list of character elements, for example: 
     c -> a -> f -> r -> q

    Write a non-recursive function, in the language of your choice, which reverses all of the pointers, for example: 

     c <- a <- f <- r <- q

    The function should return a pointer to the last node in the list (and this node is effectively the new head of the list). An initial call would be: 

     p = reverse(p);
    The nodes in the list just have a single pointer, not two pointers. Do not build a new list. Simply modify the pointers in the current list. The running time of your function should be O(n) (where n is the number of list entries) and should only use O(1) extra memory. Declare your data structures and do not include a dummy header.

  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 a sorted array of n non-negative integers. Write an iterative function, in the language of your choice, which finds a key x within the array and returns its index position. If the key does not exist, then return -1. Your algorithm should have a BIG-OH which is optimal.

SYSTEMS (1.5 hours)

Given 2 Operating Systems problems and 1 Architecture problem, choose 2 out of 3:

  1. 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?

  2. 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.

  3. 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.

THEORY (1.5 hours)

Given 1 Programming Languages problem, 1 Analysis problem, 1 Theory of Computation problem, choose 2 out of 3:

  1. a) Define "aliasing".
    b) Discuss aliasing in the context of the following C++ program. In particular, what are the different types of aliasing that occur?
    c) What is the output from this program? 
    int i = 2;
int j = 3;
int a[4] = {3, 7, 2, 2};

int f(int &x, int &y) {
  int *p;
  int *q;
  p = &j;
  q = p;
  a[i] = a[j--];
  return (i + j + a[i] + a[j] + *p + *q + x + y);
}
int main() {
  cout << f(i,i) << endl; 
}

  2. Let G be a connected weighted graph with n vertices and m edges. The edges are stored using the adjacency matrix implementation. The vertices are v0, ..., vn-1

    a) Write a routine to construct the shortest path from vertex u to vertex w. Code in the language of your choice. For fundamental local data structures (stack, queues, priority queues, etc.), you may call functions for the basic operations without writing the actual code.

    b) State in BIG-THETA terms the worst case runtime of your routine. Your answer should be the best description as a function of n and m. Note the fundamental local data structure implementations if they affect the result. Justify your answer.

    Fall 2006: students may elect to choose one problem from Theory of Computation. This problem will be EITHER Complexity OR Automata Theory:

  3. Convert the following context-free grammar into Chomsky normal form:
          S --> ASA | aB
          A --> B | S
          B --> epsilon

    Some other examples for Automata Theory:

    Show the state diagram for a PDA that recognizes {0n#1n | n > 0}.

    Construct a PDA from the following CFG:
          S --> aTb | b
          T --> Ta | epsilon

    Show that the class of regular languages is closed under the concatenation operator.

    Use the Pumping Lemma to show that the language {anbncn | n > 0} is not context-free.

    Draw the state diagram for a DFA recognizing the language L = {w | w starts with 1 and |w| is even, or w starts with 0 and contains an even number of 0s}

    Convert a NFA into an equivalent DFA.