Department of Mathematics and Computer Science
Comprehensive Exam--Computer Science
Fall 2005

DATA STRUCTURES

  1. Consider a singly-linked list of nodes, where each node contains an integer and a pointer.

    a) [6 points] Write an ITERATIVE function that returns the count of the number of nodes in the list. Code in the language of your choice and declare your data structure.

    b) [8 points] Repeat using RECURSION.

    c) [6 points] State which solution is better and give a brief justification.

  2. Consider a doubly-linked list of nodes which contain character elements. For example, 
    next:   ->   ->   ->   ->        
      c    a    f    r    q
prev:   <-   <-   <-   <-

    Write a function, in the language of your choice, which reverses all of the pointers. For example, 

    next:   <-   <-   <-   <-        
      c    a    f    r    q
prev:   ->   ->   ->   ->

    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);
    where p is a pointer to the current head of the list. 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.

  3. Consider the following MinHeap (Priority Queue) implemented as a binary tree with pointers. For example, 
            5
      /   \
    13     7
    / \   / \
  14  20 9  15
     /    \
    25    12

    Note that the tree is unbalanced. Do not worry about how it was constructed.

    Consider a breadth-first search of the tree: 5, 13, 7, 14, 20, 9, 15, 25, 12.

    Now, consider this variation of the search to find a specific key: Perform the breadth-first search but if a key is found that is larger than the search key, the sub-tree does not need to be searched. For example, if the search key is 9 in the tree above, then the search would scan 5, 13, 7, 9. That is, the search does not need to examine the sub-tree rooted at 13.

    Program in the language of your choice. You do not have to write the code for any fundamental operations on local data structures you use. The function should return a pointer to the node containing the search key, or NULL if not found. Here is the prototype in C: 

      tree_ptr find(int x, tree_ptr root)

SYSTEMS

  1. Consider this version of Producer-Consumer problem. 
    const int N = 5;
Semaphore A = N;     // initial value of the semaphore
Semaphore B = 0;     // initial value of the semaphore
int buffer[0..N-1];  
int i = -1;

Producer:                                    Consumer:
  while (true) {                               while (true) {
    wait(A);                                     wait(B);
    i = i + 1;                                   ch = buffer[i];  // consumed character
    buffer[i] = ch;  // produced character       i = i - 1;
    signal(B);                                   signal(A);
  }                                             }

    a) What are the main differences between this version and the standard version?

    b) Demonstrate that the code is faulty because it can accidentally re-consume the same character from the buffer.
    Use any combination of diagrams, charts, description, line numbers, etc.

    c) How could this fault in b) be prevented?

  2. Consider page replacement algorithms.

    a) [5 points] Define the LRU algorithm.

    b) [10 points] Describe the second-chance page replacement algorithm, sometimes known as the "clock" algorithm.

    c) [5 points] Describe the generalized form of this algorithm where a record of past reference bits are maintained.

  3. This sequential circuit has its outputs connected to a display with possible outputs from 0 to 7. What sequence of digits will it display as it is clocked? Begin with the state 0 = 000.

  4. Click here for Architecture problem.

THEORY

  1. Consider this example of an Email message: 
    To:Henry.James@csueastbay.edu Mark.Twain@sybase.com 
From:Rudyard.Kipling@cisco.com
Subject:Here is my subject
Body: This is an example email. Note that it can be addressed
to multiple users. The Subject contains one line of text (a sentence), consisting
of words, but the Body can contain multiple sentences, even blank sentences.

This is the last line of the Email message.
    where the terminal symbols (tokens) are: To:    From:    Subject:    Body:    address    word

    Notes:

    1. Examples of the terminal address are:
         Henry.James@csueastbay.edu
         Mark.Twain@sybase.com
         Rudyard.Kipling
    2. Examples of the terminal word of text are:
         Here
         multiple
    3. To:, From: always have some contents.
    4. Subject:, Body: may be empty.
    5. Do not worry about spaces or newlines: white space is ignored.

    Read the description of the language carefully. Construct a BNF grammar for this subset of the Email definition language. Do not do use any extensions such as EBNF or other BNF variants.

  2. Solve the recurrence relation T(n) = 2T(n/2) + n2 where T(1)=1 and n=2k for a nonnegative integer k. Your answer should be a precise function of n in closed form.

    You may choose 3A or 3B, but not both.

  3. A) Give the state diagram for a pushdown automaton that recognizes the language

    PALINDROME={w : w=wR}

    over the alphabet S={0, 1}.

  1. B) A Turing machine with Stay-Put
    S=(S, G, Q, qaccept, qreject, qstart, d)

    is similar to a standard Turing machine model M in all respects except that its transition function is defined as
    d: Q × G® Q × G× {L, R, S}
    where S is an additional tape directive that allows the read/write head to remain stationary after writing a symbol to the tape. Show that S is equivalent in computational power to a standard Turing Machine (i.e., Turing-Complete computational model).