pbaumgarten.com

Unit 5: Abstract data structures (HL) with Unit D4: Advanced OOP (HL)

As there is considerable overlap between Unit 5 and Unit D4, it makes more practical sense to teach the two units together. In actual fact, both can also be subdivided into two subparts that also work well together, firstly recursion, and secondly abstract data structures themselves, so I have actually organised these two units into those two sub-parts. I have indicated the syllabus alignment for each part.


Part 1: Abstract data structures

The key content of this section is

Syllabus alignment


Programming conventions

Before we proceed any further, as our programs are now becoming more complex, it is time to address the issue of programming conventions. (D.4.15)

Meaningful identifiers, proper indentation and adequate comments all improve the readability of code and thus save money, time and effort in programming teams. Some general conventions that need to be observed in order to improve readability are

When naming your identifiers, Java conventions are as follows

Please follow these conventions! Not only will it make life a lot easier for you to maintain your own code, but it will make it a lot easier on anyone marking your code too!


Dynamic v static data structures

An abstract data structure:

Dynamic Static
Memory is allocated as the program runs. Memory size is fixed, and is set at time of compilation.
Disadvantage: Possibility of overflow or underflow during runtime if allocations are exceeded. Advantage: As memory size is fixed, there will be no problems with memory allocations during run time.
Advantage: Makes most efficient use of memory, uses only what is required. Disadvantage: Potentially wasted memory space.
Disadvantage: Harder to program. Programmer must keep track of memory sizes and locations. Advantage: Easier to program. Only need to check you don’t exceed your preset limit.

Two dimensional arrays

As the name suggests, a two dimensional array will allow us to model data that is two dimensional in nature. Programming uses for this include spreadsheets, databases and 2D games.

As with one dimensional arrays, we have a couple of methods of declaring static 2D arrays with Java.

Method 1

int numbers[][]= { {25,10, 5}, 	//row 0
                   { 4, 6,13},	//row 1
                   {45,90,78}	//row 2
                 };
for (int row=0; row<numbers.length; row++) {
    for (int col=0; col<numbers[row].length; col++) {
        int val = numbers[row][col];
        System.out.println("numbers["+row+"]["+col+"] = "+val);
    }
}

Method 2

int numbers[][] = new int[3][3];

numbers[0][0] = 25;
numbers[0][1] = 10;
numbers[0][2] = 5;
numbers[1][0] = 4;
numbers[1][1] = 6;
numbers[1][2] = 13;
numbers[2][0] = 45;
numbers[2][1] = 90;
numbers[2][2] = 78;

// using the other for-loop method
for (int[] row : numbers) {
    for (int cell : row) {
        System.out.println( cell );
    }
}

Exercise 1

A teacher has decided to use a 2D array to store the marks for one of their classes. The grade book takes the following form:

Marksbook Test 1 Test 2 Test 3 Test 4 Test 5
Student A 67% 50% 93% 83% 43%
Student B 70% 52% 96% 85% 48%
Student C 90% 81% 100% 93% 68%
Student D 55% 32% 71% 72% 58%
Student E 60% 47% 65% 74% 61%

Convert the above into a suitable 2D array then write code to determine the following

  1. Determine the overall average mark
  2. Determine the average mark for each individual student
  3. Determine the average mark for each individual assessment
  4. Given the following grade cut offs, determine the grade for each student: A = 85%, B = 70%, C = 55%, D = 40%, F < 40%

Solution


Exercises: 2D array patterns

Given the following template code, can you solve the algorithm that creates each given pattern?

package com.pbaumgarten.teachingnotes;

public class TwoDimensionArrayReview {

