CS COMPREHENSIVE EXAM SOLUTIONS

SPRING 2010

DATA STRUCTURES

Scan forwards and do head inserts, OR scan backwards and do tail inserts

 
typedef struct single_node *single_ptr;
struct single_node {
    int element;
    single_ptr next;
};
typedef struct double_node *double_ptr;
struct double_node {
    int element;
    double_ptr next, prev;
};
single_ptr forwards(double_ptr dhead, double_ptr dtail) {
    single_ptr shead = NULL;
    single_ptr p;
    while (dhead != NULL) {
        p = (single_ptr) malloc(sizeof(struct single_node));
        p->element = dhead->element;
        p->next = shead;
        shead = p;
        dhead = dhead->next;
    }
    return shead;
}

 
RECURSIVE:
int alternates(tree_ptr p, int didLeft) {
  if (p == NULL) return 1;
  if (didLeft) {
    if (p->left) return 0;
    return alternates(p->right, 0);
  } else {
    if (p->right) return 0;
    return alternates(p->left, 1);
  }
}
 
ITERATIVE:
int alternates(tree_ptr p, int didLeft) {
  int didLeft = 0;
  while (p != NULL) {
    if (didLeft)
      if (p->left)
        return 0;
      else
        p = p->right;
    else
      if (p->right)
        return 0;
      else
        p = p->left;
    didLeft = !didLeft;
  }
  return 1;  // made it thru the gauntlet
}

SYSTEMS

a) P0:W*(A), P1: W(B), P1:S(A), P1:W*(B), P0:S(B), P0:S(B), P0:W*(A), P1:W(B), P1:S(A), P1:W*(B), P0:S(B)
b) P0:W*(A), P1:W(B), P1:S(A), P0:S(B), P1:W(B), P0:S(B), P1:W(B), P0:W*(A), P1:S(A), P0:S(B), P1:W(B)

THEORY

 
book -> title contents chapters
contents -> content contents | epsilon
content -> title number
chapters -> chapter chapters | epsilon
chapter -> title pages
pages -> page number pages | epsilon

 
a) M(n) = 2M(n-1) + 1; M(1)=1
 
b) M(n) = 2M(n-1) + 1
        = 2(2M(n-2) + 1) + 1
        .
        .
        = (2^(n-1))M(n-(n-1)) + (2^(n-2)) + (2^(n-3)) + ... + 1
        = 2^n - 1

 
Just the "lowest" possible language (language "below" are FALSE, languages "above" are TRUE):
 
i)   CF
ii)  REG
iii) CF
iv)  TUR
v)   CF
vi)  NOT TUR
vii) TUR

FALL 2009

SYSTEMS

 
Semaphore NotEmpty = 0;
Semaphore NotFull  = M;
MAKER/PRODUCER:                SHIPPER/CONSUMER:
  while (true) {                 while (true) {
    wait(NotFull);                 wait(NotEmpty);
    put(cake);                     get(cake);
    signal(NotEmpty);              signal(NotFull);
  }                              }

1. NO, exceeds NEED
2. YES, SAFE
3. NO, resources not available
4. NO, UNSAFE

SPRING 2009

SYSTEMS

 
a) 0, 1, 2, 3, 1, 2
b) 0, 1, 2, 1, 2, 3
c) 0, 1, 2, 1, 2, 0, 3

THEORY

FALL 2008

DATA STRUCTURES

 
typedef struct tree_node *tree_ptr;
struct tree_node {
  int element;
  tree_ptr left;
  tree_ptr right;
};
a)
int count_only(tree_ptr p) {
int count = 0;
  if (!p)
    return 0;
  if ((p->left) && (!p->right))
                ||
     ((!p->left)&& (p->right))
    count++
  return count + count_only(p->left) + count_only(p->right);
}

THEORY

n², nlog n, n²log n, n², log n

SPRING 2008

DATA STRUCTURES

 
typedef struct tree_node *tree_ptr;
struct tree_node {
  int element;
  tree_ptr left;
  tree_ptr right;
};
tree_ptr delete_min(tree_ptr root) {
tree_ptr ptr;
  if (root == NULL)                 // empty => nothing to delete
    return NULL;
  if (root->left == NULL)           // no left => root is min, delete by making right the new root
    return root->right;
  ptr = root;
  while (ptr->left->left != NULL)   // stop above the leftmost leaf
    ptr = ptr->left;
  ptr->left = NULL;                 // cut off this leaf, it is the min
  return root;                      // root stays the same
}

 
#define N 100
struct list_node *node_ptr;
struct list_node {
  node_ptr next;
  int key;
};
node_ptr hashtable[N];
 
a)
node_ptr find(int key) {
int i = hash(key);
node_ptr p = hashtable[i];
  while (p != NULL)
    if (p->key == key)
      return p;
    else
      p = p->next;
  return p;
}
b)
void display() {
  int i;
  node_ptr p;
  for (i=0; i < N; i++)  {
    p = hashtable[i];
    while (p != NULL) {
      printf("%d\n",p->key);
      p = p->next;
    }
  }
}

SYSTEMS

a) MUTUAL EXCLUSION can be violated: two workers can test p==-1, both set to their own pid, and both enter. However, once selected, a process never gives up the setting. If one process tests/set p, then it will always remain the selected progcess (unless stepped on). UNFAIR. Even if several processes test/set, the last setting will take place forever, so N-1 workers will starve. After p is set, it is impossible to violate MUTUAL EXCUSION again.

