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

DATA STRUCTURES, ANALYSIS OF ALGORITHMS AND COMPUTATIONAL COMPLEXITY

  1. Consider a general tree where a node can have zero or more children. An efficient data structure, with respect to storage, is for each node to have a child pointer and a sibling pointer. For example, the tree below has a root A which has three children B, C, and D. Essentially, the sibling pointers form a linked list of children of one parent. If the child pointer is NULL, then a node has no children. If a sibling pointer is NULL, then this is the last child in the linked list. The root does not have any siblings. 
    A
|
v
B---->C---->D
|     |
v     v
E->F  G
    The data structure, in C, is declared as: 
    typedef struct tree_node *tree_ptr;
struct tree_node {
  char element;
  tree_ptr first_child;
  tree_ptr next_sibling;
}
    Write a recursive function, in the language of your choice, to check if the general tree qualifies as a binary tree. That is, return true (1) if, and only if, each node in the tree has 0, 1, or 2 children. Otherwise, return false (0). Assume that an empty tree also qualifies as a binary tree. Note that the example above would not qualify as a binary tree because A has three children.

  2. Consider a stack with push and pop methods and the usual Last-In First-Out (LIFO) property. Implement this stack as a singly-linked list in the language of your choice. Be sure to include signatures for your push and pop methods along with declarations and initializations. The pop method should both return a value and remove it from the stack. Assume the data type in the stack is just an integer. An attempt to pop from an already empty stack should return -1.

  3. a) Write the code, in the language of your choice, for either selection sort or insertion sort to put a[0]...a[n-1] into ascending order. Assume that the array is declared by element a[n], where "element" has already been declared. Variables of type element may be compared and assigned using the usual relational and assignment operators.

    b) Give a big-theta description, along with a brief explanation, of the worst case number of

    (i) element comparisons and
    (ii) element assignments     in your algorithm.

  4. Consider the problem PRIME: Given a positive integer n, is n a prime? Also consider the following algorithm, expressed in C-like language. 
    prime = true;
for (i=2; i <= sqrt(n); i++)
  if ( n%i == 0) {
    prime = false;
    break;
  }
if (prime) print(n, " is prime");

    For each of the classes below, can the above algorithm be used to prove the problem PRIME lies in the class? Explain each answer.

    P     NP    NP-complete    co-NP    PSPACE

    COMPUTER ARCHITECTURE AND OPERATING SYSTEMS
    1. Recall the Readers-Writers problem where, as usual, any number of readers can examine a file but only one writer at a time can update the file. Consider the following code as a potential solution.

      For each reader process: 

        while (1) {
1.  wait(sem_readcount);
2.  readcount++;
3.  signal(sem_readcount);
4.  if (readcount==1) wait(sem_wrt);
    
    /* reader reads from the file */

5.  wait(sem_readcount);
6.  readcount--;
7.  signal(sem_readcount);
8.  if (readcount==0) signal(sem_wrt);
  }
      For each writer process: 
        while (1) {
9.  wait(sem_wrt);

    /* writer writes to file */

10. signal(sem_wrt);
  }
      Assume that each semaphore is initially available and that readcount is zero.

      a) Is the solution correct? YES/NO

      In each of the following, your answer should be either

      i) HAS NO EFFECT

      ii) IS NEEDED FOR A CORRECT SOLUTION

      iii) MAKES FOR AN INCORRECT SOLUTION

      Include a brief explanation. Note that each question is independent, that is, it assumes the original code above.

      b) What is the effect of swapping lines 1 and 2?

      c) What is the effect of swapping lines 3 and 4?

      d) What is the effect of swapping lines 7 and 8?

    2. Consider a computer system with virtual memory and recall that the long-term scheduler controls the "degree of multiprogramming" (the number of processes in memory).

      a) Define thrashing and its relationship to the degree of multiprogramming.

      b) Draw a typical graph of CPU utilization as a function of the degree of multiprogramming and describe why it has this shape.

      Now, the system is measured to determine the utilization of the CPU and the utilization of the disk used for swapping pages.

      For each of the following possible measurements, state (YES/NO) whether the CPU utilization would be expected to increase if the degree of multiprogramming was increased. Provide a brief explanation in each case. Hint: your graph in part b) can help provide your answers here.

      c) CPU utilization 13%; disk utilization 97%

      d) CPU utilization 13%; disk utilization 3%

      e) CPU utilization 87%; disk utilization 3%

      f) CPU utilization 87%; disk utilization 97%

    3. Design a fully simplified combinational circuit that has 2 control lines (C1 and C2) and 2 input lines (X1 and X2). The 2 outputs are F1 and F2. The circuit behavior is described by the table shown below: 

      C1   C2      F1   F2