    public static void printArray(int[][] arr) {
        for (int i=0; i<arr.length; i++) {
            for (int j=0; j<arr[i].length; j++) {
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] arr = new int[9][9];

        System.out.println("Example");
        arr = example(arr);
        printArray(arr);

        System.out.println("Q1");
        arr = question1(arr);
        printArray(arr);
    }

Example problem: Create the following number sequence

    public static int[][] example(int[][] arr) {
        int counter = 1;
        for (int i=0; i<arr.length; i++) {
            for (int j=0; j<arr[i].length; j++) {
                arr[i][j] = counter++;
            }
        }
        return (arr);
    }

Questions 1 through 12

(note: for problem 12 you can assume the array length will always be an odd integer)

    public static int[][] question1(int[][] arr) {
        for (int i=0; i<arr.length; i++) {
            for (int j=0; j<arr[i].length; j++) {
                arr[i][j] = j;
            }
        }
        return (arr);
    }
}

Question 13

(Questions adapted for Java by P Baumgarten. Original C++ version by Brian Choi 2011)


Dynamic collections

Before proceeding, we need to revisit the idea of a collection from Unit 4.


Linked lists

View the linked list animation @ https://visualgo.net/en/list

Visually comparing a linked list to an array

Common operations for a linked list include

Example usage of a linked list as follows

LinkedList list = new LinkedList()
list.add( 12 )
list.add( 99 )
list.add( 37 )
print(list.getValue())
print(list.getNext().getValue())
print(list.getNext().getNext().getValue())
Iterator = list
while ( iterator.hasNext ) {
   print( iterator.getValue() )
   iterator = iterator.getNext()
}

Doubly linked list

Circularly linked list

Inserting a node

Deleting a node

Sketching operations

Students should be able to sketch diagrams illustrating: adding a data item to linked list, deleting specified data item, modifying the data held in the linked list, searching for a given data item.

Given the following linkedlist

Pseudocode operations

Java coding a LinkedList

Using Java’s built in LinkedList

package com.pbaumgarten.teachingnotes;

import java.util.LinkedList;

public class LinkedListDemo {
   public static void main(String args[]) {
      LinkedList ll = new LinkedList();
      
      // add elements to the linked list
      ll.add("F");
      ll.add("B");
      ll.add("D");
      ll.add("E");
      ll.add("C");
      ll.addLast("Z");
      ll.addFirst("A");
      ll.add(1, "A2");
      System.out.println("Original contents of ll: " + ll);

      // remove elements from the linked list
      ll.remove("F");
      ll.remove(2);
      System.out.println("Contents of ll after deletion: " + ll);
      
      // remove first and last elements
      ll.removeFirst();
      ll.removeLast();
      System.out.println("ll after deleting first and last: " + ll);

      // get and set a value
      String val = (String)ll.get(2);
      ll.set(2, val + " Changed");
      System.out.println("ll after change: " + ll);
   }
}

Problems

  1. Write a count() function that counts and returns the number of times a given int occurs in a list.
  2. Write a GetNth() function that takes a linked list and an integer index and returns the data value stored in the node at that index position.
  3. A more difficult problem is to write a function InsertNth() which can insert a new node at any index within a list.
  4. Write a SortedInsert() function which given a list that is sorted in increasing order, and a single node, inserts the node into the correct sorted position in the list.
  5. Write an InsertSort() function which given a list, rearranges its nodes so they are sorted in increasing order. It should use SortedInsert().
  6. Write a RemoveDuplicates() function which takes a list sorted in increasing order and deletes any duplicate nodes from the list. To make it more challenging, code it so the list is only be traversed once.

(when you are ready, ask me for the solutions file, “cs-unit-5-linkedlist-problems-with-solutions.pdf”)


Stacks

A LIFO (last in, first out) data structure with the following methods:

View the stack animation @ https://visualgo.net/en/list

Make your own Stack data structure with Java

package com.pbaumgarten.teachingnotes;

import java.util.LinkedList;

public class MyStack {
    private LinkedList list;

    public Stack() {
        list = new LinkedList();
    }

    public boolean isEmpty() {
        return (list.size() == 0);
    }

    public void push(Object item) {
        list.add(item);
    }

    public Object pop() {
        Object item = list.get(list.size());
        list.remove(list.size());
        return item;
    }
}

Java actually includes a built in Stack class you can use

package com.pbaumgarten.teachingnotes;

import java.util.Stack;

public class StackUsageExample {
    public static void main(String[] args) {
        Stack<Integer> s = new Stack<Integer>();
        System.out.println( s );
        s.push(new Integer(42));
        s.push(new Integer(66));
        s.push(new Integer(99));
        System.out.println( s );
        while ( ! s.isEmpty() ) {
            int val = s.pop();
            System.out.println("Item removed: "+val);
            System.out.println( s );
        }
    }
}

Queues

A queue is a FIFO (first in, first out) data structure:

View the queue animation @ https://visualgo.net/en/list

package com.pbaumgarten.teachingnotes; 

import java.util.LinkedList;

public class MyQueue {
    // Use the Java built in LinkedList to manage our queue
    private LinkedList list;

    public MyQueue() {
        list = new LinkedList();
    }

    public boolean isEmpty() {
        return (list.size() == 0);
    }

    public void enqueue(Object item) {
        list.add(item);
    }

