Abstract Data Types and Algorithms

During this class I learnt about stacks, queues, lists, trees, and graphs. Also covered was an introduction to the analysis of algorithms using Big-O notation.

Assignment #2

The second assignment of this course was the first to contain software development work. In particular this assignment required the implementation of both a Queue and Stack Abstract Data Type.

The queue was made to model a stock portfolio, with each item in the collection being a stock transaction. After the sale of an arbitrary amount of stocks the net profit is returned, and the queue updated.

The stack was called a ‘Red-Blue Stack’, and its purpose was to hold two different types of an item. Red colored items and blue colored items. The stack ADT methods had to be available to both types of items also. Essentially this let the user employ both popBlue and popRed methods at any point during the stack operation. This functionality was accomplished by having a linked list data structure to support the individual ordering of the red items and the blue items, along with another linked list for the stack itself.

Assignment #3

For this assignment we had to implement Binary Tree, Heap, and Binary Search Tree Abstract Data Types. Unlike the previous assignment, the Abstract Data Types implemented in this case were quite straightforward, since there wasn’t any specialization needed for modeling specific scenarios.

The first data structure implemented was the binary tree, which is a tree such that every node contains at most two children. This is defined recursively, and additionally tells us that a balanced binary tree will have a height of O(logn), where n is the number of elements in the tree.

The second data structure was the min-heap. This ADT satisfies a rule such that each child node C of a parent node P has a key which is of higher value. Written mathematically it can be expressed as key(C) > key(P). The heap also satisfies the binary tree property, so each node may have at most two child nodes.

Lastly, the third data structure implemented was a binary search tree. Similar to the heap, it also places a constraint on the nodes in regard to the key values. Simply put, an inOrder traversal on the tree must return a node list such that the key values are of ascending value. Formally, this is defined such that for every node, the left subtree contains nodes with only a lesser key value, and the right subtree contains nodes with only a higher key value. As one last point, each key value in this ADT must be unique (due to the constraints placed on the value).

Assignment #4

In this assignment we created two different hash tables. One dealt with collisions by creating a linked list containing the collided elements while the other calculated a secondary offset to place the element at. As one can assume there are pros and cons to each method.

First off though I’d like to explain the Hash Table ADT. A hash table is similar to an array in that it is a fixed size container, though this is where the similarities end. To store elements in the hash table there are two functions used. The first is the actual hashing function, which uses any appropriate (unique) properties from the element to produce a location for it to be stored at. For example, in this assignment the index produced by the hashing function was the sum of the ASCII values of the string object to be stored. The second function used is a compression function, which simply takes the output from the hashing function and transforms it to a valid index. In the assignment this was done by taking the modulus of the output value with respect to the maximum index size of the hash table.

A collision in a hash table occurs when the hashing function (along with compression function) produce the same index for more than one element. Clearly two elements cannot be stored in one place, so this problem must be dealt with. The first hash table implementation uses a linked list for collisions as mentioned above. Here the upside is that an unlimited amount of objects can be stored since the linked list structure used is not bounded. The trade-off however is that when retrieving an object this method also adds an extra O(m) possible steps to go through the m objects in the list after arriving at the correct index. Adversely the secondary offset method only adds at worst O(n) steps since our container has a bounded size of n elements. These collisions can be for the most part avoided by proper creation of the hash function and a realistic storage capacity for the hash table.