-------      -------
 0    0       1    1
        
 0    1      X1   X2
        
 1    0       0    0
 
 1    1      X2'  X1' (these are complements)
      Draw the circuit diagram.

    4. a) Draw a block diagram for a simple accumulator-based microprocessor. Assume that the microprocessor has the following registers:

      AC (accumulator)
      TMP (temporary register)
      PC (program counter)
      AR (address register)
      MDR (memory data register)
      IR (instruction register)

      In your diagram you should show and label all the necessary components of the microprocessor and the necessary connections between the different units. The source inputs of the ALU are AC and TMP, while AC is also the ALU destination.

      b) Describe the sequence of events that takes place when the microprocessor executes the following instructions:

      (i) LDA $2000 (Load AC with the contents of location 2000 in memory.)

      (ii) ADA $2000 (Add the contents of memory location 2000 to AC.)

    PROGRAMMING LANGUAGES AND COMPILER DESIGN

    1. A subset of HTML might create a "PAGE" in the following required form. 
      <HTML> <TITLE>
      Some text goes here.
</TITLE> <BODY>
      <P>
	 This is a possibly multi-line "Paragraph"
         Below is an "Unordered List".
      </P>
      <UL>
      <LI> Text for first List Item.
      <LI> Text for second List Item, etc.
      </UL>
</BODY> </HTML>
      Some details of the language:

      1. Each tag (except the <LI> tag) is <...> and is matched by a closing tag </...>
      2. Outermost pair is <HTML> and </HTML>
      3. First pair is the <TITLE> pair, followed by one <BODY> pair
      4. <BODY> section is composed of any number of Paragraphs (<P> pairs) and Unordered Lists (<UL> pairs), which can occur in any order but may not be nested
      5. A Paragraph is any text included within the <P> and </P> pair
      6. An Unordered List is any number of List Items, where a List Item is: <LI>...text...
      7. Whitespace is not significant
      8. TEXT is a string of characters; characters are tokens. Thus, one can generate any text portion with the terminal token ch (which stands for any character) and the nonterminal TEXT with the rule:

        TEXT -> ch TEXT | empty

      a) List all tokens used in this language (ch is one; what are the others?)

      b) Give a simple BNF grammar that generates syntactically correct PAGEs

      PAGE -> ...
      ...
      TEXT -> ch TEXT | empty

    2. a) Define precisely "function overloading" and "function polymorphism."

      b) Suppose that an Object Oriented language has a class STUDENT with subclasses GRADSTUDENT and POSTBACSTUDENT. Also, suppose that each of the three classes above has its own "print()" method.

      Give simple examples of instances in which the correct "print()" method to call

      (i) can

      (ii) can not

      be determined at the time of compilation of the program. Explain.

    3. Suppose that a programming language specifically supports a datatype of upper triangular matrices: 

      real UpperTriangular a[n];  // a is an n by n matrix of real numbers
                            // all entries below main diagonal are zero
                            // diagonal has n entries a[0,0], a[1,1], ..., a[n-1,n-1]

real UpperTriangular b[3];  

// b could be:
//   1.1  3.4  -5.6
//     0  2.4   9.9  
//     0    0  -7.7

      a) Propose an efficient storage scheme for a compiler for this language to store the n(n+1)/2 nonzero entries.

      b) For your scheme, show the computation necessary (access function) to access element a[i,j].

    4. The following code segments are written in C (or C++); one of these segments is valid; one is not. 
        (i)                  (ii)
int x, y;            int x, y;   
y = 8;               y = 8;
x = - --y;           x = -- -y;

      a) Which segment is valid? What are the values of x and y after the valid code segment executes? Explain.

      b) Which segment is not valid? Explain. (If your answer is language or compiler dependent, explain also.)