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

DATA STRUCTURES

1. Consider a QUEUE with enqueue and dequeue methods, and the usual First-In First-Out (FIFO) property. Implement this queue as a SINGLY-LINKED LIST in the language of your choice. Be sure to consider the appropriate function declarations and initializations. Assume the data type in the queue is just positive integers. An attempt to dequeue from an already empty queue should return a -1 value. The allocation and deallocation of memory should be appropriate for the language of choice.

2. Given a BINARY TREE of integer elements, write an ITERATIVE function that scans along the extreme right side of the tree (this is equivalent to a linked list). During this scan, create (and eventually return) a new SINGLY-LINKED LIST that contains nodes with the same elements as the right side of the tree. However, the new list should be in REVERSE order of the scan of the right side. Be sure to consider default conditions.

   For example, this tree:

           5
         /   \
        2     1
       / \   / \
     14  13 9   6
        /      /
       10    12
   

   would yield this list: 6, 1, 5.

   Code in the language of your choice, and include declarations of your data structures (plural).

3. Consider a HASH TABLE (size = 100) in which collisions are handled by chaining with DOUBLY-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 locates the node containing a specified search key, and returns a pointer to the node (or NULL).

   b) Write a function which deletes the node containing a specified search key. The delete function must utilize the find function in part a). If the node does not exist, do nothing.

   Code in the language of your choice, and include the declaration of your data structure. Each list has a dummy header that you can assume is always present. Do not worry about returning the node to memory.

SYSTEMS

1. Consider the following code for N (>0) readers and a SINGLE writer.

   // Global Variables, initialized once:
   int readcount = 0;
   boolean readOK = true;
   boolean writeOK = false;
   
   Readers:                                 Writer:
     while (true) {                           while (true) {
       while (!readOK) {}                       while (!writeOK) {}
       readcount++;
       // read data section                     // write data section
       readcount--;
       if (readcount == 0) {
         readOK = false;                        writeOK = false;
         writeOK = true;                        readOK = true;
       }
     }                                        }
   

   Answer the following questions YES/NO, with an explanation.

   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)?

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

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

2. Consider page faults in a virtual memory system with demand paging. In particular, consider the behavior of FIFO, LRU, LFU, and OPT page replacement strategies. The physical memory has exactly 3 frames (0..2) and the logical memory has only 4 pages (0..3). In each of the following three parts, make up your own page reference string that guarantees exactly 1 page fault and:

   a) LRU = FIFO = OPT. That is, all three strategies behave exactly the same. In particular, the page reference string should be of length 6, and the final physical memory, starting from frame 0, should contain 3, 1, 2.

   b) LRU = FIFO = LFU. In particular, the page reference string should be of length 6, and the final physical memory, starting from frame 0, should contain 3, 1, 2.

   c) LRU = OPT <> FIFO. In particular, the page reference string should be of length 7, and the final physical memory, starting from frame 0, should contain:

        LRU = OPT: 0, 3, 2
        FIFO: 3, 1, 2

3. Design a fully simplified 3-bit mod 6 down counter with your choice of J-K, D, or T flip-flops. The circuit decrements each clock pulse, going through the sequence 0, 5, 4, 3, 2, 1, 0, 5, 4, 3, 2, 1, 0, 5, 4, ... . Show the circuit diagram.

THEORY

1. Given the following main and the function "sum" declaration, draw the program stack at the marked line inside of the function "sum".

   int sum(int len, int nums[]) {
      int result = 0;
      // DRAW STACK HERE
      for (int i = 0; i < len; i++)
         result = result + nums[i];
      return result;
   }
   
   int main() {
      int list[] = {10, 30, 20};  // list starts at address 0x22ff60
      int length = 3; // at address 0x22ff6c
   
      int x = sum(length, list);
      // rest of program omitted
   }
   

   Draw the stack assuming each of the following parameter passing mechanisms:

   a) call-by-value

   b) call-by-reference

   Assume that BOTH parameters to "sum" follow the specified mechanism. Be sure to include all types of information that would appear in the stack.

   [WARNING: the syntax matches C/C++ and is close to Java, but the semantics of the parameter passing mechanisms is not tied to any language.]

2. Let G be a connected graph with V vertices and E edges. The edges are stored using the adjacency lists implementation.

   a) Write a recursive routine to perform depth-first-search traversal on G. Declare any data structures, including their initialization. Assuming a specified starting node, give the initial call. Code in the language of your choice.

   b) State in BIG-THETA terms the runtime of your routine as a function of V and E.

3. Consider the language consisting of strings of balanced brackets - that is, such strings as [ [ ] ], [ ] [ [ ] ], [ ] [ ] [ ].

   a) Does this language have a context free grammar? Either write a grammar or show that there is no such grammar.

   b) Does this language have a regular expression or deterministic finite automaton? Either write a regular expression (or deterministic finite automaton) or show that one does not exist.