SOL Prep

Computational Methods

Virginia SOL DM.CM.4

Analyze the limitations of algorithms and their contextual relationships in computing.

Study DM.CM.4 with SOL PrepBack to Discrete Mathematics

What students need to be able to do

  • Describe maximum complexity of an algorithm using Big O notation.
  • Describe Turing machines and how they are used to test the limits of computation.
  • Describe the halting problem and explain its implications for computation and undecidability.
  • Explain the P versus NP problem and defend a justification for equality, inequality, or undecidability.
  • Analyze how the equivalence of P- and NP-class problems might impact society.