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

DATA STRUCTURES, ANALYSIS OF ALGORITHMS AND COMPUTATIONAL COMPLEXITY

  1. Given a binary tree write a function that returns TRUE (1) if the tree has an even number of nodes. Otherwise, return FALSE (0). For example, consider a node which has two even sub-trees. What should the function return as result? Do not forget to consider the node itself. Code in the language of your choice and include the declarations of your data structure. You must also consider what the return value should be if the tree is NULL. Do NOT count the number of nodes (no credit will be given).

  2. Consider the five data structures in the table below (make your own table on your answer sheets). Fill-in the table with the average and worst-case BIG-THETA values for both the FIND (of a specified key) and DELETE operations. For the DELETE operation, assume that the FIND operation has already been performed (i.e. do NOT include the cost of performing the FIND in the performance of the DELETE).
    Warning: do NOT guess, just leave blank (+1 point for correct answers, 0 point for blanks, -1 point for incorrect answers).
    FIND DELETE
      AVG   WORST   AVG   WORST
    HASH TABLE        
    BINARY SEARCH TREE        
    MINHEAP (PRIORITY QUEUE)        
    SORTED ARRAY        
    SORTED DOUBLY-LINKED LIST        

  3. Consider f(n) and g(n).

    a) Define precisely

    (i) f Î o(g)        ("little-oh")

    (ii) f Î Q(g)         ("Big-Theta")

    b) Let
    f(n) = n3 - n + 5
    8n + 4     		and g(n) = n2.
    Precisely one of the following statements is true:

    (i) f Î o(g)       (ii) f Î Q(g)       (iii) g Î o(f).

    Which one of the three statements is the valid statement? Prove that your selection is correct. You do not need to prove that the other two statements are incorrect.

  4. a) Define "NP-Hard".

    b) Suppose that one has N files, of size s1, s2, ..., sN (in megabytes), to store on disk, and suppose that there are two K-megabyte disks available for storage.

    Show that the problem of deciding whether M files, for 1 <= M <= N, can be stored on the two disks is NP-Hard. You may assume that the standard Garey-Johnson list of problems are known NP-Complete: SATISFIABILITY, 3-SATISFIABILITY, 3-DIMENSIONAL MATCHING, VERTEX COVER, CLIQUE, HAMILTONIAN CIRCUIT, PARTITION.

COMPUTER ARCHITECTURE AND OPERATING SYSTEMS

  1. Consider two CPU scheduling algorithms for a single CPU: Round-Robin scheduling and (nonpreemptive) Shortest-Job-First scheduling. Assume that there is no time lost during context switching. Given five processes with arrival times and expected CPU time:
    Process Arrival time Expected CPU time
    P1 0 14
    P2 2 12
    P3 4 8
    P4 5 4
    P5 17 7

    a) Assuming Shortest-Job-First scheduling, draw a Gantt chart to show when each process executes on the CPU. Also compute the average waiting time.
    b) Repeat for Round-Robin scheduling, assuming a time quantum of size = 6.

  2. Consider a system with three resources (A, B, C) in quantity (9, 5, 7). The Banker's Algorithm is being used to allocate resources and it has the following current SAFE state:
    Process Allocation    Max    Need    Available
    A B C A B C A B C A B C
    P0 2 0 0 3 2 1 1 2 1 2 3 4
    P1 0 1 0 5 5 4 5 4 4
    P2 3 0 2 7 0 2 4 0 0
    P3 2 1 1 2 2 1 0 1 0
    Assume the following requests for (A, B, C) arrive in the order below. In each case, answer YES (request granted) or NO (request denied). Assume that the problem is CUMULATIVE. For example, your answer for request 3 assumes that requests 1 and 2 have been processed (with results of granted or denied). At no time during this problem are any resources actually returned by any of the processes. Show your work to support your YES/NO answers.
    Request# Process Request Banker Response (YES/NO)
    A B C
    1 P1 2 3 4 YES/NO
    2 P0 1 2 1 YES/NO
    3 P3 1 1 1 YES/NO
    4 P3 0 1 0 YES/NO
  3. Design a fully simplified 3-bit mod 5 down counter with T flip-flops. The circuit decrements with each clock pulse, going through the sequence 0, 4, 3, 2, 1, 0, 4, 3, 2, 1, 0, 4, ... . Show the circuit diagram.

  4. Design an Arithmetic Logic Unit (ALU) to perform the following operations:
    S1 S0 Function
    0 0 X Plus Y
    0 1 X
    1 0 Not(Y)
    1 1 X Xor Y
    Assume that X and Y are 4-bit numbers. Draw the logic diagram of the final circuit. You should first design a 1-bit version. You may use block diagrams for full adders, half adders, multiplexers, and decoders. Use the resulting 1-bit diagram for your final result.

PROGRAMMING LANGUAGES AND COMPILER DESIGN

  1. The concept of "Abstraction" is important in software development, and modern programming languages provide features to support it.

    a) Define "Abstraction" in this context.
    b) Give 3 examples of features in modern programming languages which provide support for abstraction. Explain briefly how these features support abstraction.

  2. Give a simple grammar (in BNF) which is SLR(1) but not LL(1), and prove the correctness of your claims. Use no more than 3 nonterminals and 6 production rules in your grammar.

  3. Language definitions sometimes say that certain constructions are simply "undefined," since they are left as "implementation dependent," and this may make their meaning ambiguous. (The example cited in the C++ standard is "i = a[i++];".) The following constructions may have ambiguous meanings, depending either on implementation dependencies or on design choices made in language definition. In each case, identify what the ambiguity is, what language feature it involves, and why. Assume the declarations "int i, x, a[256]".

    a) i = a[i++];

    b) int f(int); /* A function with global side effects */
         . . .
         if ( f(x) > 0 || f(x) < 3 ) { /* do something */ }

    c) int f(int); /* A function with global side effects */
         . . .
         x = 3*f(x) + 7*f(x);

    d) void g(inout int, inout int); /* A function with value-result parameter passing */
         . . .
         g(x, x);

  4. The following program is written in a Ada/Pascal like language. 
    program P
    var x,y,z: integer;         /* Static (global)   variables */
    var ip: pointer to integer;
    const c = 2, d= 3;          /* Static (global) constants */
    procedure Proc(
            in i: integer;      /* Value or input parameter */
            out j: integer;     /* Result or output parameter */
            inout k: integer)   /* In/Out or value-result parameter */
        var x,y: integer;       /* Local variables */
        x := i + 1;             /* Use of input parameter and local variable */
        j := x + 1;             /* Use of output parameter */
        k := k + 1;             /* Use of value-result parameter */
        z := i + j + k + x;     /* Use of non-local variable */
        y := 2 * z;
        ip := new integer;      /* Use of non-local pointer variable */
        ip^ := z + 1;           /* Represents a dereferenced pointer, similar to *ip in C */
                                /* <<<<< HERE >>>>> */
    end Proc;
    procedure main()
        x := 1;                 /* Use of global variables */
        z := 1; 
        Proc(x,y,z);            /* Subprogram invocation */
        print(x,y,z,ip^);
    end main;
end P;

    a) Show (1) how memory is allocated and (2) the contents of memory at the point labeled <<<< HERE >>>>>.
    b) What is the output of the program?