Spring 2006

Consider an application that requires a task, myTask, to perform the following sequence of operations on a single data structure:
i) find the minimum value in the data structure
ii) delete this value from the data structure
iii) insert some other value into the data structure

Consider each of the following data structures as a candidate for the above task. For each data structure, state the overall BIG-OH for myTask in terms of the average case and the worst case as a function of n, where n is the number of elements in the data structure. Do NOT guess: +2 points for correct answer, -2 points for incorrect answer, 0 points for no answer.

myTask: Big-Oh

Average Case Worst Case

Unsorted Linked List

Sorted Linked List

Minheap (Priority Queue)

Binary Search Tree

Hash Table
Consider these two binary trees, where the first tree consists of identical integer elements:
```
 
        5                  2
      /   \              /   \
     5     5            5     5
    / \   /            / \
   5   5 5            8   2 
  /       \            \
 5         5            5
  \       /
    5    5 
```
The problem is: Given a binary tree and an integer key x, return TRUE (1) if every node in the tree contains element x. Otherwise, return FALSE (0). If the tree is empty, return TRUE.

In the example, if the integer key is 5, the function would return TRUE for the first tree, but FALSE for the second tree.

Code in the language of your choice and include the declaration of your data structure. Do not call any other functions.

The protoype in C is: int allSame(tree_ptr p, int x);
Given a singly-linked list of character elements, write a function which removes every other node from the list. For example,

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

would result in:

 
 c -> f -> q

That is, the function should remove these nodes: 2nd, 4th, 6th, etc. If the list has fewer than two nodes, then nothing is removed. Code in the language of your choice and include the declaration of your data structure. Do not worry about actually "freeing" the nodes back to memory. Note that this problem can be solved with just a few lines of code, without any temporary variables.

Consider disk scheduling algorithms. Assume that the disk has blocks 0..99 and that the head is currently processing block 66. Select three (3) of the standard algorithms, but do not include FCFS. For each algorithm, briefly describe with words and/or diagrams the general behavior of the algorithm. Now, assume the arrival of the following block requests while block 66 is still being processed: 54, 95, 25, 87. For each of the three algorithms, construct the sequence in which the blocks are processed. If necessary, assume that the head is moving upwards towards larger block numbers.
Consider two processes interacting with semaphores:
```
 
Semaphore A = 0;  // initialization of semaphore
Semaphore B = 0;
Semaphore C = 0;
 
P0:                       P1:
  while (true) {            while (true) {
    wait(C);                  signal(C);
    signal(B);                wait(B);
    wait(A);                  signal(A);
  }                         }
```
In each of the following two parts below, draw a Gantt chart illustrating the execution of the processes. Assume initially that P0 is in front of P1 in the ready queue. A short-hand notation: P1:W(B) indicates that process P1 executes wait(B) without blocking, and P1:W*(B) indicates that P1 blocks on B. Each Gantt chart should consist of 11 semaphore calls.

a) Use First-Come First-Serve (FCFS) scheduling.

0 1 2 3 4 5 6 7 8 9 10

b) Use Round Robin (RR) scheduling where one time quantum is represented by one box in the Gantt chart, that is, a semaphore call uses exactly one time quantum.

0 1 2 3 4 5 6 7 8 9 10
Design a fully simplified 3-bit mod 7 down counter. The circuit decrements with each clock pulse, going through the sequence 0, 6, 5, 4, 3, 2, 1, 0, 6, 5, ... , repeatedly. Note the kind of flip-flops that are used. Show the circuit diagram.

Consider the following C-like program where a function is allowed to be passed as a parameter:
```
 
int i = 2;
int f(int j){
  return(i*j);
}
int g( int h(int) ){
  int i = 3;
  return h(i);
}
main(){
  int j = g(f);
  print(j);
}
```
a) Assuming static scoping, show the runtime stack when at its highest point. Include all important information. Also, what is the output of the program?

b) Assuming dynamic scoping, show the output of the program (do NOT show the runtime stack).
Code a solution to the Minimum Spanning Tree (MST) problem. Given an weighted graph G = (V, E) implemented as adjacency lists, use either Prim's or Kruskal's algorithm. For fundamental local data structures (stack, queues, priority queues, etc.), you may call functions for the basic operations without writing the actual code. Code in the language of your choice (or a reasonable pseudocode).
You may choose 3A or 3B, but not both.
A) Convert the following NFA into an equivalent DFA.
B) Let CLIQUE = {G, k : G is an undirected graph with a k-clique}. Show that 3SAT £_p CLIQUE.

	myTask: Big-Oh
	Average Case	Worst Case
Unsorted Linked List
Sorted Linked List
Minheap (Priority Queue)
Binary Search Tree
Hash Table