b) MUTUAL EXCLUSION is still a problem, but can be violated over and over. With the reset p=-1, there is the opportunity for multiple workers to test/set the flag. It is still UNFAIR, but not in the sense that the selected worker naturally stays selected. With the reset, it is still UNFAIR in that the selected process may continue on the CPU, and retake the flag again.

FALL 2007

DATA STRUCTURES

unsorted array: n, n
sorted array: n, n
minheap (priority queue): n, n
binary search tree: log n, n
hash table: 1, n (but will accept 1)

THEORY

SPRING 2007

SYSTEMS

 
b)
Semaphore A = 0;  // P0 blocks right-away on A
Semaphore B = 1;  // P1 blocks on B on the second attempt
Semaphore C = 2;  // P1 blocks on C on the third attempt
 
// CODE CAN BE READ DIRECTLY FROM THE GANTT CHART:
// EASY IF STUDENT UNDERSTANDS HOW THE DYNAMIC GANTT CHART
// RELATES TO THE STATIC CODE
 
a)
P0:                       P1:
  while (true) {            while (true) {
    wait(A);                  wait(B);
    signal(B);                wait(C);
    wait(C);                  signal(A);
  }                         }

FIFO, LRU, LFU, MFU.

THEORY

SPRING 2006

DATA STRUCTURES

1.  
   1. Formal Parameter - Formal Parameter: x and y both denote the address of i
   2. Global Variable - Formal Parameter: i and x denote the same address
   3. Pointer - Pointer: y and p end up pointing to the same address
   4. Array Element - Array Element: a[i] and a[*x] are the same cell

2.  
   int allSame(tree_ptr p, int x) {
     if (p == NULL)
       return 1;
     if (p->element != x)
       return 0;
     return allSame(p->left,x) && allSame(p->right,x);
   }
   

    
   void rm_every_other(node_ptr p) {
     while (p && p->next) {
       p->next = p->next->next;
       p = p->next;
     }
   }
   

   SYSTEMS

   Consider: 54, 95, 25, 87 (moving up)

    
   SSTF  : 66, 54, 25, 87, 95             = 111
   SCAN  : 66, 87, 95, (99), 54, 25       = 107
   C-SCAN: 66, 87, 95, (99), (0), 25, 54  = 186
   

   THEORY

   FALL 2004

   DS/ALG/COMPLEX

   a)

    
         3
        / \
       4   9
      / \ / \
     7  8 12 15
    /
   10
   

   b)

    
   #define MAX_ELEMENTS 100
   struct heap_struct {
   int max_heap_size;
   int size;
   int elements[MAX_ELEMENTS];
   };
    
   typedef struct heap_struct *PRIORITY_QUEUE;
    
   void insert(int x, PRIORITY_QUEUE H) {
   int i;
     if (H->size < H->max_heap_size) {
       i = ++H->size;
       while (H->elements[i/2] > x) {
         H->elements[i] = H-> elements[i/2];
         i /= 2;
       }
       H->elements[i] = x;
     }
   }
   

   SPRING 2004

   DS/ALG/COMPLEX

   a) Recursive Binary Search

    
   int BinSearch(int x, int a[], int left, int right) {
     int middle = (right+left)/2;
     if (left > right)
       return -1;
     else
       if (key == a[middle])
           return(middle);
       else
          if (key < p->key[middle])
           return(BinSearch(x,a,left,middle-1));
         else
           return(BinSearch(x,xmiddle+1,right));
       }
   }
   

   b) 1/2..1/2 (k terms) n = 1; 1/2^k * n = 1; n = 2^k; k = O(log n)

   PLC/COMP

   a) a: value, b: ref, c: ptr, d: array which is ref, e: value

   4 7 3 3

   SPRING 2003

   DS/ALG/COMPLEX

    
   node_ptr push(node_ptr L, int element) {
   node_ptr p;
      p = (node_ptr)malloc(sizeof(struct node));
      p->element = element;
      p->next = L;
      return p;
   }
   node_ptr reverse_intersection(node_ptr L1, node_ptr L2) {
   node_ptr L3 = NULL;
     while (L1 && L2)
       if (L1->element == L2->element) {
         L3 = push(L3,L1->element);      // or just insert in-line
         L1 = L1->next;
         L2 = L2->next;
       } else
       if (L1->element < L2->element)
         L1 = L1->next;
       else
         L2 = L2->next;
     return L3;
   }
   

   OS/ARCH

   Placing the 0's in a 4-var K-map yields

   F' = c'd + ad + a'b'cd'

   F = (c+d') (a' + d') (a + b + c' + d)

   PLC/COMP

   a) Aliasing: two (or more) expressions denote the same memory address.

   b) There are four types of aliasing, all of which are illustrated in the code above.

   c) 2 + 2 + 9 + 9 + 2 + 2 = 26

   FALL 2002

   DS/ALG/COMPLEX

   If both sub-trees are even, then result is odd.
   If both sub-trees are odd, then result is odd.
   If one sub-tree is even and one is odd, then result is even.
   This can be simpified to this:

    
   int even(tree_ptr p) {
     int l, r;
     if (p == NULL)
       return 1;
     else {
       l = even(p->left);
       r = even(p->right);
       return (l && !r) || (!l && r);    // or some other variation of this, perhaps if-stmts, maybe XOR
     }
   }
   

   FALL 2000

   DS/ALG/COMPLEX

   a)

    
   void postorder(tree_ptr p) {
     if (p != NULL) {
       child = p->first_child;
       while (child != NULL) {
         postorder(child);
         child = child->next_sibling;
       }
       printf("%d ",p->element);
     }
   }
   

   b) E, F, B, G, C, D, A

FALL 1999

OS/ARCH