Data Structures and Algorithms Tutorial Problems: Part 2

### Asymptotic behaviour

#### Threshhold values

For what values of n is

4 x 106 n2 > 10 x 2n ?

#### Algorithm comparison

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

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.

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.