Topic 5-2.pptx ib computer science topic 5

topic 5 ib css

1. Topic 5 Abstract Data Structures

2. Array An array is a list data structure in which elements are of the same type and stored in adjacent memory addresses . This fact leads to three key characteristics: Arrays support direct access because it is possible to mathematically calculate the address of a particular element, allowing you to jump straight to where it is. You have to declare how big your array should be before you can use it. This can cause problems if you don't know how many elements your program needs. It's difficult to insert values into the middle of an array because elements need to be shifted along to make room.

3. Array operations Array elements are accessed using subscript notation: NUMS[2] // 754 They can be written to in the same way: NUMS[4] = 98 // Changes the 97 to 98 Their structure lends itself to processing using loops: loop J from 0 to 7 NUMS[J] = 0 end loop // resets every element to zero 457 239 754 123 97 13 386 334 [0] [1] [2] [3] [4] [5] [6] [7] NUMS

4. Two-dimensional arrays Three different representations of the same 2d array What numbers are referenced by the following? (a) NUMS[0][0] (b) NUMS[1][3] (c) NUMS[2][1]

5. 2d arrays and nested loops loop I from 0 to 2 loop J from 0 to 3 output(ARRAY[I][J]) end loop end loop Note that IB pseudocode doesn't give arrays a length property. for (int i = 0; i < array.length; i++) { for (int j = 0; j < array [i] .length; j++) { System.out.println(array[i][j]); } } In Java, 2d arrays are in fact arrays of arrays. Note carefully that the inner for loop runs up to array[i].length, not array.length. Practice Construct code that will output: The sum of all the numbers The sum of each row of numbers The sum of each column of numbers

6. Linked List Linked lists are normally drawn with boxes and arrows but really they are more like this... 23 HEAD 34 54 77 89 data: 89 next: 0000 124B data: 54 next: 3348 3F4C data: 23 next: 210E AF34 data: 34 next: 3F4C 210E data: 77 next: 124B 3348 HEAD: AF34

7. Linked list nodes Each element of a linked list is called a node . At the least it has (a) some way to store information and (b) a reference to the next node. The code for a Node class in Java would be something like this: class Node { int data; Node next; } 23 HEAD 34 54 77 89 data: 89 next: 0000 124B data: 54 next: 3348 3F4C data: 23 next: 210E AF34 data: 34 next: 3F4C 210E data: 77 next: 124B 3348 HEAD: AF34

8. Constructing a linked list You could make this linked list using the following code: Node head = new Node(); head.data = 23; head.next = new Node(); head.next.data = 34; head.next.next = new Node(); head.next.next.data = 54; head.next.next.next = new Node(); head.next.next.next.data = 77; head.next.next.next.next = new Node(); head.next.next.next.next.data = 89; But as you can see, this approach is not workable as the list grows in size. Instead we use loops to add nodes. 23 HEAD 34 54 77 89 Here is the code to add a node on the end of the list: Node newNode = new Node(); newNode.data = 100; if (head == null) { head = newNode; } else { Node tmp = head; while (tmp.next != null) { tmp = tmp.next; } tmp.next = newNode; } You no longer need to know how to code linked list algorithms, but you may well need to describe linked lists, how they are constructed and how data is inserted.

9. 4 12 32 44 79 HEAD 4 12 32 44 79 BACK 4 12 32 44 79 HEAD HEAD 44 32 12 4 FRONT … HEAD 44 32 12 4 Singly linked list. This is the vanilla linked list. Singly linked list with a tail pointer. The tail pointer allows this list to support queue operations more easily. Doubly linked list. Each node has a "prev" as well as a next. This allows you to access nodes in reverse order . Circular linked list. There is no tail as such because it just points round back to the head. This is good for modelling any order that is inherently circular, such as round-robin scheduling. Circular doubly linked list. You can go round the circle in either direction! Types of linked list

10. Sketching linked list insertion 4 12 32 44 79 HEAD 24 N TMP Step 1: To insert a new node, you need a pointer to the node before the location where the new node will go. Make sure you understand why. Can you explain why? 4 12 32 44 79 HEAD 24 N TMP Step 2: The next thing to do is get the new node's next pointer to point to the tmp's next pointer. 4 12 32 44 79 HEAD 24 N TMP Step 3: Finally TMP's next pointer points to the new node. Note that you cannot do step 3 before you do step 2. Can you explain why not? N.NEXT = TMP.NEXT TMP.NEXT = N N = NEW NODE()

