Computer ScienceCode 9618
Algorithms
What this topic asks you to be able to do
- Demonstrate an understanding of how linear and binary search methods work
- Write an algorithm that carries out a linear search
- Write an algorithm that performs a binary search
- Demonstrate an understanding of how insertion sort and bubble sort work
- Write an algorithm that carries out an insertion sort
- Write an algorithm that performs a bubble sort
- Demonstrate an understanding of Abstract Data Types (ADT) and their use
- Write algorithms which find an item held in a linked list and in a binary tree
- Write algorithms that add a new item to a stack, a queue, a linked list and a binary tree
- Write algorithms that remove an item from a stack, a queue and a linked list
- Show an understanding that graphs count as one kind of ADT
- Describe a graph's key features and justify using one in a particular situation
- Show how ADTs can be implemented by building them on another ADT
- Describe each of these ADTs, and demonstrate how it can be implemented from suitable built-in types or from other ADTs: binary tree, dictionary, linked list, queue, stack
- Demonstrate an understanding that algorithms doing the same job can be compared against criteria (e.g. how much memory each uses and how long each takes to finish the task)
- Show an understanding of how Big O notation is employed to state time and space complexity