Classification of algorithms exam tips

Exam tips

• Compare against problem size

  When explaining algorithm efficiency, always state how time or memory use changes as the problem size increases.

  The specification focuses on complexity as a function relative to problem size, so this makes the comparison relevant and precise.

• Read function notation carefully

  For a notation such as ℕ → ℕ, identify the first set as the domain and the second set as the co-domain before describing the mapping.

  This prevents the input and output sets from being reversed and gives a precise explanation of the function.

• Trace loops systematically

  For each loop, determine how many times it executes and multiply the counts for nested loops.

  This provides a reliable method for deriving linear and polynomial complexities instead of guessing from the appearance of the code.

• Link complexity to hardware

  When explaining limits of computation, describe how resource requirements grow and then relate those requirements to finite processing speed or memory.

  This directly addresses both parts of the specification requirement and produces a more complete explanation than discussing either factor alone.

• Use the exact classification criterion

  When defining the terms, explicitly include the phrase polynomial (or less) time solution.

  This phrase distinguishes tractable problems from intractable problems and directly matches the specification.

• Use the word algorithm

  When defining computable and non-computable problems, explicitly refer to whether an algorithmic solution exists.

  The distinction in the specification is about what can and cannot be solved algorithmically, so this wording directly addresses the required knowledge.

• State both the definition and the significance

  For a longer response, explain that the Halting problem asks whether any program eventually stops for particular input, then state that some problems cannot be solved by a computer.

  This covers both parts of the specification requirement and avoids giving only a partial definition.