Also available via http://www.kluge.net/~felicity/proj/cs2223-hw6.html

1) What value is returned by the following program when invoked by P(n)? You may assume that the input value n is a power of 2. Your answer should be expressed as a simple (not recursive) function of n.

int P(int n)
{
	int i,j,sum;
	if (n==1) return 1;
	sum=P(n/2);
	for (i=0;i<n;i++)
		for (j=0;j<n;j++) sum++;
	sum+=P(n/2);
	return sum;
}

Theo's Answer:

n	total	breakdown of total
1	1	1
2	6	1+4+1
4	28	1+4+1+16+1+4+1
8	120	1+4+1+16+1+4+1+64+1+4+1+16+1+4+1

I looked at the breakdown, and I noticed a pattern... The middle term is always n². There is also (when n>1) n number of +1 terms. For n=4, there is n²+n+n+n (4+4+4*1). For n=2, there's n²+n. n=8 provides n²+7*n (4+4+4+4=2n, 8*1=1n, 2*16=4n, sum=7n.)

From this, if another n is added, the sum is 2*n². Then just remove the n that was added for the actual sum. Therefore the answer is:

2n²-n

2) A divide-&-conquer implementation of a priority queue is a binary search tree (see, for example, Section 5.5 of our text). Test this data structure by writing and testing a program to do the following:

• choose several fairly large values of n
• for each value of n, construct a new priority queue
• insert n random values into the new priority queue
• determine the time to perform an insert into a priority queue with n elements (you can do this by performing m inserts where m<<n)
• determine the time to perform a delete-min (you can do this by performing m delete-mins, where m<<n)

Describe your implementation, and estimate the time to perform an insert and a delete-min (as a function of n) for your implementation. As a check that your program is performing correctly, you should note that constructing a new priority queue, then performing n inserts followed by n delete-mins returns the input in sorted order.

The best and average time to insert an element into a binary search tree with n-elements is O(lgn) because adding an element requires you to go completely through a branch of the tree with height lgn (for best case, approximately that (+/- a small constant for large n) for average case.) Worst case is in O(n) time due to the height of the branch the program goes through being n.

The implementation for insert is as follows:

• If root=NULL, insert the value as the root.
• Otherwise, compare each node to the value we're inserting. If the value is greater, traverse the right node, or if it's less, traverse the left node. If the value and the node value are equal, choose a free child (or if both are full/empty, pick a random one) to traverse. Continue until node=NULL, then add the value there.

For delete-min, the best and average cases are also O(lgn) because to get to the minimum value, only the left children must be traversed, and then the actual deletion is completed in constant time. Worst time is O(n).

The implementation for delete-min is:

• If root=NULL, return.
• Otherwise, traverse down through all left children from the root until there are no more left children. This is the minimum value. Delete this node. If the current node had a right child, assign the left child of the current node's root the right child of the current node.

Summary:

function	best/average cases	worst case
delete-min()	Theta(lgn)	Theta(n)
insert()	Theta(lgn)	Theta(n)

---

Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include <malloc.h>

typedef struct btn {
  int value;
  struct btn *root,*left,*right;
} BTNode;

BTNode *root=NULL;

void insert(int);
void insertnode(BTNode *,BTNode *,int,int);
void printtree(BTNode *);
void deltree(void);
void deletetree(BTNode *);
void delmin(void);
BTNode *delminimum(BTNode *);

void main()
{
  int n,loo,temp,max,m;
  int array[]={100000,200000,400000,800000,0};
  clock_t start,finish,end1;

  srand(time(NULL)^((getpid()<<15)+3*getpid()+1));

  m=array[0]/5;
  temp=0;
  while(array[temp]!=0)
    {
      n=array[temp];
      printf("Now doing %d ...\n",n);
      for(loo=0;loo<n;loo++)
          insert(rand());
      start=clock();
      for(loo=0;loo<m;loo++)
        insert(rand());
      end1=clock();
      for(loo=0;loo<n;loo++)
          delmin();
      finish=clock();
      deltree();
      temp++;
      printf("Insertion of %d took %.9f\n%d deletions took %.9f.\n\n",m,((double)(end1-start)/((double)(CLOCKS_PER_SEC))),m,((double)(finish-end1)/((double)(CLOCKS_PER_SEC))));
      sleep(1);
    }
  return;
}

void delmin(void)
{
  BTNode *temp;
  if (root==NULL)
    return;
  if (root->left==NULL)
    {
      temp=root->right;
      free(root);
      root=temp;
      if ( root!=NULL )
        root->root=NULL;
      return;
    }
  temp=root->left;
  while(temp!=NULL)
    temp=delminimum(temp);
  return;
}


BTNode *delminimum(BTNode *r)
{
  BTNode *rr;
  if (r->left==NULL)
    {
      if (r->right==NULL)
        {
          rr=r->root;
          free(r);
          rr->left=NULL;
          return NULL;
        }
      rr=r->root;
      rr->left=r->right;
      free(r);
      rr->left->root=rr;
      return NULL;
    }
  return r->left;
}

void printtree(BTNode *r)
{
  if (r==NULL)
    return;
  if ( r->left!=NULL )
    printtree(r->left);
  printf("%d\n",r->value);
  if ( r->right!=NULL )
    printtree(r->right);
  return;
}

void deltree(void)
{
  deletetree(root);
  root=NULL;
  return;
}

void deletetree(BTNode *r)
{
  if (r==NULL)
    return;
  if ( r->left!=NULL )
    deletetree(r->left);
  if ( r->right!=NULL )
    deletetree(r->right);
  free(r);
  return;
}

void insert(int x)
{
  if ( root==NULL )
    {
      root=(BTNode *)malloc(sizeof(BTNode));
      root->root=NULL;
      root->left=NULL;
      root->right=NULL;
      root->value=x;
      return;
    }
  insertnode(root,root->root,x,0);
  return;
}

void insertnode(BTNode *r, BTNode *rr, int x, int side)
{
  int temp;
  if ( r==NULL )
    {
      r=(BTNode *)malloc(sizeof(BTNode));
      if ( side )
        rr->right=r;
      else rr->left=r;
      r->left=NULL;
      r->right=NULL;
      r->value=x;
      r->root=rr;
      return;
    }

  if ( x<r->value )
    {
      insertnode(r->left,r,x,0);
      return;
    }
  else if (x>r->value)
    {
      insertnode(r->right,r,x,1);
      return;
    }

  /* x=r, now what? */

  if ( r->left!=NULL && r->right==NULL )
    {
      insertnode(r->right,r,x,1);
      return;
    }
  else if (r->left==NULL && r->right!=NULL )
    {
      insertnode(r->left,r,x,0);
      return;
    }

  /* either both right + left are defined, or none are ... */

  temp=rand()%2;
  insertnode(temp?r->right:r->left,r,x,temp);
  return;
}