- You are here:
- Home »
- Topic 5 Abstract Data

Quick Navigation

A procedure or function that can call itself until a base case is reached.

Work thru Khan Academy as far as properties of a recursive algorithm click here go as far as properties of recursive algorithms.

We can use a loop to work out a factorial of any number see php example below.

Create an equivalent recursive function to work out the factorial of any number.

Upload your solution to your BLOG and Google Classroom. Also upload answers/views to the questions recursion about stacks and loops

Write a recursive function that computes the sum of all numbers from 1 to n, where n is given as parameter.

A two-dimensional array is simply an array in which each element contains another array. The following illustration shows this.

*Figure 2: Illustration of two-dimensional array (By Derrick Coetzee, via Wikimedia Commons)*

ables have many applications and so do two-dimensional arrays. For instance, tables can be used to store the distances between cities.

*Figure 3: Distances between cities in New Zealand (Champion Freight)*

This could be used for calculating the total distance of a given path or to find the shortest route for a given tour.

Two-dimensional arrays are also often used for games, e.g. battleship or chess. Programming such a game is a good exercise to practise algorithmic thinking and the use of arrays!

**Further reading:** WikiBooks provides an excellent explanation of arrays and has good practice exercises for algorithms using two-dimensional arrays here.

What are the characteristics of a multi dimensional array. Give an example of data that could be stored in a multi dimensional array

Write an algorithm in pseudo code to print out contents of a 2 dimensional array - using a loop

Cartoon video The Difference Between Stacks and Queues please click here

A stack is an abstract data type in which accesses are made at only one end. You can insert an item as the first one and you can remove the first one. This ADT models many things in real life. Accountants call it LIFO, which stands for Last In First Out. The plate holder in a cafeteria has this property. We can only take the top plate. When we do, the one below rises to the top so the next person can take one. Canned goods on a grocer’s shelf exhibit this property. When we take the first can in a row, we are taking the last can put in that row. Another way of stating the accessing behavior of a stack is that the item removed is the item that has been in the stack the shortest time. Viewing a stack from this perspective is more abstract. The insert has no constraints, the entire LIFO behavior is specified in the removal operation.

The mental image of the cafeteria plates has left an imprint on the traditional names used for the insert and delete operations. The insert is called Push and the delete is called Pop. We Push and item onto the stack and Pop an item off the stack. A stack does not have the property of length, so there is no operation that returns the number of items on the stack. We do need operations that determine whether a stack is Empty because trying to Pop an item when the stack is empty is an error.

If items 90, 65, 80, 95, 75, 60 are entered into a linked implementation of an un ordered list with each item going at the front of the list, the list would look like below . The first item is accessed and put onto the stack, the second item is accessed and put on the stack, and so on. When the last item has been added to the stack, the contents of the stack look like this: Top of stack Bottom of the stack 60 75 95 80 65 90

Now we Pop off one item at a time and print it. The first item printed is 60, the next item printed is 75, and so on. The original list has now been printed in reverse order using the stack. Any sequence of items put on the stack comes off in reverse order.

When we call a function memory is allocated from the stack.

The text segment contains the actual 0’s and 1’s of your program. The

initialized data and unitialized data segments contain global variables.

The stack is used to store local variables and function parameters.

RAM

If you call a recursive function without a base case what will happen?

Stack is used for static memory allocation and Heap for dynamic memory allocation, both stored in the computer's RAM .

What is the stack? It's a special region of your computer's memory that stores temporary variables created by each function (including the `main()`

function). The stack is a "LIFO" (last in, first out) data structure, that is managed and optimized by the CPU quite closely. Every time a function declares a new variable, it is "pushed" onto the stack. Then every time a function exits, **all** of the variables pushed onto the stack by that function, are freed (that is to say, they are deleted). Once a stack variable is freed, that region of memory becomes available for other stack variables.

The advantage of using the stack to store variables, is that memory is managed for you. You don't have to allocate memory by hand, or free it once you don't need it any more. What's more, because the CPU organizes stack memory so efficiently, reading from and writing to stack variables is very fast.

A key to understanding the stack is the notion that **when a function exits**, all of its variables are popped off of the stack (and hence lost forever). Thus stack variables are **local** in nature. This is related to a concept we saw earlier known as **variable scope**, or local vs global variables. A common bug in C programming is attempting to access a variable that was created on the stack inside some function, from a place in your program outside of that function (i.e. after that function has exited).

Another feature of the stack to keep in mind, is that there is a limit (varies with OS) on the size of variables that can be store on the stack. This is not the case for variables allocated on the **heap**.

To summarize the stack:

- the stack grows and shrinks as functions push and pop local variables
- there is no need to manage the memory yourself, variables are allocated and freed automatically
- the stack has size limits
- stack variables only exist while the function that created them, is running

The heap is a region of your computer's memory that is not managed automatically for you, and is not as tightly managed by the CPU. It is a more free-floating region of memory (and is larger). To allocate memory on the heap, you must use `malloc()`

or `calloc()`

, which are built-in C functions. Once you have allocated memory on the heap, you are responsible for using `free()`

to deallocate that memory once you don't need it any more. If you fail to do this, your program will have what is known as a **memory leak**. That is, memory on the heap will still be set aside (and won't be available to other processes). As we will see in the debugging section, there is a tool called `valgrind`

that can help you detect memory leaks.

Unlike the stack, the heap does not have size restrictions on variable size (apart from the obvious physical limitations of your computer). Heap memory is slightly slower to be read from and written to, because one has to use **pointers** to access memory on the heap. We will talk about pointers shortly.

Unlike the stack, variables created on the heap are accessible by any function, anywhere in your program. Heap variables are essentially global in scope.

- very fast access
- don't have to explicitly de-allocate variables
- space is managed efficiently by CPU, memory will not become fragmented
- local variables only
- limit on stack size (OS-dependent)
- variables cannot be resized