    public Object dequeue() {
        Object item = list.get(0);
        list.remove(0);
        return item;
    }

    public Object peek() {
        return list.get(0);
    }

    public static void main(String[] args) {
        MyQueue q = new MyQueue();
        System.out.println( "Queue:" );        
        q.enqueue("person 1");
        q.enqueue("person 2");
        q.enqueue("person 3");
        q.enqueue("person 4");
        q.dequeue();
        q.enqueue("person 5");
        q.enqueue("person 6");
        while (! q.isEmpty() ){
            int i = 1;
            System.out.println( "Now calling customer " + q.dequeue() );
        }
    }
}

Stacks & Queues: Static implementation

If we wanted to implement our own stack or queue, in addition to using a dynamic structure such as the LinkedList like we used above, we can make one quite easily using an object that used a static array as an instance variable.

What would be required of our object to be able to implement this?

Task: Build the classes StaticStack and StaticQueue that use a statically declared array as the data store. Use an array size of 100 items. Your class should only publically expose the methods of a queue or stack, with the addition of an isFull() method.

(Yes, Philipp, it must be a static array. The course demands it you show you can do this)


Stacks & Queues: Exercises

  1. For any given string, reverse its contents by way of using a stack.
  1. For any given string, use a stack to determine if every opening parenthesis is matched with a closing parenthesis.

  2. What does the following code fragment print when n is 50? Give a high-level description of what the code fragment does when presented with a positive integer n.

Stack stack = new Stack();
while (n > 0) {
    stack.push(n % 2);
    n /= 2;
}
while (!stack.isEmpty()) {
     print(stack.pop());
}
println();
  1. Consider the following pseudo code. Assume that IntQueue is an integer queue. What does the function fun do?
void fun(int n) {
    IntQueue q = new IntQueue();
    q.enqueue(0);
    q.enqueue(1);
    for (int i = 0; i < n; i++) {
        int a = q.dequeue();
        int b = q.dequeue();
        q.enqueue(b);
        q.enqueue(a + b);
        print(a);
    }
}
  1. more challenging For any given string, use a stack to create a PEMDAS compliant calculator. For example, ( 2 + ( ( 3 + 4 ) * ( 5 * 6 ) ) )

Trees

Trees are a commonly used data structure in computing. One place you will have used them all the time without even a moments thought is when navigating the folder/file structure of your computer.

This course only requires you to be familiar with the binary tree, a tree that has no more than two branches coming off each node.

Some terminology

There are three ways of traversing a tree, starting from the root:

A simple way of visually remembering these traversal methods is to imagine flags as follows

Example

So, with the original tree shown at the start (root node = 2), what would the pre-order, in-order and post-order traversal be?

Coding a Binary Tree

There is not a pre-built Binary Tree class for us to use in Java. Can you write your own so the following main() will work?

public static void main(String[] args) {
    MyBinaryTree bt = new MyBinaryTree();
    bt.insert( 13 );
    bt.insert( 4 );
    bt.insert( 2 );
    bt.insert( 15 );
    bt.insert( 100 );
    bt.insert( 1000 );
    bt.insert( 222 );
    bt.insert( 23 );
    bt.insert( 7 );
    bt.insert( 8 );
    System.out.println("Node count");
    System.out.println( bt.countNodes() );
    System.out.println("Pre order traversal");
    bt.preorder();
    System.out.println("In order traversal");
    bt.inorder();
    System.out.println("Post order traversal");
    bt.postorder();
}

Hint: Take a look my LinkedList class, you will need to create your own Node subclass like I did there.

Binary Tree exercises

