# DP CompSci: Unit 5: Abstract data structures

# Teaching notes

Current notes (class of 2019)

- Unit 5 Teaching slides Part 1 (doesn't yet include LinkedLists and BinaryTrees)
- IB Pseudocode in detail

Archived notes (used with class of 2018)

Other teachers

# 2D arrays

**Problems**

(when you are ready, ask me for the solutiosn file, "cs-unit-5-array-problems-solutions.txt")

# Stacks & Queues

**Resources**

**Problems**

- For any given string, reverse its contents by way of using a stack.
- 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();
```

- 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);
}
}
```

**challenging**For any given string, use a stack to create a PEMDAS compliant calculator. For example,`( 2 + ( ( 3 + 4 ) * ( 5 * 6 ) ) )`

(cs-unit-5-stacks-queues-problems-with-solutions.pdf)

# Linked lists

**Resources**

**Problems**

- Write a count() function that counts and returns the number of times a given int occurs in a list.
- 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.
- A more difficult problem is to write a function InsertNth() which can insert a new node at any index within a list.
- 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.
- Write an InsertSort() function which given a list, rearranges its nodes so they are sorted in increasing order. It should use SortedInsert().
- 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")

# Binary trees

**Problems**

- Program the function inorder() to output the data contained in a binary tree using inorder tree traversal
- Program the function preorder() to output the data contained in a binary tree using preorder tree traversal
- Program the function postorder() to output the data contained in a binary tree using postorder tree traversal
- 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)
- 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.
- Program the function maxdepth() which returns the longest path from the root node to the furthest leaf node.
- 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")