Quick Navigation

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 

 

  • What is the base case in a recursive algorithm ?
  • Loop or Recursion: Which do you think is the most efficient and why. // time memory usage  can one be traded off the other / is using less memory, but slower better than using lots of memory and fast ? 
  • What are the dangers with recursion.
  • What are if any the advantage of recursion,  will this be true for all programming languages ?
  • Extension : What is tail recursion optimization ?

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.,

  • Periodic table 
  • Board Games
  • Spread Sheets
  • Lab book of multiple readings over several days

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.

Distance matrix exampleFigure 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

  • 60   top of stack
  • 75
  • 95
  • 80
  • 60
  • 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. 

  • space is carved out on the stack for the function's arguments and local variables
  • the function's arguments are copied into this new space
  • control jumps to the function
  • the function's code runs
  • the function's result is copied into a return value
  • the stack is rewound to its previous position
  • control jumps back to where the function was called
  • 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.

    stack vs heap (afterlecture.com)

    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.

    Using a stack to determine if a word is a palindrome

    Try it!

    function isPalindrome(word) {
    var s = new Stack();
    for (var i = 0; i < word.length; ++i) {
    s.push(word[i]);
    }
    var rword = "";
    while (s.length() > 0) {
    rword += s.pop();
    }
    if (word == rword) {
    return true;
    }
    else {
    return false;
    }
    }

    var word = "hello";
    if (isPalindrome(word)) {
    print(word + " is a palindrome.");
    }
    else {
    print(word + " is not a palindrome.");
    }
    word = "racecar"
    if (isPalindrome(word)) {
    print(word + " is a palindrome.");
    }
    else {
    print(word + " is not a palindrome.");
    }

    The output from this program is:

    hello is not a palindrome.
    racecar is a palindrome.

    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.

    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

    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

    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 Tree

    Important Terms

    • Path − Path refers to the sequence of nodes along the edges of a tree.
    • Root − The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node.
    • Parent − Any node except the root node has one edge upward to a node called parent.
    • Child − The node below a given node connected by its edge downward is called its child node.
    • Leaf − The node which does not have any child node is called the leaf node.
    • Subtree − Subtree represents the descendants of a node.
    • Visiting − Visiting refers to checking the value of a node when control is on the node.
    • Traversing − Traversing means passing through nodes in a specific order.
    • check
      Levels − Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.
    • check
      keys − Key represents a value of a node based on which a search operation is to be carried out for a node.

    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.

    Binary Search Tree

    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.

    Preorder Tree TraversalFigure 4: Preorder Tree Traversal

    1. Display the data part of the root (or current node).
    2. Traverse the left subtree by recursively calling the pre-order function.
    3. 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.

    Inorder Tree TraversalFigure 2: Inorder Tree Traversal

    1. Traverse the left subtree by recursively calling the in-order function.
    2. Display the data part of the root (or current node).
    3. 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.

    Postorder Tree TraversalFigure 3: Postorder Tree Traversal

    1. Traverse the left subtree by recursively calling the post-order function.
    2. Traverse the right subtree by recursively calling the post-order function.
    3. 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 

    • 1
      W,T,N,J,E,BA
    • 2
      W,T,N,A,B,E,J
    • 3
      A,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)

  • is not in a tree;
  • is a leaf;
  • has only one child;
  • has two children.
  • 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

    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.)