Short Questions

Longer Questions

1. Algorithm A requires 200 machine cycles for each iteration and requires nlogn iterations to solve a problem of size n.

   A simpler algorithm, B, requires 25 machine cycles for each iteration and requires n² iterations to solve a problem of size n.

   Under what conditions will you prefer algorithm A over algorithm B?

2. Simple ADT Design
   A double-ended queue or deque is one that has both LIFO and FIFO behaviour, ie you can add an item to the head or the tail of a list and extract an item from the head or the tail.

   Taking the following specification for the Collection class, modify it to handle a deque. Note:

   • There are quite a few ways that a software engineer could do this: see how many you can devise!
   • A software engineer would probably try to ensure that code using the original specification continued to function correctly.
   • C++ and Java programmers should be able to produce versions in those languages from this outline with little effort.

   Similarly, modify the implementation to handle a deque.

   /* Specification for Collection */
   
   typedef struct t_Collection *Collection;
   
   Collection ConsCollection( int max_items, int item_size );
   /* Construct a new Collection
      Pre-condition: max_items > 0
      Post-condition: returns a pointer to an empty Collection
   */
   
   void AddToCollection( Collection c, void *item );
   /* Add an item to a Collection
      Pre-condition: (c is a Collection created by a call to
                          ConsCollection) &&
                     (existing item count < max_items) &&
                     (item != NULL)
      Post-condition: item has been added to c
   */
   
   void DeleteFromCollection( Collection c, void *item );
   /* Delete an item from a Collection
      Pre-condition: (c is a Collection created by a call to
                        ConsCollection) &&
                     (existing item count >= 1) &&
            	  (item != NULL)
      Post-condition: item has been deleted from c
   */
   
   void *FindInCollection( Collection c, void *key );
   /* Find an item in a Collection
      Pre-condition: c is a Collection created by a call to
                        ConsCollection
                     key != NULL
      Post-condition: returns an item identified by key if one
                      exists, otherwise returns NULL
   */
   
   
   /* Linked list implementation of a collection */
   
   #include 	/* calloc */
   #include 	/* NULL */
   #include 	/* Needed for assertions */
   #include "collection.h"	/* import the specification */
   
   extern void *ItemKey( void * );
   
   struct t_node {
   	void *item;
   	struct t_node *next;
   	} node;
   
   struct t_collection {
   	int size;	/* Needed by FindInCollection */
   	struct t_node *node;
   	};
   
   collection ConsCollection(int max_items, int item_size )
   /* Construct a new collection
      Pre-condition: (max_items > 0) && (item_size > 0)
      Post-condition: returns a pointer to an empty
   collection
   */
   	{
   	collection c;
   	/* Although redundant, this assertion should be
   	   retained as it tests compliance with the formal
              specification */
    	assert( max_items > 0 );
    	assert( item_size > 0 );
   	c = (collection)calloc( 1, sizeof(struct t_collection) );
   	c->node = (struct t_node *)0;
   	c->size = item_size;
   	return c;
   	}
   
   void AddToCollection( collection c, void *item )
   /* Add an item to a collection
      Pre-condition: (c is a collection created by a call to 
                   ConsCollection) &&
                     (existing item count < max_items) &&
                     (item != NULL)
      Post-condition: item has been added to c
   */
   	{
   	struct t_node *new;
   	assert( c != NULL );
   	assert( item != NULL );
   	/* Allocate space for a node for the new item */
   	new = (struct t_node *)malloc(sizeof(struct t_node));
   	/* Attach the item to the node */
   	new->item = item;
   	/* Make the existing list `hang' from this one */
   	new->next = c->node;
   	/* The new item is the new head of the list */
   	c->node = new;
   	assert( FindInCollection( c, ItemKey( item ) ) != NULL );
   	}
   
   void DeleteFromCollection( collection c, void *item )
   /* Delete an item from a collection
      Pre-condition: (c is a collection created by a call to
                        ConsCollection) &&
                     (existing item count >= 1) &&
                     (item != NULL)
      Post-condition: item has been deleted from c
   */
   	{
   	struct t_node *node, *prev;
   	assert( c != NULL );
           /* The requirement that the collection has at least
              one item is expressed a little differently */
   	assert( c->node != NULL );
   	assert( item != NULL);
   	/* Select node at head of list */
   	prev = node = c->node;
   	/* Loop until we've reached the end of the list */
   	while( node != NULL )
   		{
   		if ( item == node->item )
   			{
   			/* Found the item to be deleted,
                              re-link the list around it */
   			if( node == c->node )
   				/* We're deleting the head */
   				c->node = node->next;
   			else
   				prev->next = node->next;
   			/* Free the node */
   			free( node );
   			break;
   			}
   		prev = node;
   		node = node->next;
   		}
   	}