  1. Program the function inorder() to output the data contained in a binary tree using inorder tree traversal
  2. Program the function preorder() to output the data contained in a binary tree using preorder tree traversal
  3. Program the function postorder() to output the data contained in a binary tree using postorder tree traversal
  4. Program the function lookup(), which given a value, will search the binary tree to determine if the value is present in the tree, and returns true or false accordingly (you may assume the contents of the tree are sorted in order)
  5. Program the function insert(), which given a value, will insert a new node with the given value at the correct location within the tree, and shuffles the rest of the tree accordingly as required.
  6. Program the function maxdepth() which returns the longest path from the root node to the furthest leaf node.
  7. Program the function isInOrder() which searches the contents of the tree and returns true if the contents are sorted for in order traversal.

(when you are ready, ask me for the solutions file, “cs-unit-5-binarytree-problems-with-solutions.pdf”)


Extension: Hash tables/maps

The commonly used data structure known as hash tables, key-value pairs, or a dictionary is quite a fascinating yet complex structure. This video does a great job of clearly explaining the underlying concepts of how it works.

Can you make your own simple hash table class?


Exercises & Review


Part 1: Recursion

Syllabus alignment

Thinking recursively

To understand recursion, one must first understand recursion.

Definition:

We use it to create looping behaviour without actually using a loop construct in our code.

Any recursive algorithm could be solved iteratively, and vice-versa. Here is a simple algorithm shown with both it’s iterative and recursive versions.

// Iteration
function goHome()
    while (I am not home) then
        face the direction of home
        take one step
    end while
end function

// Recursion
function goHome()
    if (I am not home) then
        face the direction of home
        take one step
        goHome()
    end if
end function

Requirements for recursion

Every recursive algorithm has

In a recursive algorithm, the computer “remembers” every previous state of the problem. This information is “held” by the computer on the “activation stack” (i.e., inside each function’s memory workspace). Every function has its own workspace for every call of the function.

Recursive functionality really suits some problems – makes it a lot simpler / more elegant than the iterative equivalent. However, stack space is limited and the computer will only be able to recurse so many times before it runs out of memory.

  1. Identify the base case – and write the procedure for it
  2. Identify the recurring case – and write the procedure for it
  3. Identify the test for determining whether the present case is base or recurring
  4. Code it
  5. Trace test
  6. Test on a small scale
  7. Test on a larger scale

Recursive situations

Here are a few of the more commonly known recursive situations.

Factorial number sequence

Fractal tree

MathFractalTree

The recursive steps for a fractal tree could be described as

Without worrying about the programming, focusing just on the pseudo code logic, how would you create a fractal drawing algorithm? Manually test it for for depths 1, 2 and 3.

Image credit: https://rosettacode.org/mw/images/8/8a/MathFractalTree.png

Snowflake

The humble snowflake, is very similar to fractals and is recursive in nature.

Here is a Python implementation of a snowflake drawing algorithm

from turtle import *

def drawFlake(length, depth):
    hideturtle()
    if depth > 0:
        for i in range(6):
            forward(length)
            drawFlake(length // 3, depth - 1)
            backward(length)
            left(60)

if __name__ == "__main__":
    drawFlake(200,4)

See the live demo at https://repl.it/@PaulBaumgarten/SnowflakeRecursion

Others

What other other real-world recursive situations can you identifty?

Construct & trace recursive algorithms

Exercise: Factorials

We looked at the factorial algorithm earlier. Did you obtain this solution? Have a go at implementing it if you haven’t done so yet.

public static long factorial(int n) { 
    if (n == 1) {                   // test
       return 1;                    // base case
    } else {
       return n * factorial(n-1);   // recursive call
    }
} 

Exercise: Fibonacci

The fibonacci sequence is 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Determine the pseudo code, do a trace table test of your algorithm, then code it in Java.

Solution

Exercise: Fractal tree

Can you implement the fractal tree algorithm you came up with earlier?

Exercise: Snowflake

Can you implement the snowflake algorithm you came up with earlier?

Here is a good stack overflow discussion of creating a snowflake algorithm with Python.

Exercise: Tower of hanoi

The Tower of Hanoi is a straight forward game that requires recursion to solve. In this puzzle, we have three pegs and several disks, initially stacked from largest to smallest on the left peg. The rules are simple:

An example of how it works with 3 disks.

You don’t need to create a graphical output, a printed set of instructions is fine. Eg:

(note: you’d very quickly find solutions online… while I can’t stop you, I emphasis this would deprive yourself of the learning experience the problem solving brings)

By now we should all know and love the binary search algorithm, but did you realise there is a recursive version of the algorithm?

Can you create a recursive version of the algorithm? (no cheating with google)

Here is an array of 50 sorted names you can use for your binary search.

String[] names = {"Aaliyah","Abigail","Adalyn","Aiden","Alexander","Amelia","Aria","Aubrey","Ava","Avery","Benjamin","Caden","Caleb","Carter","Charlotte","Chloe","Daniel","Elijah","Emily","Emma","Ethan","Evelyn","Grayson","Harper","Isabella","Jack","Jackson","Jacob","James","Jayden","Kaylee","Layla","Liam","Lily","Logan","Lucas","Luke","Madelyn","Madison","Mason","Mia","Michael","Noah","Oliver","Olivia","Riley","Ryan","Sophia","William","Zoe"};

Exercises & review

Textbooks

Programming exercises for recursion: