• Show understanding of linear and binary searching methods
  • Write an algorithm to implement a linear search
  • Write an algorithm to implement a binary search
  • The conditions necessary for the use of a binary search
  • How the performance of a binary search varies according to the number of data items
• Show understanding of insertion sort and bubble sort methods
  • Write an algorithm to implement an insertion sort
  • Write an algorithm to implement a bubble sort
  • Performance of a sorting routine may depend on the initial order of the data and the number of data items
• Show understanding of and use Abstract Data Types (ADT)
  • Write algorithms to find an item in each of the following: linked list, binary tree
  • Write algorithms to insert an item into each of the following: stack, queue, linked list, binary tree
  • Write algorithms to delete an item from each of the following: stack, queue, linked list
  • Show understanding that a graph is an example of an ADT. Describe the key features of a graph and justify its use for a given situation. Candidates will not be required to write code for a graph structure
• Show how it is possible for ADTs to be implemented from another ADT
  • Describe the following ADTs and demonstrate how they can be implemented from appropriate built-in types or other ADTs: stack, queue, linked list, dictionary, binary tree
• Show understanding that different algorithms which perform the same task can be compared by using criteria (e.g. time taken to complete the task and memory used)
  • Including use of Big O notation to specify time and space complexity