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

DATA STRUCTURES, ANALYSIS OF ALGORITHMS AND COMPUTATIONAL COMPLEXITY

  1. Given a binary tree, write a function which returns the count of the number of interior nodes (i.e. not a leaf node). An empty tree has no interior nodes. Code in the language of your choice and include declarations for your data structure. Do not code any other functions.

  2. Consider two linked lists, L1 and L2, both sorted in ASCENDING order of their integer elements. Write a function called "reverse_intersection" which is provided the two lists and will return an entirely new list L3 which is the reverse intersection of the elements of the two input lists. That is, L3 will be in descending order and contain those elements that are common to both L1 and L2.

    Example: 

    L1->[2]->[9]->[17]
L2->[3]->[9]->[12]->[17]->[20]
L3->[17]->[9]

    There will no be duplicates within a list. Code in the language of your choice. The C version of the function prototype (signature) is: 

    node_ptr reverse_intersection(node_ptr L1, node_ptr L2)

  3. Consider the standard mergesort algorithm to sort the array of "elements" a[0], ..., a[n-1].
    a) Construct the recurrence relation that describes the worst case number of array entry comparisons as a function of n, where n is any positive integer.
    b) Solve this recurrence relation under the additional assumption that n = 2k, where k is a positive integer. Your answer should be a precise function of n in closed form.

  4. a) Define "polynomial transformation".
    b) State precisely what must be shown to prove A <=P B.
    c) if A <=P B and A is NP complete, what can be said about B?
    d) if A <=P B and B is NP complete, what can be said about A?

COMPUTER ARCHITECTURE AND OPERATING SYSTEMS

  1. In the context of variable partition memory management schemes:

    a) Briefly explain the First-Fit algorithm.

    b) Briefly explain the Best-Fit algorithm.

    Given a variable partition memory management scheme with the following free list:

    Free element Size in KB
    1 100
    2 500
    3 200
    4 300
    5 600
    This free list may be represented as (100, 500, 200, 300, 600); use this notation in your table below.
    The following memory requests will be received in order: 212, 417, 112, 426 (size in KB).

    c) Show how memory is allocated using the First-Fit algorithm by filling in this table:

    Request # Size in KB Request Satisfied (Y/N)? Updated Free List
    1 212 Y/N (                        )
    2 417 Y/N (                        )
    3 112 Y/N (                        )
    4 426 Y/N (                        )
    d) Repeat for the Best-Fit algorithm beginning, again, with the original free list.

  2. Consider this solution for a Producer-Consumer sharing a bounded buffer of size N. 
    Producer:                          Consumer:
  while (true) {                     while (true) {
    wait(A);                           wait(B);
    wait(C);                           wait(C);
    /* put into the buffer */          /* take out of the buffer */
    signal(C);                         signal(C);
    signal(B);                         signal(A);
  }                                  }

    The problem is to consider the effects of the initialization of the semaphores A, B, C with respect to i) a correct solution and whether the solution guarantees ii) mutual exclusion, iii) no deadlock, and iv) no starvation. The table below has five different initializations and for each initialization answer Yes/No to the previous four questions. Draw this table on your solution paper. Note: The definition of starvation here is that it is possible for only one of the two processes to make progress.

    Warning: do NOT guess, just leave blank (+1 point for correct answers, 0 point for blanks, -1 point for incorrect answers).

    A=N,B=0,C=0A=0,B=N,C=1A=N,B=0,C=1A=0,B=0,C=1A=N,B=0,C=2
    Correct Solution: Y/N Y/N Y/N Y/N Y/N
    Guarantees Mutual Exclusion: Y/N Y/N Y/N Y/N Y/N
    Guarantees No Deadlock: Y/N Y/N Y/N Y/N Y/N
    Guarantees No Starvation: Y/N Y/N Y/N Y/N Y/N

  3. Rewrite F(a,b,c,d) = S (0,3,4,6,7,8,10,12,14) in simplified product-of-sums form.

  4. Design the needed hardware that would allow for the execution of Arithmetic and Logical Instructions of a generic microprocessor. The processor has a register file that consists of eight 8-bit registers and an 8-bit ALU. It uses a two-operand addressing format where a register can be the source of one operand and also the destination register. For example, the following are typical instructions:

    ADD R1, R2         T1 <- R1 + R2
    SUB R1, R1 R1 <- R1 - R1
    AND R3,R4 R3 <- R3 and R4

    The instruction format for "op rd, rs" is as follows: opcode(4 bits) rd(3 bits) rs(3 bits) plus other fields that are not needed for this problem.

    Draw a diagram showing how such a scheme can be implemented. Clearly label the components and connections in your design and write a brief explanation of your approach. You may use block diagrams for standard components you may need, such as encoders, decoders, multiplexers, shifters, counters, etc. The following is the beginning of the diagram.

PROGRAMMING LANGUAGES AND COMPILER DESIGN

  1. Show the output of the program (in a language that is not C++ but has similar syntax) listed below if the language uses:

    a) dynamic scope and call by value-result
    b) static scope and call by reference
    c) static scope and call by value

    Show your work in terms of activation records. 

    int a, b, c;
int g(int x, int y) {
  c = 2;
  x++;
  y--;
  a = x + c;
  return (x-y);
}
void f(int x) {
  int a = x+3;
  b = g(a,c);
  x = x + b;
}
void main() {
  a = 3;
  b = 5;
  c = 7;
  f(b);
  print(a,b,c);
}

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

  3. Consider storage-allocation strategies.

    a) Describe the static storage-allocation strategy.
    b) Describe the stack storage-allocation strategy.
    c) Describe the heap storage-allocation strategy.

    Be sure to compare the strategies and describe differences between the strategies (including lifetimes, visibility, efficiency, etc.).

  4. Consider the following declaration of a C structure: 
    struct y {             struct id {
  float x;       or      float id;
  int i;                 int id;
};                     };
    The following LL(1) grammar can be used to define this part of the C language: S -> struct id { L };
    L -> F L | e
    F -> T id;
    T -> int | float
    where the terminal symbols (tokens) are: struct id { } ; int float and the nonterminals are: S, L, F, and T.

    a) Show the set of terminals belonging to FIRST(S), FIRST(L), FIRST(F), FIRST(T).
    b) Compute FOLLOW of these non-terminals.
    c) Using your results from a) and b), construct an LL(1) parsing table.
    d) Using your result from c), begin the parse of the example above assuming that y, x, i are all replaced with the terminal id. Show the contents of the stack and how the input is consumed (show at least the first five steps).