Data Structures and Algorithms
Tutorial Problems: Part 2

Tutorial 2

  • Asymptotic behaviour
    1. Threshhold values
    2. For what values of n is

      4 x 106 n2 > 10 x 2n ?

    3. Algorithm comparison
    4. 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 n2 iterations to solve a problem of size n.

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


    Tutorial 3

  • 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:

    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; } }

    Key terms

    deque
    A double-ended queue - one to which items can be added at both the head and the tail and one from which items can be extracted from the head or the tail.

    Continue on to Tutorials: Part 3 Back to the Table of Contents
    © John Morris, 1998