Fall 2004

Consider a single-linked list of character elements, for example:

 c -> a -> f -> r -> q

Write a non-recursive function, in the language of your choice, which reverses all of the pointers, for example:

 c <- a <- f <- r <- q

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);

The nodes in the list just have a single pointer, not two pointers. 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.

Consider a MinHeap (Priority Queue) of integer keys. Assume these integer keys are inserted into the heap in this order: 10, 4, 12, 8, 3, 9, 15, 7.

a) [5 points] Draw the heap after the insertion of the keys.

b) [15 points] Code the "insert" function in the language of your choice. Assume, as usual, that the MinHeap is implemented as an array. Declare your data structure and the prototype of your function.

Let G be a connected weighted graph with n vertices and m edges. The edges are stored using the adjacency matrix implementation. The vertices are v₀, ..., v_n-1

a) Write a routine to construct the shortest path from vertex u to vertex w. Code in the language of your choice. For fundamental local data structures (stack, queues, priority queues, etc.), you may call functions for the basic operations without writing the actual code.

b) State in BIG-THETA (Q) terms the worst case runtime of your routine. Your answer should be the best description as a function of n and m. Note the fundamental local data structure implementations if they affect the result. Justify your answer.

Describe as precisely as possible the containment and equality relationships among the following complexity classes. Clearly distinguish between proved relationships and generally assumed relationships, and briefly justify your reasoning.

PSPACE, Turing-Recognizable (or Turing-Acceptable), NP, Decidable, NPSPACE, P, NP-Complete

Consider this solution to the Readers-Writer problem.

Readers:                                       Writer:
  while (true) {                                 while (true) {
    wait(A);                                       wait(B);
    readcount++;
    if (readcount==1) wait(B);
    signal(A);
    /* reader reads from the file */               /* writer writes to the file */
    wait(A);
    readcount--;
    if (readcount==0) signal(B);                             
    signal(A);                                     signal(B);
  } // end while                                   } // end while

The problem is to consider the effects of the initialization of the semaphores A and B 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 only one process makes progress.

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

Consider a virtual memory with demand paging.

a) Assume that it takes 1 time unit to execute an instruction and that every k^th instruction is a reference to a page other than the current page. Also assume that every m^th reference to a page other than the current page causes a page fault. The service time for a page fault is an ADDITIONAL n time units to the usual 1 time unit.

What is the effective (average) instruction execution time as a function of k, m, and n? HINT: Draw a time chart and consider how many instructions are executed in one page fault episode. What is the elapsed time of this episode? Verify your function by considering limits on k, m, n.

b) In this part, no page faults occur. Consider a system where the page table is stored in cache memory. The hit ratio is 80%, meaning that the page table entry will be found in the cache 80% of the time; otherwise, the page table entry will be found in physical memory as usual. Checking an entry in the cache takes 20 nanoseconds and the normal physical memory access time is 100 nanoseconds.

What is the effective (average) access time to a page in physical memory?

a) Show the gate design for a D latch.

b) Design a rising edge-triggered D flip-flop.

Design a simplified sequential circuit to implement the following sequence of hexadecimal states: 0, 7, A, 5, C, F, 2, 9, 1, 0. Use D flip-flops

a) Describe, briefly, the principal parts (stages) of a compiler including their actions and relationships between stages.

b) Demonstrate your understanding of the stages you propose by describing what specific actions you would expect each stage to take during the compilation of the two statements below, which have been extracted from a larger C program.

           
     int Aleph[100], n;
     . . .
     Aleph[n] = 1 + Aleph[n + 1] * Aleph[n + 1] + zed;
     . . .

Determine if the following grammars are LL(1), SLR(1), both, or neither. Justify your answers. [Some authors simply use "SLR" for "SLR(1)".]

a) Z -> A
A -> aAa | BbB
B -> bB | a

b) Z -> AaAb | BbBa
A -> e
B -> e

Consider the following correct C++ program:

     class funny { 
       private: int x;
       public:
         funny(int k = 0) {x=k;}
         int give_value(void) {return x;}
     };
     void print_it(funny x, funny *y) {
       cout << x.give_value() << " " << y -> give_value() << endl;
     }
     int main(int argc, char *argv[]) {
       funny a(50);
       funny *b = new funny(100);
       // Two function calls. How are they implemented?
       print_it(a, b);
       print_it(*b, &a);
     return 0;
     }

Explain, precisely, what actions need to take place to implement the two function calls to "print_it" in the given C++ program.

High level languages (e.g., FORTRAN, Algol, BASIC, Lisp, Pascal, C, C+, APL, PL/1, ML, Java, etc.) use various memory management strategies for dealing with code and data. Explain what these strategies are and how they are used by several different high level languages. (The languages that you choose for illustration should use different strategies.)