Algorithms - MEI D1 Specification

Background and definition

  1. Be able to interpret and apply algorithms presented in a variety of formats
  2. Be able to develop and adapt simple algorithms

Basic ideas of complexity

  1. Understand the basic ideas of algorithmic complexity
  2. Be able to analyse the complexity of some of the algorithms covered in this specification

Notes

  • Flowcharts; written English; pseudo code.
  • To include sorting and packing algorithms.
  • Sorting: Bubble, Shuttle, insertion, quick sort.
  • Packing: Full-bin, first-fit, first-fit decreasing.
  • Candidates will not be required to memorise sorting algorithms.
  • Candidates will be expected to know the packing algorithms.

  • Worst case; size of a problem; that for quadratic algorithms doubling the size of a large problem can quadruple the solution time, etc.
  • Use order notation, e.g. O(n2) for quadratic complexity.
  • Kruskal, Prim (network and tabular forms), Dijkstra.

The requirements will also apply to algorithms in later modules (D2 and DC) at the stage when they are met.