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.
The key content of this section is
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!
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. |
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 );
}
}
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
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)
Before proceeding, we need to revisit the idea of a collection from Unit 4.
addItem()
, getNext()
, resetNext()
, hasNext()
, isEmpty()
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
addHead( value )
- adds at the front of the listaddTail( value )
- adds at the end of the listadd( value )
- same as addTail()insert( value )
- in order insertiondelete( value )
list()
getNext()
- advance pointer to next item in the listresetNext()
- returns to the beginning of the listhasNext()
- returns true/false if there is a next itemisEmpty()
isFull()
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
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
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);
}
}
(when you are ready, ask me for the solutions file, “cs-unit-5-linkedlist-problems-with-solutions.pdf”)
A LIFO (last in, first out) data structure with the following methods:
push()
to add to the stackpop()
to remove from the stackisEmpty()
to query stack statusView 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 );
}
}
}
A queue is a FIFO (first in, first out) data structure:
enqueue()
to add an item to the back of the queue.dequeue()
to remove an item from the front of the queue.isEmpty()
to query the queue status.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() );
}
}
}
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)
For any given string, use a stack to determine if every opening parenthesis is matched with a closing parenthesis.
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();
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);
}
}
( 2 + ( ( 3 + 4 ) * ( 5 * 6 ) ) )
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?
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.
(when you are ready, ask me for the solutions file, “cs-unit-5-binarytree-problems-with-solutions.pdf”)
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?
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
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.
Here are a few of the more commonly known recursive situations.
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
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
What other other real-world recursive situations can you identifty?
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
}
}
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.
Can you implement the fractal tree algorithm you came up with earlier?
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.
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"};
Textbooks
Programming exercises for recursion: