Alternative transcript:

the back and removed from the front of an array and the queue will gradually move up along the array until the end of the array is reached • circular queue - reuses the empty slots at the front of the array that are caused when elements are removed from the queue ● o as items are added, the rear index pointer reaches the last position of the array and wraps around to point to the start of the array applications of queues: o print tasks on a print queue o when tasks are waiting to be executed o simulations Trees a connected, undirected graph with no cycles o cycle - a path that starts and ends at the same node o connected - there is a path from any node to any other node o undirected there is no direction associated with an edge root the start node for traversals • branch - a path from the root to an end point • rooted tree - a tree with one node that has been designated as the root • binary tree - a rooted tree where every node has at most two child nodes Component 2.3 revision notes 4 binary search tree - a special type of binary tree which is ordered to optimise searching • uses for trees - ● o used in compilers to build syntax trees o can help speed up searching o can be used to represent Boolean expressions in a way that simplifies the processing of the expression Tree traversals • breadth first traversal - start at the parent node and then read down each layer ● A B E Component 2.3 revision notes G H The order for a breadth first traversal: F, B, G, A, D, I, C, E, H depth first traversal - will go down one branch of the tree as far as possible before trying any other branch the order for a depth first traversal: 1,2,4,5,3,6,7, 5 4 5 7 Linked lists a dynamic data structure • each node has the data relating to the element and a pointer to the next node • to traverse a linked list, start from the first node and follow each next link until you reach the last node ● a new node can either be added by adding it to the front of the list or inserting it into its correct position depending on the order of the list • to delete a node, you need to find it and then adjust pointers Bubble sort • works by going through a list of items, comparing consecutive pairs of items and swapping the items if they are in the wrong order o one of the slowest algorithms for sorting data o takes many passes to get to the correct order o performs poorly in the real world o can be sufficient for short lists Component 2.3 revision notes 6 Insertion sort • works by building up a sorted sub-list in the first part of the original list while the remaining part of the list remains unsorted • at the start of the algorithm, the sorted sub list contains a single item o the algorithm goes through the unsorted part of the list item by item and as each item is examined, it is moved to the correct position in the sorted sub list • fewer comparisons per pass than bubble sort Merge sort • works by splitting items and merging items • it repeatedly splits sub lists in half until each sublist contains only one item o these single item sub lists are then merged together into pairs and are ordered o then lists keep merging to become larger whilst becoming ordered • merge sort performs faster than bubble and insertion sorts on larger lists Quick sort • sorts a list by selecting a pivot value • to sort the list into ascending order: o the list is partitioned so that values lower than the pivot are moved before the pivot and values larger than the pivot are moved after the pivot o the process is repeated on smaller and smaller partitions until the list is fully sorted • similar to merge sort but the ordering is done in place Component 2.3 revision notes 7 ● good performance and low memory requirements Dijkstra's algorithm • works on a weighted, undirected graph • used to find the best way to get from one node to another • the cost of a path is calculated by adding the weights of all the edges that belong to the path A 1. step one: Node A B C B D E 5 Unvisited list Cost (from start) Component 2.3 revision notes 0 ∞ ∞ C с D Previous none none none none none 2 E Node Visited list Cost (from start) Previous 8 2. step two: Node A 3. step three: Node A C Cost (from start) Visited list 4. step four: 0 Visited list Cost (from start) 0 5 Component 2.3 revision notes Previous none Previous none A Node C B D A E B Node C D E Unvisited list Cost (from start) 0 ∞ 8 Unvisited list Cost (from start) 5 8 11 14 Previous none none A none A none none Previous A A nene C nene C 9 Node A C B 5. step five: Node A C B D 6. step six: Node A C B D E Visited list Cost (from start) 0 5 8 Visited list Cost (from start) 0 5 8 9 Visited list Cost (from start) 0 Component 2.3 revision notes 5 8 9 11 Previous none A A Previous none A A B Previous none A A B D Node B D E Node D E Node E Unvisited list Cost (from start) 8 419 14 Unvisited list Cost (from start) 9 14 11 Unvisited list Cost (from start) 11 Previous A GB C Previous B GD Previous D 10 7. The shortest path from A to E would be A, B, D, E and the cost would be 11 can be inefficient o always follows the shortest path from the unvisited list, regardless of the direction or proximity to the target A* Algorithm • uses heuristics to decide the next node to visit 15 B 11 1. step one: 10 10 11 Component 2.3 revision notes 10 A 12 g = cost from start f - cost from start + heuristic 5 6 8 F 5 D 14 0 11 node A B C D E F node A node g-score A 0 2. step two: D ∞ ∞ ∞ ∞ 3. step three: g-score 0 g-score 0 5 Unvisited list f-score 10 Component 2.3 revision notes ∞ ∞ ∞ Visited list f-score 10 Visited list f-score 10 10 previous none none none none none none previous none previous None A node node B C D E F g-score g-score 10 12 ∞ Visited list f-score Unvisited list f-score 25 17 10 ∞ previous previous A A A none none 12 4. step four: node A D C node A D 5. step five: C g-score F 0 5 11 g-score 0 5 Visited list 11 19 Component 2.3 revision notes f-score 10 10 16 Visited list f-score 10 10 16 19 previous None A D previous None A D D node B C E F node B F F g-score 10 42 11 19 g-score 10 22 19 Unvisited list f-score 25 17 16 ∞ 19 Unvisited list f-score 25 32 19 previous A AD none D previous A C D 13 Binary search only works if the list is ordered 1. the algorithm calculates the midpoint value in the list 2. if the item at the midpoint is the item you were looking for the search ends 3. if the item at the midpoint is less than the item you are searching for, you can focus on the items after the midpoint ● 4. if the item at the midpoint is greater than the item you are looking for, you can focus on the items before the midpoint and discard the other side of the list Linear search • looks at every item in the list one after another to check whether this is the item you were looking for can be used on an unordered list • works better on shorter lists as it isn't the most efficient Component 2.3 revision notes 14