Solutions to Mid-Term: Winter, 2003

Multiple Choice:

1: b
2: d
3: d
4: a
5: a

1(a):

node *Pop(node **head) {

   node* temp;

   if ((*head)==NULL) {
      fprintf(stderr,"Stack is empty\n");
      return NULL;
   } else {
      temp = *head;
      (*head) = (*head)->next;
      return temp;
   }
}


1(b):

node *CopyStack(node *head) {
   node* new_head;
   if (head==NULL)
      return NULL;
   } else {
      new_head = (node*)malloc(sizeof(node));
      new_head->data = head->data;
      new_head->next = CopyStack(head->next));
      return new_head;
   }
}

1(c):

void PrintStackBackwards(node *head) {
   if (head != NULL) {
      PrintStackBackwards(head->next);
      printf("%c",head->data);
   }
}
2:

Errors listed in order of appearance in the code. Note that some errors will cancel each other out (example: errors 1 & 3 below). 
1. Compile error: scanf is given an undeclared parameter (m).
2. Compile error: comment on malloc line not closed
3. Runtime error: malloc is given an unitialized parameter (n).
4. Runtime error: malloc is given absolute size for int (4) instead of sizeof(int)
5. Runtime error: In for loop: printing ip[n] which is undeclared memory 
6. Runtime error: In for loop: ip[n] set to zero, this is undeclared memory
7. Runtime error: printing **myp which is unallocated memory
8. Runtime error: return(1) sends signal to OS, probably want return(0)


3(a): O(n)
(note that O(n+m) is also an accepted solution)

Line 1 takes a constant amount of time and is executed once.

Lines 2&3 take a constant amount of time and are executed n times

Lines 4&5 take a constant amount of time and are executed 0 times if m >= n, or m times if m < n.  In the worst case, these lines are run n-1 times.

T = O(1 + n + n-1) = O(n)

3(b): 

Since there are no loops or outside function calls in this function, each call to stranger takes a constant amount of time to execute.

if n is even, the number of calls to stranger is equal to 2 * the number of calls on an odd number.

if n is odd, the number of calls to stranger is equal to n/2.

In the worst case the initial call to stranger is with an even n, and so T(n) = O(1 * (2*n/2)) = O(n)