COSC160 MIDTERM

9:30-10:45 AM                                                           Answer ALL                                                         (100 Points)

Name:   _____________________________________________________


1.  (5 points each) Give running time analysis of the following program segments in terms of n.  Accurate answer gets full points.

a.     for (i = n - log n ; i < n*n; i++)
	cout << i;

b.     for (i = 0; i <n *n*n; i++)
            cout <<i;
        for (j= 0; j < (n * n * logn) ; j++)
            cout <<j;

c.     sum = 0; 
        for (i = 1; sum < n log n; i++)
             sum = sum +4* i;

d.    for (i=1; i<n; i++)
             for (j = i; j < (3*i); j++)
                   cout << i+j;

e.    for (i=1; i<  n; i++)
             for (j= i ; j < n*n; j++)
                   for (k= 2; k < n; k++)
                          cout << i+j+k;

2.  (5 points each)
a.  Define Search Property 
b.  Define AVL Property

3.  (20 points)  How would you implement the following data structure?  Give enough details and pseudocode.
It is a stack with additional operator called Delete-AThird().
Suppose you have pushed 6 items, say 6,14,13,4,15,16 in that order.  Then Delete-AThird() would delete  ceiling(6/3) = 2nd item entered , which is 14, leaving the stack with 6,13,4,15,16.  If you invoke Delete-Athird() again,  it should delete ceiling(5/3) = 2nd item entered , which is 13, leaving the stack with 6,4,15,16.  You need to implement regular Push and Pop for the stack.

4. (20 points)  Explain how you did modulus in your Polynomial project.  Give enough details and pseudo code.

5. (20 points)

Assume the following struct to implement singly linked list:

   struct node {
       int item;
       node* next;
}
type node* nodeptr;
Write the C++ code for the following function:

int PrintInFirstNotSecond (nodeptr head1,head2)
// print elements in linked lists pointed to by head1 but not in the list pointed to by head2