Virginia flagVirginia: Discrete Mathematics Math Standards

88 standards · 4 domains

COMPUTATIONAL METHODS

  • DM.CM.1.a Select and apply a sorting algorithm, such as a bubble sort, merge sort, or network sort.
  • DM.CM.1.b Describe the advantages and disadvantages of various sorting algorithms.
  • DM.CM.1.c Analyze the knapsack and bin-packing problems.
  • DM.CM.1.d Select and apply search algorithms to analyze problems.
  • DM.CM.1.e Determine the average, best-case, and worst-case reasoning for different searches.
  • DM.CM.2.a Compare and contrast iterative and recursive processes.
  • DM.CM.2.b Use recursive processes to model growth and decay.
  • DM.CM.2.c Use recursive processes to create fractals.
  • DM.CM.2.d Use recursive processes to generate the Fibonacci sequence.
  • DM.CM.2.e Determine if a recursive solution is more efficient than an iterative solution.
  • DM.CM.3.a Compare and contrast ciphers and codes.
  • DM.CM.3.b Describe the evolution of cipher systems.
  • DM.CM.3.c Identify the Fundamental Theorem of Arithmetic.
  • DM.CM.3.d Describe how the complexity of prime factorization is used in cryptography.
  • DM.CM.3.e Describe modular arithmetic in context (e.g., clocks, days of the week, measures of time).
  • DM.CM.3.f Analyze the relationship between divisibility and modulus.
  • DM.CM.3.g Determine congruence within modular arithmetic.
  • DM.CM.3.h Perform operations within modular arithmetic.
  • DM.CM.3.i Apply modular arithmetic to problems in context (e.g., cryptography, International Standard Book Number (ISBN), International Bank Account Number (IBAN)).
  • DM.CM.4.a Describe maximum complexity of an algorithm using Big O notation.
  • DM.CM.4.b Describe Turing machines and how they are used to test the limits of computation.
  • DM.CM.4.c Describe the halting problem and explain how it characterizes the fundamental limitations of computation and undecidability.
  • DM.CM.4.d Explain the P versus NP problem and defend a justification for equality, inequality, or undecidability.
  • DM.CM.4.e Analyze how the equivalence of P- and NP-class problems might impact society.

GRAPH THEORY

  • DM.GT.1.a Illustrate the basic terminology of graph theory (e.g., vertex, edge, graph, degree of a vertex).
  • DM.GT.1.b Use graphs to map situations in which the vertices represent objects, and edges represent a particular relationship between objects.
  • DM.GT.1.c Identify and describe degree and connectedness.
  • DM.GT.1.d Determine whether a graph is planar or nonplanar.
  • DM.GT.1.e Analyze the relationship between faces, edges, and vertices using Euler’s formula (𝐹 = 𝐸 – 𝑉 + 2).
  • DM.GT.1.f Use directed graphs (digraphs) to represent situations with restrictions in traversal possibilities.
  • DM.GT.1.g Determine when graphs are trees.
  • DM.GT.2.a Determine whether a graph has an Euler circuit or path, and determine the circuit or path, if it exists.
  • DM.GT.2.b Determine whether a graph has a Hamilton circuit or path, and determine the circuit or path, if it exists.
  • DM.GT.2.c Count the number of Hamilton circuits for a complete graph with 𝑛 vertices.
  • DM.GT.2.d Use an Euler circuit algorithm to solve optimization problems.
  • DM.GT.3.a Model projects consisting of several subtasks, using a graph.
  • DM.GT.3.b Use graphs to resolve conflicts that arise in scheduling.
  • DM.GT.3.c Use graph coloring to determine the chromatic number of a graph.
  • DM.GT.4.a Recognize algorithms such as nearest neighbor, brute force, and cheapest link as they apply to graphs.
  • DM.GT.4.b Use Kruskal’s algorithm to determine the shortest spanning tree of a connected graph.
  • DM.GT.4.c Use Prim’s algorithm to determine the shortest spanning tree of a connected graph.
  • DM.GT.4.d Use Dijkstra’s algorithm to determine the shortest spanning tree of a connected graph.
  • DM.GT.5.a Specify in a digraph the order in which tests are to be performed.
  • DM.GT.5.b Identify the critical path to determine the earliest completion time (minimum project time).
  • DM.GT.5.c Use the list-processing algorithm to determine an optimal schedule.
  • DM.GT.5.d Create and test scheduling algorithms.