11. Basic Linked List Operations Animation Follow this link for a presentation showing animations of the basic linked list operations. Some of the animations assume you already have a tail pointer , or a pointer to the last-but-one node. If you don't already have those for your own linked list operations, it is easy to find the end of the list using this code: Node tmp = head; while (tmp.next != null) { tmp = tmp.next; } And if you want to find the last-but-one node , you can do this: Node tmp = head; Node lastButOne; while (tmp.next != null) { lastButOne = tmp; tmp = tmp.next; }

12. Arrays vs Linked Lists Arrays Arrays support direct access , so retrieving a value from the middle of the array is O(1) -- ie it's very quick. 👍 Arrays are static . That means you have to say how many elements you want when you declare the array, ie before you use it. This could be bad if you don't know how many elements you're likely to want. If you declare too many and don't use them, then you waste memory . 👎 If you don't declare enough and you need more, then you have to create a whole new array and copy each element across. This takes time . 👎 Adding and deleting elements from the middle of an array is problematic as well, because existing elements need to be shifted along to make room , or shifted back in order to fill up any holes created. 👎 Linked Lists Linked lists only support sequential access ; they don't support direct access since you only have a pointer to the head node. This means to retrieve a value from the middle of the list you have to start at the beginning and loop through the list. This is O(N). 👎 Linked lists are dynamic , which means you don't need to say how big they're going to get. 👍 Linked lists never waste memory because they only contain nodes which have data in them. You also never run out of space to add nodes (unless I guess if you run out of memory entirely). 👍 It is easy to insert into and delete from the middle of a linked list. 👍 Click here to see an animation showing insertion into the middle of an array and a linked list.

13. Feynman Technique Activity: Arrays vs Linked Lists Watch this short video on the Feynman Technique for Learning . Simple, uncluttered explanations of the main points Clear notes with plenty of diagrams In pairs: A explains to B the advantages and disadvantages of arrays . B explains to A the advantages and disadvantages of linked lists . Work together for five minutes to plan one written page of notes. It should contains definitions , explanations (fact + reason) and plenty of simply annotated diagrams . Once your plan is done, produce the page of notes and share a good photo of it.

14. Linked List Activity Prepare cards as follows (add extra as necessary depending on your number of students ) Shuffle all the cards, including the head pointer. Then give each student a card at random and tell them to keep it secret. The head pointer should then identify herself and write the address of the first node clearly on the board. She will then play the part of a tmp pointer that will traverse the list. Rules: Only the head/tmp pointer can ask questions. Other students can only answer: Whose address is… [address]? (Student answers by raising a hand.) The next two questions can only be answered if the tmp pointer is pointing at the student: What is the value of your data? Where are you pointing? Address: 6F31 Data: 34 Next: A112 Address: A112 Data: 45 Next: 3987 Address: 3987 Data: 56 Next: 100D Address: 100D Data: 73 Next: 88C0 Address: 88C0 Data: 82 Next: null Head : 6F31 Using these rules, practice the following algorithms: Finding a specific value in the list Finding the last node in the list Mix students up so that they each get a turn at being the head/tmp node. Introduce further rules (you will need two more students): The head node can spontaneously create: A new node (use a blank card) A pointer pointing to that node Any pointer pointing at a node can instruct their node to change its data value and the address it is pointing to. Using these rules, practice some of the algorithms on the next slide. Each time the group decides on an action, e.g. asking/answering a question, changing a field value, etc, get them to write it down on the board in pseudocode. Build up the full pseudocode for each algorithm. Address: Data: Next:

15. Linked List Methods On the left are some of the methods you can include in your linked list to make it more useful. Concept questions : Which methods are necessary to use your list as a stack? queue? The getNthElement and setNthElement mimic the type of direct access that an array supports. Does this mean your list supports direct access? Discuss. isEmpty() returns true if the list is empty, otherwise false getFirstElement() returns the value of the head node getLastElement() returns the value of the tail node insertAtHead(num) inserts num as the new head node insertAtTail(num) inserts num as the new tail node list() output every item in the list getCount() returns the number of elements in the list exists(num) returns true if num is in the list getIndex(num) returns the (first) index of num in the list removeFromHead() removes the head node removeFromTail() removes the tail node removeElement(num) removes (first, all, etc) occurrences of num from the list getNthElement(n) returns the nth element from the list setNthElement(n, num) sets the data value of the nth element to num insertInOrder(num) inserts num in the right order (ascending or descending as required) From the Guide: Methods that should be known are add (head and tail), insert (in order), delete, list, isEmpty, isFull. Note that we have conceived of a class and specified its behaviour without implementing it in any way. We could just as easily use an array to create this behaviour. This is the idea behind Abstract Data Types (ADTs) . ADTs like this are Collections .

16. Java Code Scaffold public class LinkedListDemo { public static void main(String[] args){ LinkedList.main(null); // remove the call to LinkedList.main() and add // your own code to test the methods you have coded. } } class LinkedList { Node head; public static void main(String[] args){ // This is just a demo LinkedList list = new LinkedList(); int i = 1; list.head = new Node(); list.head.data = i; Node p = list.head; do { i++; p.next = new Node(); p = p.next; p.data = i; } while (i < 10); list.print(); } void print(){ Node p = head; System.out.print("HEAD->"); while (p != null){ System.out.print(p.data + "->"); p = p.next; } System.out.println(); } void insertAtFront(int n) { // insert code } void insertAtTail(int n) { // insert code } void insertInOrder(int n) { // insert code } boolean isEmpty(){ // insert code } } class Node { int data; Node next; } The code on the right can be given to students to scaffold a LinkedList coding task in Java. In Netbeans students would need to name their project LinkedListDemo and paste the code in to their main class window. Alternatively this can be saved to LinkedListDemo.java and compiled from the command line using javac. After the Linked List activity, ask students to work in small coding teams to code the methods in the LinkedList class. Notes: insertInOrder() is quite challenging and is probably beyond the scope of the course. Students will have to think hard about all the possible preconditions such as the list is empty, the new node should be placed at the start, middle, end of the list.

17. Stack A stack a special type of list in which you can only add and remove items from one end. It's called a LIFO (last in first out) data structure because the last item added will always be the first one removed. It's called a stack because it's like a stack of plates. You can only add and remove plates from the top of the stack. Conventionally, the function to add an item is called push and the function to remove an item is called pop . The last function that you need to remember is isEmpty , which should check to see if the stack is empty and which is used to ensure you don't try to pop from an empty stack.

18. Stack: Java code The syllabus requires that you can construct code for the pop, push and isEmpty methods. You may also be required to draw a diagram of the stack before and after various calls to push and pop. This stack uses an array to hold integers. It has room for 100 integers but it must maintain a stack pointer to show where the top of the stack is. Remember that push takes an argument but returns void pop doesn't take an argument but returns a value

19. Uses of Stacks Browser back button Word processor undo button The call stack Evaluating expressions

20. Queue A queue a special type of list in which you can only add items to one end and remove items from the other. It's called a FIFO (first in first out) data structure because the first item added will always be the first one removed. It's called a queue because… Conventionally, the function to add an item is called enqueue and the function to remove an item is called dequeue . The last function that you need to remember is isEmpty , which should check to see if the queue is empty and which is used to ensure you don't try to dequeue from an empty queue.

21. Uses of Queues Keyboard buffers Print queues CPU scheduling

22. Recursion

23. T owers of Hanoi

24. 1 2 3 This is the Towers of Hanoi. You may have seen it before. You have three rods, and some discs which have holes in and slide over the rods.

25. 1 2 3 You have to move all of the discs from 1 to 3 subject to two rules.

26. 1 2 3 You can only move one disc at a time.

27. 1 2 3

28. 1 2 3 And you can't put a larger disc on top of a smaller one.

29. 1 2 3 Now, you could start moving stuff about randomly, but you will quickly find that this is actually quite a tough problem, especially if you have more than a few discs. A moment's thought draws your attention to this guy.

30. 1 2 3 Think: What will the state of the game be when you come to move this disc? Take one full minute to think about it. Don't shout out. We will discuss it in a moment.

31. 1 2 3 Because this one is the biggest, when you move it, you will have to move it to a rod that is empty, and if you want to move it from 1 to 3, then all the others need to be on 2. You quickly realise that at some point, you will have to get to this next position...

32. 1 2 3 Once you have reached this position, then you can move the big one over...

33. 1 2 3 And then work on getting the others from 2 to 3.

34. 1 2 3 ? But how can you get the first four from 1 to 2? Let's consider this as a separate problem.

35. 1 2 3 A moment's thought draws your attention to this guy. Like before, if you want to move it from 1 to 2, then all the others need to be on 3 and you quickly realise that at some point, you will have to get to this position...

36. 1 2 3 Then you can slide the big one over, etc.

37. The problem of the Towers of Hanoi is to move N discs from the source peg to the destination peg via the intermediate peg. In order to solve this problem, we must first move N-1 discs from the source peg to the intermediate peg via the destination peg. Then we move the big disc from the source to the destination peg. Then we again move N-1, but this time from the intermediate peg to the destination peg. Take some time to consolidate your understanding of this.

38. So the solution to the N disc Towers of Hanoi problem can be given in terms of solutions to the N-1 disc Towers of Hanoi problem, and the solution to the N-1 disc Towers of Hanoi problem can be given in terms of solutions to the N-2 disc Towers of Hanoi problem, and so on until we get to the 1 disc Towers of Hanoi problem, which is trivial. When a problem can be solved in terms of the solutions to smaller versions of the same problem it is said to have a recursive solution. The 1 disc problem is said to be the base case . It represents the condition under which we stop recursing.

39. In computing, a recursive function is one which includes in its body at least one call to itself. Here is a Java function that prints the numbers from 1 to 10 using recursion. This example would reward some study if you haven't seen recursion before. Take time to understand exactly how it works. It highlights one disadvantage of recursion: it can be quite confusing, especially to new programmers. What is the base case here?

40. printRecursivelyUpTo(10) printRecursivelyUpTo(9) printRecursivelyUpTo(8) printRecursivelyUpTo(7) printRecursivelyUpTo(6) printRecursivelyUpTo(5) printRecursivelyUpTo(4) printRecursivelyUpTo(3) printRecursivelyUpTo(2) printRecursivelyUpTo(1) printRecursivelyUpTo(0) System.out.println(1); System.out.println(2); System.out.println(3); System.out.println(4); System.out.println(5); System.out.println(6); System.out.println(7); System.out.println(8); System.out.println(9); System.out.println(10); return ; The call stack for the printRecursivelyUpTo function

41. In order to program a solution to the Towers of Hanoi problem, we need to create a function which we can call recursively. So if we wanted to set up a Towers of Hanoi problem of moving 7 discs from peg 1 to the peg 3 via peg 2 then you would use this call:

42. Now, the recursive solution to the Towers of Hanoi problem was something like this: move n-1 discs from the source to the intermediate move the one big disc from the source to the destination move n-1 discs from the intermediate to the destination And the base case was: if there is only one disc: move the disc from the source to the destination So if we write this in our Java function it would be:

43. We now just need to add our base case: if there is only one disc: move the disc from the source to the destination And our function is now: But that can't be it , right?

44. Actually it is. Remarkably, although it may feel like we have only really described how to solve the problem, rather than actually solving it, this code works. The example given is for the 4 disc problem. Function call Output Code

45. Recursion recap Make a copy of the worksheet and enter your answers. Try on your own before you discuss with your table. Define recursive function. [1 mark] State one advantage of recursion and one disadvantage of recursion. [2 marks] Outline how recursion can be used in a binary search. [3 marks] Recursion worksheet

46. Discuss in your table groups. In what ways is this pattern recursive in nature? This is created using a recursive function in Scratch. What would the base case be? What parameters do you think the function must take? What would the recursive function call be? Write the function in pseudocode.

47. This is a Sierpinski Triangle See if you can write the pseudocode Hints: The biggest triangle is drawn first. Each call to the Sierpinski function draws one triangle only. The Sierpinski function contains three recursive calls.

48. Generalized recursive function func (arg1, arg2, …) { if (arg1 == base_case) { return [value] } else { [perform some task] [value = ] func (arg1 (closer to base case), arg2, …) [perform some task] } }

49. Binary Trees

50. Binary tree structure Binary tree: A tree in which each node has at most two children. Tree: A non-linear data structure (representing a strictly hierarchical system of data) where each data item is thought of as a node. Strictly binary tree: A tree in which each node has precisely two children.

51. Node structure Data A data field and two pointers, left and right

52. Recursive! All the nodes together form a binary tree. The nodes within the red triangle also form a binary tree. The nodes within the blue triangle also form a binary tree. How may binary trees are there in total?

53. Binary search tree 50 76 25 12 37 65 89 59 72 83 95 6 17 32 41 Binary search tree: A binary tree that has the following properties: The left subtree of a node contains only nodes with data less than the node's data. The right subtree of a node contains only nodes with data greater than the node's data. Both the left and right subtrees are also binary search trees.

54. Terminology 50 76 25 12 37 65 89 59 72 83 95 6 17 32 41 root node Parent of the node that contains 12 Left child of the node that contains 25 Leaf nodes Right subtree of the tree of which the 76 node is the root

55. Binary trees don’t have to be symmetrical

56. Insertion operation 50 76 25 12 37 65 89 59 72 83 95 6 17 32 41 We want to insert a new node into the tree. Where should we put it? 63

57. Insertion operation 50 76 25 12 37 65 89 59 72 83 95 6 17 32 41 It is bigger than 50, so go down the right subtree… 63

58. Insertion operation 50 76 25 12 37 65 89 59 72 83 95 6 17 32 41 It is smaller than 76, so go down the left subtree… 63

59. Insertion operation 50 76 25 12 37 65 89 59 72 83 95 6 17 32 41 It is smaller than 65, so go down the left subtree… 63

60. Insertion operation 50 76 25 12 37 65 89 59 72 83 95 6 17 32 41 It is bigger than 59, and 59 has no right children, so that’s where it goes. 63

61. Task 50 76 25 12 37 65 89 59 72 83 95 6 17 32 41 Think about how you would code the insert operation… 63

62. The iterative way Don’t think about this too long because there is a beautifully elegant alternative… 50 76 25 12 37 65 89 59 72 83 95 6 17 32 41 63 private Node root; public void insert(int data) { if (root == null) { root = new Node(data); return; } Node tmp = root; while (true) { if (data == tmp.getData()) { // Data is already in the tree return; } else if (data < tmp.getData()) { // insert left if (tmp.getLeft() == null) { tmp.setLeft(new Node(data)); return; } else { tmp = tmp.getLeft(); } } else { // insert right if (tmp.getRight() == null) { tmp.setRight(new Node(data)); return; } else { tmp = tmp.getRight(); } } } }

63. The recursive way Recursion is sometimes tough to get your head round. But can be very simple and very elegant. 50 76 25 12 37 65 89 59 72 83 95 6 17 32 41 63 void insertNode(Node root, int data) { if (data < root.getData()){ if(root.getLeft() == null){ root.setLeft(new Node(data)); } else { insertNode(root.getLeft(), data); } } else { if(root.getRight() == null){ root.setRight(new Node(data)); } else { insertNode(root.getRight(), data); } } } You could be expected to be able to code this type of method from scratch for your exam

64. Binary Tree Traversals "Traversing" a binary tree means visiting every node in turn. 50 76 25 12 37 65 89 59 72 83 95 6 17 32 41 There are three types of traversal: Preorder Inorder Postorder

65. Binary Tree Traversals Let's say that you want to print out your binary tree. Here are the three different traversals. Preorder: When you get to a node: Print the node's data. Then traverse its left subtree. Then traverse its right subtree. Inorder: When you get to a node: Traverse its left subtree. Then print the node's data. Then traverse its right subtree. Postorder: When you get to a node: Traverse its left subtree. Then traverse its right subtree. Then print the node's data. void preOrder(Node n){  if(n == null) return;   print(n);   preOrder(n.left);   preOrder(n.right); } void inOrder(Node n){  if(n == null) return;   inOrder(n.left); print(n);   inOrder(n.right); } void postOrder(Node n){  if(n == null) return;   postOrder(n.left);   postOrder(n.right); print(n); } Which of these would you want to use to print your binary search tree in ascending order?

66. Task Write down the order of the numbers as printed by each of the traversals. 50 76 25 12 37 65 89 59 72 83 95 6 17 32 41 void preOrder(Node n){  if(n == null) return;   print(n);   preOrder(n.left);   preOrder(n.right); } void inOrder(Node n){  if(n == null) return;   inOrder(n.left);   print(n);   inOrder(n.right); } void postOrder(Node n){  if(n == null) return;   postOrder(n.left);   postOrder(n.right);   print(n); }

67. Infix, prefix and postfix notation Consider the following mathematical expression: 4 × (3 + 8) This is written in what is called infix notation , in which the operators (+, - , x, /) are written between their operands. It is the usual notation that you are familiar with from mathematics. However, there are two other ways of writing expressions like these, and both of them are used in computer science. In prefix notation , also known as Polish notation, the operators come before their operands. In postfix notation , also known as Reverse Polish notation, the operators come after their operands. (All operators are assumed to be binary.) This is not on the syllabus any more but it's a good example of how binary trees are used.

68. Examples Infix: 4 × (3 + 8) Convert the following expressions to prefix and postfix: 4 + 5 4 / 3 + 7 (5 + 2) × (3 + 1) 4 / (3 + 6) + 5 × 9 Prefix: × 4 + 3 8 Postfix: 4 3 8 + × This is not on the syllabus any more but it's a good example of how binary trees are used.

69. Why use different notations? Computers normally convert all infix expressions to postfix. Reasons: Brackets are not necessary in postfix expressions There are no rules about precedence in postfix expressions, as there are in infix expressions Postfix expressions are easy to evaluate using stacks Stacks are fast and easy to program This is not on the syllabus any more but it's a good example of how binary trees are used.

70. What has this got to do with binary trees? What happens when the following tree is printed: preorder? inorder? postorder? This is not on the syllabus any more but it's a good example of how binary trees are used.

71. Using stacks to evaluate postfix expressions When we see an operand, push it onto the stack When we see an operator, pop two operands from the stack, do the operation, and push the answer onto the stack Loop If you follow this algorithm, you will be left with one value on the stack, which is the answer to the expression. This is not on the syllabus any more but it's a good example of how binary trees are used.

72. Task Create annotated notes in Word, using drawing objects. Show how 5 x (4 + 3) is converted to postfix notation. Show how the postfix expression is evaluated using a stack. This is not on the syllabus any more but it's a good example of how binary trees are used.

73. Task answer Parse expression 5 × (4 + 3) 3 Convert to postfix: 543+× Push 5 Push 4 Push 3 (diagram 1) 4 5 Pop 3 Pop 4 Push 3 + 4 = 7 (diagram 2) Pop 7 Pop 5 7 5 Push 7 × 5 = 35 (diagram 3) 35 1 2 3 This is not on the syllabus any more but it's a good example of how binary trees are used.

74. Past exam questions

75. Past exam questions (cont.)

76. Recursion A recursive function is a function that calls itself, either directly or indirectly. Recursion is a powerful programming technique in which a problem is divided into a set of similar subproblems, each solved with a trivial solution. Generally, a recursive function calls itself to solve its subproblems. Douglas Crockford, JavaScript the Good Parts, 2008 int fib(int n) { if (n <= 1) return n; else return (fib(n-1) + fib(n-2)); } int factorial(int n) { if (n == 0) return 1; else return (n * factorial(n-1)); } int gcd(int m, int n) { if ((m % n) == 0) return n; else return gcd(n, m % n); } boolean binSearch(int[] x, int start, int end, int n) { if (end < start) return false; int mid = (start+end) / 2; if (x[mid] == n) { return true; } else { if (x[mid] < n) { return binSearch(x, mid+1, end, n); } else { return binSearch(x, start, mid-1, n); } } } Advantages: Some problems are much easier to program using recursion. Disadvantages: Can be confusing. Can take up a lot of memory with repeated calls. Can be slower than iterative alternatives.

77. 32 8 21 10 [0] [0] [1] [2] [3] [1] 4 64 24 19 [2] [0] [1] [2] [3] 44 13 73 50 [0] [1] [2] [3] Junk [0] [1] [2] [3] [0] 32 8 21 10 [1] 4 64 24 19 [2] 44 13 73 50

78. 3 17 43 77 12 65 31 24 13 69