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

DATA STRUCTURES, ANALYSIS OF ALGORITHMS AND COMPUTATIONAL COMPLEXITY

  1. Consider a Binary Search Tree (BST) with integer keys. Assume these integer keys are inserted into the tree in this order: 10, 4, 7, 15, 12, 13, 5.

    a) Draw the BST after the insertion of the keys.

    b) Code an ITERATIVE function called "find" in the language of your choice. The function should return a pointer to the node containing a specified key. If the key is not found, then return NULL. Also, declare your data structure. The signature (prototype) in C: tree_ptr find(int x, tree_ptr p).

    c) Code a RECURSIVE version of the function.

  2. For each of the algorithms listed below, state the average-case BIG-THETA (Q) running time. In general, assume n is the size of the data set and, in particular for graph algorithms, assume n is the number of vertices and m is the number of edges. For graphs, assume the adjacency list implementation. On your answer sheets, number your answers 1..20.

    Warning: do NOT guess, just leave blank (+1 point for correct answers, 0 point for blanks, -1/2 point for incorrect answers).
    1. Hash Table: Find Key 11. Sorted Linked List: Insert Key
    2. Hash Table: Find Minimum Key 12. FIFO Queue as Circular Array: Enqueue Key
    3. Binary Search Tree: Find Key 13. Stack: Pop
    4. Binary Search Tree: Delete Key 14. Insertion Sort
    5. MinHeap (Priority Queue): Delete Minimum Key 15. Quicksort
    6. MinHeap (Priority Queue): Find Key 16. Mergesort
    8. Sorted Array: Find Key 17. Heapsort
    7. Unsorted Array: Insert Key 18. Graph: Depth-First Search
    9. Sorted Linked List: Find Key 19. Graph: Dijkstra's Shortest-Path
    10. Unordered Linked List: Insert Key 20. Graph: Prim's Minimum-Weight Spanning Tree

  3. Let G be a connected graph with n vertices and m edges. The edges are stored using the adjacency list implementation.

    a) Write a routine to perform a breadth-first-search traversal on G. Code in the language of your choice. For fundamental local data structures (stack, queues, etc.), you may call functions for the basic operations without writing the actual code.

    b) State in BIG-THETA (Q) terms the runtime of your routine. Your answer should be the best description as a function of n and m. Justify your answer.

  4. a) Define "NP-Complete decision problem".

    Consider these six classic NP-Complete problems: 3-SATISFIABILITY, 3-DIMENSIONAL MATCHING, VERTEX COVER, CLIQUE, HAMILTONIAN CIRCUIT, PARTITION.

    b) Define precisely and concisely any ONE of the above problems.

    c) Give a yes-instance, explaining WHY it is a yes-instance.

    d) Give a no-instance, explaining WHY it is a no-instance.

COMPUTER ARCHITECTURE AND OPERATING SYSTEMS

  1. Consider the following faulty code for a Producer-Consumer pair sharing a bounded buffer [0..N-1]: 
    Producer:                                      Consumer:
  while (true) {                                 while (true) {
    while (counter == N) {} // empty loop body     while (counter == 0) {} // empty loop body
    buffer[in] = ch;        // produced character    ch = buffer[out];  // consumed character
    in = (in + 1) % N;                               out = (out + 1) % N;
    counter = counter + 1;                           counter = counter - 1;
  }                                              }

    Assume that global shared variables have current values: N=2, counter=1, out=0, in=1. Describe an execution sequence such that the Producer thinks the buffer is full when, in fact, the buffer is not full, thus illustrating the faulty code. Use any combination of description, diagrams, charts, etc. to help describe the execution sequence.

  2. Consider resource allocation graphs with a set of processes P = {P1, P2, P3}, a set of resources R = {R1, R2, R3}, and a set E of request (Pj®Ri) or assignment (Ri®Pj) edges. R1, R2, R3 have 1, 2, 1 instances, respectively.

    In each of the following, draw the graph and state whether deadlock exists or not. Briefly explain each answer.

    a) E = {P1®R1, P3®R2, R1®P2, R2®P2, R2P1, R3®P3, P2®R3}
    b) E = {P1®R1, P3®R2, R1®P2, R2®P2, R2®P1, R3®P3}
    c) E = {P1®R1, R2®P3, R1®P2, P2®R2, R2®P1, R3®P3}

    Note: the bold edges are intended to highlight the differences between the graphs.

  3. A simple ALU performs ADD, SUB, AND, OR, and XOR. Draw a diagram for a 1-bit slice of the ALU. You should assume decoded control lines. Use a block diagram for the full adder.

  4. Show the circuit diagram for a 5-bit counter that increments the stored value on each clock pulse. It should use JK flip-flops and be a lookahead counter that minimizes gate delay.

PROGRAMMING LANGUAGES AND COMPILER DESIGN

  1. a) Describe the important differences between interpretation versus compilation.

    b) What are the particular advantages or disadvantages of interpretation versus compilation?

    c) Are all languages either compiled or interpreted? Explain.

    d) Some languages support multiple-inheritance and others (like Java) do not. Explain the advantages and disadvantages of multiple inheritance.

  2. Consider these following examples of a Uniform Resource Locator (URL): 
    http://server
http://server.company.com
http://server.company.com/
http://server.division.com/dir1/dir2/myfile
http://server.division.com/myfile.cgi
https://server.division.company.com:80/dir1/dir2/myfile.html
rmi://server.company.com/dir1/myobject
    where the terminal symbols (tokens) are: http https rmi html cgi : / . id num

    Notes:

    1. server, division, company, com, dir1, dir2, myfile, myobject are examples of the terminal id.
    2. Port number (e.g. 80) is an optional num (introduced by a ":"), with at most one number following the server name.
    3. Protocol (e.g. http) is mandatory.
    4. Assume each server is one or more id, and is "." separated.
    5. A list of directories is zero or more id, and is "/" separated, followed by an optional file name.
    6. A file name may have an optional suffix (cgi or html) and, in this case only, would a "." appear in the file name.

    Construct a grammar for this subset of the URL language.

  3. Given the grammar A ® aBa | aC
    B ® aA | bb
    C ® aAa     with start symbol A,

    a) Prove the grammar is ambiguous using the string "aaabbaa".

    b) Use standard transformations to remove the common prefixes in the grammar.

    c) Is the revised grammar ambiguous? Prove/disprove.

  4. Given this subset of standard intermediate code: SUB var, regi     performs     regi = regi - var
    SUB regj, regi     performs     regi = regi - regj
    MOV var, regi     performs     regi = var
    MOV regi, var     performs     var = regi
    where var represents variables a, b, ..., or temporary variables t1, t2, ... and regi represents register R0, R1, ..., Rr-1 (r is the total number of available registers) and the following Directed Acyclic Graph (DAG): 
          [-]
     /   \
  [-]     [-]
  / \     / \
[a] [b] [c] [-]
            / \
          [-] [f]
          / \
        [d] [e]

    a) Write the expression, using parentheses, which corresponds to the above DAG.

    b) Write the optimized standard intermediate code assuming r=1 and count the number of statements. "Optimized" means that the number of statements should be minimal. The result should reside in register R0.

    c) What is the minimum value of r required to achieve the fewest number of statements? That is, increasing r has no effect on the the number of required statements. Briefy explain.