- variables can be accessed globally
- no limit on memory size
- (relatively) slower access
- no guaranteed efficient use of space, memory may become fragmented over time as blocks of memory are allocated, then freed
- you must manage memory (you're in charge of allocating and freeing variables)
- variables can be resized using
`realloc()`

They are both stored in the computer’s RAM (Random Access Memory).

Data on the stack is ** automatically** deallocated when variables go out of scope. However, in languages like C and C++, data stored on the heap has to be deleted

Once a function call runs to completion, any data on the stack created specifically for that function call will automatically be deleted. Any data on the heap will remain there until it’s manually deleted by the programmer (example: by using free() function built in c).

The stack is much faster than the heap. This is because of the way that memory is allocated on the stack. Allocating memory in this is as simple as moving the stack pointer up.

The stack is set to a fixed size, and can not grow past it’s fixed size (although some languages have extensions that do allow this). So, if there is **not** enough room on the stack to handle the memory being assigned to it, a ** stack overflow** occurs. This often happens when a lot of nested functions are being called, or if there is an infinite recursive call.

If the current size of the heap is too small to accommodate new memory, then more memory can be added to the heap by the operating system. This is one of the big differences between the heap and the stack.

**Access methods: • push • pop • isEmpty**

class stringList

{

protected $stack;

protected $limit;

public function __construct($limit = 10) {

// initialize the stack

$this->stack = array();

// stack can only contain this many items

$this->limit = $limit;

}

public function push($item) {

// trap for stack overflow

if (count($this->stack) < $this->limit) {

// prepend item to the start of the array

array_unshift($this->stack, $item);

} else {

throw new RunTimeException('Stack is full!');

}

}

public function pop() {

if ($this->isEmpty()) {

// trap for stack underflow

throw new RunTimeException('Stack is empty!');

} else {

// pop item from the start of the array

return array_shift($this->stack);

}

}

public function isEmpty() {

return empty($this->stack);

}

}

$openBrackets = array('(,[');

$closeBrackets = array('],)');

If string is free of syntax errors echo Good Syntax else Invalid Syntax

If ($a>$b) or ($b<10 {

If ($a>$b) or ($b<10 {

First in, first out (FIFO)

Examples of the applications of queues may include print queues and the computer modelling of physical queues (eg supermarket checkouts).

Both linear and circular implementation of a queue are required.

Access methods: • enqueue • dequeue • isEmpty.

A **dynamic data structure** is a data structure that is flexible in growing or shrinking in size. This can make memory allocation more efficient, by only using as much as is necessary, while also allowing the programmer to design more flexible algorithms, where the size of a data structure is not known before runtime.

**Nodes and pointers** are two concepts commonly used for dynamic data structures. The idea is that each data element is allocated a *node *for storing information. In addition, each node has a *pointer* which points to the memory space in which the next node (data element) is stored.

...

Arrays VS

Linked Lists

Fast Access

Linear / Sequential Access

Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at contiguous location; the elements are linked using pointers.

**Circular linked list** is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list.

A **D**oubly **L**inked **L**ist (DLL) contains an extra pointer, typically called *previous pointer*, together with next pointer and data which are there in singly linked list.

Trees are hierarchical data structures that are best explained with a sketch

Binary trees have the characteristic of being ordered. The **left-child**(e.g. 3) must come before the parent node (i.e. 8) and the **right-child**must come after the parent node (i.e. 10). For this reason each node in a binary tree can have a maximum of two child nodes only.

**Non-binary trees** on the other hand do not follow these rules and could be used for example to represent animal species trees. A non-binary, or multifurcating, tree is a tree in which at least one node has more than two children.

.

Binary Tree is a special data structure used for data storage purposes. A binary tree has a special condition that each node can have a maximum of two children.

A binary tree has the benefits of both an ordered array and a linked list as search is as quick as in a sorted array and insertion or deletion operation are as fast as in linked list.

Binary Search tree exhibits a special behavior. A node's left child must have a value less than its parent's value and the node's right child must have a value greater than its parent value.

**Recursive Definition of Binary Search Tree **for every node on the trees the left child smaller than the right child ? Is the right child bigger than the left child ? This is a recursive definition.

In a tree data structure, each child from a node forms a subtree recursively. Every child node will form a subtree on its parent node.

A walk in which each parent node is traversed before its children.

*Figure 4: Preorder Tree Traversal*

- Display the data part of the root (or current node).
- Traverse the left subtree by recursively calling the pre-order function.
- Traverse the right subtree by recursively calling the pre-order function.

Result: F, B, A, D, C, E, G, I, H.

A walk in which a node’s left subtree, then the node itself, and finally its right subtree are traversed.

*Figure 2: Inorder Tree Traversal*

- Traverse the left subtree by recursively calling the in-order function.
- Display the data part of the root (or current node).
- Traverse the right subtree by recursively calling the in-order function.

Result: A, B, C, D, E, F, G, H, I.

A walk in which the children are traversed before their respective parents are traversed.

*Figure 3: Postorder Tree Traversal*

- Traverse the left subtree by recursively calling the post-order function.
- Traverse the right subtree by recursively calling the post-order function.
- Display the data part of the root (or current node).

Result: A, C, E, D, B, H, I, G, F.

Excellent resource for tree traversal exercises please click here

Beginning with an empty Binary search Tree, what tree is formed when you insert the following values in order

- 1W,T,N,J,E,BA
- 2W,T,N,A,B,E,J
- 3A,B,W,J,N,T,E

The insertion procedure is quite similar to searching. We start at the root and recursively go down the tree searching for a location in a BST to insert a new node. If the element to be inserted is already in the tree, we are done (we do not insert duplicates). The new node will always replace a NULL reference.

Searching in a BST always starts at the root. We compare a data stored at the root with the key we are searching for (let us call it as `toSearch`

). If the node does not contain the key we proceed either to the left or right child depending upon comparison. If the result of comparison is negative we go to the left child, otherwise - to the right child. The recursive structure of a BST yields a recursive algorithm.

Searching in a BST has O(h) worst-case runtime complexity, where h is the height of the tree. Since s binary search tree with n nodes has a minimum of O(log n) levels, it takes at least O(log n) comparisons to find a particular node. Unfortunately, a binary serch tree can degenerate to a linked list, reducing the search time to O(n).

Deletion is somewhat more tricky than insertion. There are several cases to consider. A node to be deleted (let us call it as `toDelete`

)

If `toDelete`

is not in the tree, there is nothing to delete. If `toDelete`

node has only one child the procedure of deletion is identical to deleting a node from a linked list - we just bypass that node being deleted

Deletion of an internal node with two children is less straightforward. If we delete such a node, we split a tree into two sub trees.

Deletion strategy is the following: replace the node being deleted with the largest node in the left sub tree and then delete that largest node. By symmetry, the node being deleted can be swapped with the smallest node is the right sub tree.

Draw Binary tree by inserting numbers left to right 11, 6, 8, 19, 4, 10, 5, 17, 43, 49, 31

A structure to store data or data collections in memory. The structure can grow or shrink dependent on storage requirements. Implemented using pointers to store memory locations in the heap part of memory.

In contrast a static data structure is normally fixed and declared at run time. This type of structure can not exceed the memory space allocated. This is useful when you know the size of data structure in advance for example representation of a board game. Whilst dynamic structure are more flexible they do come at extra costs of memory to store address pointers. Elements within a static data structure such as array can be access in constant time (O)1 items in dynamic stricture can only be accesses sequentially. (0)n

Consider the following sequence of stack operations

push(d),push(h),pop(),push(s),pop(),pop(),push(m)

A) Assume the stack is empty, what is the sequence of popped values?

What is the final state of the stack?

B) Suppose you were to replace the push and pop operations with enqueue and dequeue respectively. What would be the sequence of dequeued values, and what would be the final state of the queue? (Identify which end is the front of the queue.)