Fall 1999

1. Code any O(n log n) sorting algorithm in the language of your choice. Be sure to state the name of your algorithm. Assume that the data are integer elements stored in an array.

2. Write a function which removes (and returns to memory) duplicate nodes in L where L is a singly-linked list, with integer elements sorted in ascending order. That is, keep the first occurrence of each element value and remove the following copies. Do not create a new list but, instead, re-link the original list. Performance is important. Declare your data structure and program in the language of your choice. You may assume that there is a dummy header node at the beginning of the list.

3. Construct an efficient algorithm that is given an undirected graph G and returns the number of connected components of G. Give a BIG-OH, i.e., Θ, analysis of your algorithm in terms of the number of vertices (n) and the number of edges (m).

4. a) Define these classes precisely: P, NP

PSPACE is defined (Garey&Johnson) as "the class of all languages recognizable by polynomial space bounded DTM programs that halt on all inputs." Here, DTM is an abbreviation for Deterministic Turing Machine.

b) Prove: P PSPACE

Consider SAT. Answer each of the following yes/no/unknown, with a brief but complete explanation or proof.

c) SAT is in P

d) SAT is in PSPACE

e) SAT is in NP

1. Consider the critical section problem.

a) Define and describe briefly:

b) Consider the code below, with four line numbers. State TRUE or FALSE, with a brief explanation, whether the code guarantees:

  Global Variable (shared by both processes):
    int lock;
  Processes:
      Philosopher0() {                                Philosopher1() {
        while (true) {                                  while (true) {
  Line#
  1:      while (lock == 1) { /* empty loop body */ }     while (lock == 1) { /* empty loop body */ }
  2:      lock = 1;                                       lock = 1;
  3:      << critical section >>                          << critical section >>
  4:      lock = 0;                                       lock = 0;
        }                                               }
      }                                               }
  Main Body:
    lock = 0;
    start asynchronously: Philosopher0();
    start asynchronously: Philosopher1();

2. Consider optimal algorithms, usually used as baselines for comparison purposes.

a) In one sentence, what is the optimal CPU scheduling algorithm?

b) In one sentence, what is the optimal page replacement algorithm?

Consider the Shortest-Seek-Time-First (SSTF) disk scheduling algorithm for processing blocks/sectors.

c) Discuss any serious drawbacks to SSTF.

d) Show that SSTF is not optimal. Prove your answer using exactly a sequence of 5 block/sector numbers of your choice.

3. Design a fully simplified 3-bit mod 7 counter with JK flip-flops. The circuit increments with each clock pulse, going through the sequence 0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,... . Show the circuit diagram.

4. Draw the circuit diagram for a 4-bit shifter as a combinational circuit. (Note that there are no flip-flops in this problem.) The inputs are A3 A2 A1 A0. The outputs are B3 B2 B1 B0 with the direction of the shift determined by a control input C. If C=1, B3 B2 B1 B0 is a logical left shift of the input. If C = 0, it is a logical right shift.

1. The below skeleton is in a C-like language. It includes one goto statement. The target of the goto might be any one of the labeled statements, s1...s5.

a) For each possible target, list BRIEFLY and CONCISELY

b) Choose a language of your choice and discuss which gotos would be legal.

  int g() {
    int x = 5;
    ...
    t1: s1;                 // first target
    ...
    return x;
  }

  int f() {
    int i,j; 
    for (i=1;i<20;i++)
    { ...
      t2: s2;              // second target
      ...
      goto < target ti >;  // goto statement
      ...
    }
    t3: s3;                // third target
    ...
    for (j=1;j<30;j++)
    { int k=3;
      ...
      t4: s4;              // fourth target
      ...
    }
    ...
    return (i+j);
  }

  int main () {
    int x=5, y=10;
    x=g();
    y=f();
    t5: return 0;         //fifth target
  }

2. An e-commerce company has a reply template that asks for a user's email address. You, as an expert in compiler design, are asked to use compiler techniques for language specification to help in validating input by specifying the set of legal strings.

For simplification, suppose that the only characters are:

And suppose that a legal email address must be a sequence of characters that:

a) Write a regular expression for legal email addresses.

b) Write a BNF grammar that generates legal email addresses.

3. The XXX Language Reference manual says that "the order of the evaluation of parameters is not specified."

a) Write a simple C function that gives different results depending on the order of evaluation of the parameters. Show the definition of your function and the call to the function. Use no more than two parameters and three lines of code in the function. Show the different outputs possible. Explain why they occur.

b) What effect does the non-specification of parameter evaluation order have on the writer of the compiler for XXX? on programmers who write XXX programs?

4. A compiler writer must choose a data structure to use for building the symbol table. Among the possible choices are:

a. linked list.

b. binary tree.

c. hash table.

In a few sentences for each, list the ADVANTAGES and DISADVANTAGES of each of these. Be sure to list why each is good (or bad) for the special requirements of a symbol table. You may assume a standard block-structured language such as C, Java, or Ada in your answer.