LOGICAL REASONING

  • DM.LR.1.a Use Venn diagrams to codify and solve logic problems.
  • DM.LR.1.b Express logical statements in symbolic form.
  • DM.LR.1.c Represent a conditional statement as its converse, inverse, and contrapositive.
  • DM.LR.1.d Describe how symbolic logic can be used to map the processes of computer applications.
  • DM.LR.1.e Construct a truth table to display all possible input combinations and their outputs.
  • DM.LR.1.f Identify the rules of inference and model basic logical statements including De Morgan’s Law.
  • DM.LR.1.g Apply logical reasoning to model contextual situations and make decisions.
  • DM.LR.2.a Apply informal logical reasoning to contextual problems (e.g., predicting the behavior of software, solving puzzles).
  • DM.LR.2.b Outline the basic structure of a proof technique (e.g., direct proof, proof by contradiction, induction).
  • DM.LR.2.c Deduce the best type of proof for a given problem.
  • DM.LR.2.d Use the rules of inference to construct direct proofs and proofs by contradiction.
  • DM.LR.2.e Construct induction proofs involving summations and inequalities.
  • DM.LR.2.f Use a truth table to prove the logical equivalence of statements.
  • DM.LR.3.a Explain basic properties of Boolean algebra: duality, complements, and standard forms.
  • DM.LR.3.b Represent verbal statements as Boolean expressions.
  • DM.LR.3.c Apply Boolean algebra to prove identities and simplify expressions.
  • DM.LR.3.d Generate truth tables that encode the truth and falsity of two or more statements.
  • DM.LR.3.e Explain the operation of discrete logic gates.
  • DM.LR.3.f Describe the relationship between Boolean algebra and electronic circuits.
  • DM.LR.3.g Analyze a combinational network using Boolean expressions.
  • DM.LR.3.h Design simple combinational networks that use NAND (AND followed by NOT), NOR (OR followed by NOT), and XOR (exclusive-OR) gates.
  • DM.LR.4.a Compare and contrast inductive and deductive reasoning.
  • DM.LR.4.b Explain the relationship between weak and strong induction.
  • DM.LR.4.c Construct induction proofs involving a divisibility argument.
  • DM.LR.4.d Prove the Binomial Theorem through mathematical induction.

SET AND NUMBER THEORY

  • DM.SNT.1.a Compare and contrast sets, relations, and functions.
  • DM.SNT.1.b Express relationships between sets using Venn diagrams.
  • DM.SNT.1.c Describe a set using set-builder notation.
  • DM.SNT.1.d Construct new sets using the set operations intersection, union, difference, and complement.
  • DM.SNT.1.e Identify the laws of set theory (e.g., associative, commutative, distributive, De Morgan’s Law).
  • DM.SNT.1.f Use the principle of inclusion and exclusion to determine the size of a set.
  • DM.SNT.1.g Use the properties of set operations to prove set equality.
  • DM.SNT.2.a Create a tree diagram to represent relationships between independent events.
  • DM.SNT.2.b Use the Fundamental (Basic) Counting Principle to determine the number of possible outcomes of an event.
  • DM.SNT.2.c Determine the number of combinations possible when subsets of 𝑟 elements are selected from a set of 𝑛 elements without regard to order.
  • DM.SNT.2.d Determine the number of permutations possible when 𝑟 objects selected from 𝑛 objects are ordered.
  • DM.SNT.2.e Use the pigeonhole principle to solve packing problems to facilitate proofs.
  • DM.SNT.2.f Construct a proof by induction using principles of combinatorics.
  • DM.SNT.3.a Construct Pascal’s Triangle.
  • DM.SNT.3.b Expand binomials having positive integral exponents, using the Binomial Theorem and Pascal’s Triangle.
  • DM.SNT.3.c Compare the binomial coefficient to the calculation of combinations.
  • DM.SNT.3.d Identify the Fibonacci numbers within Pascal’s Triangle.