Midterm Examination Solutions. 
 
Problem 1: 
 
// There was _no_ problem with the code. Some of you 
// have succeeded in confusing me on this issue. 
// A funny thing for a teacher to admit - I trusted 
// your ability to find my mistakes more than my  
// own ability not to make them :-) .  
 
(a) the nodes "L" and "S" become unlinked from the list. 
    The new list reads  "DIT" 
 
(b) the intent of the code is to create a list made of 
    every other node of the original list. Nodes 2, 4, ... 
    etc. of the oroginal list get unlinked. 
 
(c) For this particular example tail doesn't need being adjusted, 
    because it still points at the last node in the new list. 
    However, adjustment will be necessary for any list with an 
    even number of nodes. 
 
    Hence the code should be changed to 
 
template<class T> void every_other( DList<T>& l ){ 
  Node<T>* p1 = l.head, p2, p3; 
 
  Node<T>* newtail = p1; 
 
  while( p1 != NULL ){ 
    p2 = p1->next;           // points to the next node after p1    
    if( p2 != NULL ){         
      p1->next = p2->next;   // now the current node points to  
      p3 = p1->next;         // the _second_ node ahead rather 
                             // than the next node 
      if( p3 ) p3->prev = p1;   // now the _second_ node down the line 
                                // thinks that the current (p1) is its 
                                // predecessor 
      newtail = p1; 
      p1 = p2->next;         // p1 is now == p3, jumped two nodes ahead 
    }                             
    else break; 
  } 
  // there are two ways to leave the loop -  
  // either the while condition became false, or break has fired;  
  // we need to handle both cases. But notice that the nodes 
  // pointed to by p1 will always remain in the list whatever happens, 
  // so the new tail is the _last_ node p1 points to before the loop 
  // ends (for either reason). 
  l.tail = newtail;  
} 
 
------------------------------------------------------------------------- 
 
Problem 2: 
 
(a)  Preorder :  1 2 4 7 9 3 5 8 6 
     Postorder:  9 7 4 2 8 5 6 3 1 
     Inorder  :  7 9 4 2 1 5 8 3 6 
     Breadth  :  1 2 3 4 5 6 7 8 9 
 
(b)  Recursive soluiton 1:  (more elegant) 
 
// argument p can be NULL, in which case return 0 
 
int CountChar( BTNode* p, char ch ){ 
  if( p == NULL ) return 0; 
  else if( p->data == ch )  
         return 1 + CountChar( p->lchild, ch )  
                  + CountChar( p->rchild, ch ); 
       else  
         return  CountChar( p->lchild, ch )  
                  + CountChar( p->rchild, ch );       
} 
 
     Recursive soluiton 2: 
 
// argument p is never NULL (else get a seg. fault) 
 
int CountChar( BTNode* p, char ch ){ 
  int count = 0; 
  if( p->data == ch ) count++; 
  if( p->lchild != NULL ) count += CountChar( p->lchild, ch ); 
  if( p->rchild != NULL ) count += CountChar( p->rchild, ch ); 
  return count; 
} 
 
---------------------------------------------------------------------- 
 
Problem 3: 
 
(a)  N + (N-1) + ... + 1 = N*(N+1)/2 , hence  O( N^2 ) 
 
(b)  On each iteration x is multiplied by 2 .  
     How many such multiplications are needed  
     for x to become >=  N*100000  ? 
 
     log( N*100000 ) = log(N) + log(100000) = log(N) + 5*log(10) 
 
     Hence  O( log N ) 
 
(c)  On each of the  N  iterations we have an O(N) loop and then 
     an O( N*log N ) function call. Hence 
 
     N * ( N + O(N*log N) ) = N^2 + O( N^2 * log N ) = 
   
     = O( N^2 * log N )   
 
     N^2 is dominated by N^2 * log N and can be removed from  
     Big-Oh. 
 
------------------------------------------------------------------              
 
Problem 4: 
 
list<Student> ClassList; 
 
// ... initialization of ClassList ... 
 
if( ! ClassList.empty() ){ 

  list<Student>::iterator itr = ClassList.begin(); 
  list<Student>::iterator end = ClassList.end(); 
  
  double average_grade = 0;  
  int    body_count    = 0; 
 
  while( itr != end ){ 
    average_grade += (*itr).grade; 
    body_count++; 
    ++itr; 
  } 
 
  average_grade /= body_count; 
 
  cout << "Average grade is " << average_grade << endl; 
 
  itr = ClassList.begin();  // another pass through the list 
  while( itr != end ){ 
    if( (*itr).grade > average_grade ) cout << (*itr).name << endl; 
    ++itr; 
  } 
}
 
//Notes:  ++ and * on  itr  can be combined by  (*itr++).grade   
//        -> is undefined in STL, so we use  *  to dereference itr . 
 
-------------------------------------------------------------------- 
 
Problem 5: 
 
(a) f(4) == 61,  9 calls including the initial one. 
 
Draw a tree of recursive calls: 
 
                                  f(4) 
                  __________________|___________________ 
                f(3)                                  f(2) 
         _________|__________                  _________|________                      
       f(2)                f(1)              f(1)              f(0) 
  _______|________    
f(1)           f(0)   
 
Also, f(0) == 1,  f(1) == 2,  f(2) == 3*1 + 2*2 == 7, 
                              f(3) == 3*2 + 2*7 == 20, 
                              f(4) == 3*7 + 2*20 == 61 .  
 
(b) one of the possible solutions is 
 
int GCD( int m, int n ){ 
  if( m == n ) return m; 
  if( m == 1 || n == 1 ) return 1; 
  if( m > n )  
    return GCD( m-n, n ); 
  else  // n > m         
    return GCD( n-m, m ); 
} 
    
Solutions with  "%"  instead of  "-"  need much fewer steps.  
Using the above property of GCD makes sense only if  
division is very expensive. 
 
If we allow  0  as input to GCD, we need fewer base cases: 
 
int GCD( int m, int n ){ 
  if( m == 0 ) return n; 
  if( n == 0 ) return m; 
  if( m > n )  
    return GCD( m-n, n ); 
  else  // n > m         
    return GCD( n-m, m ); 
} 
 
---------------------------------------------------------------------