5.1.1 Identify a situation that requires the use of recursive thinking.
A procedure or function that can call itself until a base case is reached.
5.1.2 Identify recursive thinking in a specified problem solution.
Activity 1 Khan Academy
Work thru Khan Academy as far as properties of a recursive algorithm click here go as far as properties of recursive algorithms.
Activity A Discussion Loops Vs Recursion
Activity B Applying
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
Activity C Applying
Write a recursive function that computes the sum of all numbers from 1 to n, where n is given as parameter.
5.1.3 Trace a recursive algorithm to express a solution to a problem.
5.1.4 - 5.1.5 - 2 D arrays
Arrays that we have consider up to now are one dimensional arrays, a single line of elements. • Often data come naturally in the form of a table, e.g.,
Two-dimensional (2D) arrays are indexed by two subscripts, one for the row and one for the column.
5.1.5 Describe the characteristics of a two dimensional array
A two-dimensional array is simply an array in which each element contains another array. The following illustration shows this.
Find the average rating by the reviewer in row 2.
5.1.5 Construct algorithms using two dimensional arrays.
2 D Arrays Activity
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.
Activity A Questions Section : Please Upload Answers/Solution to your blog
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
5.1.6 Describe the characteristics and applications of a stack.
Cartoon video The Difference Between Stacks and Queues please click here
Stacks
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?
Difference between the Heap and Stack
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
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.
Stack vs Heap Pros and Cons
Stack
- 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
Heap
- 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()
FAQs
Where are the stack and heap stored?
They are both stored in the computer’s RAM (Random Access Memory).
How is memory deallocated on the stack and heap?
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 manually by the programmer using one of the built in keywords like free, delete, or delete[ ]
How long does memory on the stack last versus memory on the heap?
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).
Which is faster – the stack or the heap? And why?
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.
Can the Stack and Heap grow in size?
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.
5.1.7 Construct algorithms using the access methods of a stack.
Access methods: • push • pop • is Empty
Quick Introduction to the Constructor Function
function Person(first, last, age, eye) {
this.firstName = first;
this.lastName = last;
this.age = age;
this.eyeColor = eye;
}
function Person() is an object constructor function.
Objects of the same type are created by calling the constructor function with the new keyword:
Try It
<!DOCTYPE html>
<html>
<body>
<h2>JavaScript Object Constructors</h2>
<p id="demo"></p>
<script>
// Constructor function for Person objects
function Person(first, last, age, eye) {
this.firstName = first;
this.lastName = last;
this.age = age;
this.eyeColor = eye;
}
// Create two Person objects
var myFather = new Person("John", "Doe", 50, "blue");
var myMother = new Person("Sally", "Rally", 48, "green");
// Display age
document.getElementById("demo").innerHTML =
"My father is " + myFather.age + ". My mother is " + myMother.age + ".";
</script>
</body>
</html>
A Stack Implementation
To build a stack, we first need to decide on the underlying data structure we will use to store the stack elements. We will use an array in our implementation.
We begin our stack implementation by defining the constructor function for a Stack class:
function Stack() {
this.dataStore = [];
this.top = 0;
this.push = push;
this.pop = pop;
this.peek = peek;
this.clear = clear;
this.length = length;
}
function push(element) {
this.dataStore[this.top++] = element;
}
function peek() {
return this.dataStore[this.top-1];
}
function pop() {
return this.dataStore[--this.top];
}
function clear() {
this.top = 0;
}
function length() {
return this.top;
}
Palindromes
A palindrome is a word, phrase, or number that is spelled the same forward and backward. For example, “dad” is a palindrome; “racecar” is a palindrome; “A man, a plan, a canal: Panama” is a palindrome if you take out the spaces and ignore the punctuation; and 1,001 is a numeric palindrome.
We can use a stack to determine whether or not a given string is a palindrome. We take the original string and push each character onto a stack, moving from left to right. When the end of the string is reached, the stack contains the original string in reverse order, with the last letter at the top of the stack and the first letter at the bottom of the stack, as shown in Figure 4-2.
Try it!
functionisPalindrome(word){
vars=newStack();
for(vari=0;i<word.length;++i){
s.push(word[i]);
}
varrword="";
while(s.length()>0){
rword+=s.pop();
}
if(word==rword){
returntrue;
}
else{
returnfalse;
}}varword="hello";if(isPalindrome(word)){
(word+" is a palindrome.");}else{
(word+" is not a palindrome.");}word="racecar"if(isPalindrome(word)){
(word+" is a palindrome.");}else{
(word+" is not a palindrome.");}
The output from this program is:
helloisnotapalindrome.racecarisapalindrome.
5.1.8 Describe the characteristics and applications of a queue.
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.
5.1.9 Construct algorithms using the access methods of a queue.
Access methods: • enqueue • dequeue • isEmpty.
5.1.10 Explain the use of arrays as static stacks and queues.
5.1.11 Describe the features and characteristics of a dynamic data structure..
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 & pointers
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.
...
5.1.12 - 5.1.12 Linked Lists
5.1.12 Describe how linked lists operate logically.
5.1.13 Sketch linked lists (single, double and circular).
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 Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.
5.1.14 - 5.1.17 Trees Binary and Non Binary
Binary Trees Link to Slide Presentation Click here
5.1.14 Describe how trees operate logically (both binary and non-binary).
5.1.15 Define the terms: parent, left-child, right-child, sub tree, root and leaf.
Binary and non-binary trees
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-childmust 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.
Important Terms
Binary Search Tree Representation
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.
5.1.16 State the result of inorder, postorder and preorder tree traversal.
Preorder traversal
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.
Inorder traversal
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.
Postorder traversal
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.
Traversal Tree Interactive Exercises
Excellent resource for tree traversal exercises please click here
5.1.17 Sketch binary trees.
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
Insertion
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
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).
Insertion
Deletion
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
Draw Binary tree by inserting numbers left to right 11, 6, 8, 19, 4, 10, 5, 17, 43, 49, 31
Binary Tree Questions ( upload answers to your blog )
Complete and upload solution to your blog
5.1.18 - 5.1.20 Applications
5.1.18 Define the term dynamic data structure.
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.
5.1.19 Compare the use of static and dynamic data structures.
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
5.1.20 Suggest a suitable structure for a given situation.
Resources for Option 5
CS50 week 5 data Structures Video Harvard Click here
Question Section
Questions Traversal
Data Structures Question Section
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.)