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 void every_other( DList& l ){
Node* p1 = l.head, p2, p3;
Node* 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 ClassList;
// ... initialization of ClassList ...
if( ! ClassList.empty() ){
list::iterator itr = ClassList.begin();
list::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 );
}
---------------------------------------------------------------------