2.3

Classifications of big O notation, ranging from fast efficient algorithms that remain constant despise their input size to the bad ones to be avoided. - Can help you select the most appropriate one to use and optimise your code. O(1) Constant Will always take the same amount of memory (in addition to the list itself). O(n)Linear Best time grows at the same rate as the number of elements This is the case when the data is already in order O(n2) Polynomial / Quadratic Worst and average time is proportional to the square (polynomial) of the number of elements Worst case is when the data is initially in the reverse order Logarithmic complexity: impact of an algorithm directly proportional to the logarithmic result of the input size (e.g., binary search) Exponential complexity: the time it take to execute will double with each additional item in the input.

function enqueue(newJob) if queueTail == 99 then return -1 else queueTail = queueTail + 1 buffer[queueTail] = newJob return 1 endif endfunction

function dequeue() if queueHead > queueTail then return null else queueHead = queueHead + 1 return buffer[queueHead-1] endif endfunction

 Mark A as the initial node and then visit B (5)  Node E (8) is then visited (chosen from C (13), D (14), E (8))  Node I (12) is then visited after E  Node J (14) is then visited after I  Visiting G (18) from I;  Visiting G (15) from C – overriding the previous value of 18  solution A-B-E-I-J path length 14

Heuristic helps produce a solution in a faster time  A* uses estimated distance from final node  Dijkstra uses a weight/distance  A* chooses which path to take next based on lowest current distance travelled AO2: Application  Description of how A* will differ from Dijkstra, e.g. taking the shorter route A-B-E-I before exploring nodes from D and E  Description of the different number of comparisons that would be needed in this problem  A* doesn’t need to find all possible solutions (saves time) AO3: Evaluation Candidates will need to evaluate the benefits and drawbacks of each algorithm  Small-scale problem  Quick to find a solution using either method  Difference in programming complexity is minimal  Don’t know if this problem needs to scale  Most efficient route needed

An array is a static collection of items of the same data type called elements. An array is typically used when the required number of data items is known in advance, to store data that would otherwise be stored in multiple variables. Limitations of using arrays: 1. All data elements in an array must be of the same data type. For example, an array of strings cannot contain an integer. 2. The size of an array is determined when it is declared – i.e., when the algorithm is written – and cannot usually be changed when the program is running.

Assigning data to the array can be carried out using syntax similar to: name[0] = “Craig” name[1] = “Dave” name[2] = “Sam” name[3] = “Carol” Possible to use an iteration to output all the data in the array: For index = 0 to 3 Print(name[index]) Next

data structure that provides a foundation upon which other structures can be built, e.g. stacks, queues, graphs, trees. constricted from nodes and pointers and a start pointer identifies the first node. each node contains data and a pointer to the next node. data in lists can be stored anywhere in memory, with pointers indicating the address of the next item. doubly linked lists have extra pointers, where nodes can point to previous/next items. circular linked lists can be created by making the last node point to the first. doubly circular linked lists is when each node in a circular linked list can also have an additional pointer pointing to the previous item.