Virginia

DM.LR Logical Reasoning

• DM.LR.1 The student will use reasoning to develop and apply logical arguments.

  • 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.

    • Converses, inverses, and contrapositives (G-A.5)

  • 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.

    • Truth tables (G-A.7)

  • DM.LR.1.f Identify the rules of inference and model basic logical statements including De Morgan's Law.

    • Truth values (G-A.8)

  • DM.LR.1.g Apply logical reasoning to model contextual situations and make decisions.

    • Identify hypotheses and conclusions (G-A.1)
    • Counterexamples (G-A.2)
    • Conditionals (G-A.3)
    • Negations (G-A.4)
    • Converses, inverses, and contrapositives (G-A.5)
    • Biconditionals (G-A.6)

• DM.LR.2 The student will apply logic and proof techniques in the construction of a sound argument.

  • DM.LR.2.a Apply informal logical reasoning to contextual problems.

    • Use logical reasoning to find the order (G)

  • DM.LR.2.b Outline the basic structure of a proof technique.

  • 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.

    • Truth tables (G-A.7)
    • Truth values (G-A.8)

• DM.LR.3 The student will apply Boolean algebra to represent and analyze the function of logical gates and circuits.

  • 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 The student will use mathematical induction to prove formulas and mathematical statements.

  • 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.

    • Pascal's triangle and the Binomial Theorem (PC-E.10)

DM.SNT Set and Number Theory

• DM.SNT.1 The student will identify and use the properties of sets and set operations.

  • DM.SNT.1.a Compare and contrast sets, relations, and functions.

    • Sets, subsets, and complements (A1-G.1)

  • DM.SNT.1.b Express relationships between sets using Venn diagrams.

  • DM.SNT.1.c Describe a set using set-builder notation.

    • Set-builder notation (A1-G.2)

  • DM.SNT.1.d Construct new sets using the set operations intersection, union, difference, and complement.

    • Unions and intersections of sets (A1-G.4)

  • DM.SNT.1.e Identify the laws of set theory.

  • 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 The student will apply the formulas of combinatorics.

  • DM.SNT.2.a Create a tree diagram to represent relationships between independent events.

    • Identify independent events (A2-OO.6)
    • Independence and conditional probability (A2-OO.9)

  • DM.SNT.2.b Use the Fundamental (Basic) Counting Principle to determine the number of possible outcomes of an event.

    • Counting principle (A2-OO.2)

  • DM.SNT.2.c Determine the number of combinations possible when subsets of r elements are selected from a set of n elements without regard to order.

    • Combinations and permutations (PC-CC.2)
    • Combinations II (A2)
    • Combination notation (G)
    • Find probabilities using combinations (G)

  • DM.SNT.2.d Determine the number of permutations possible when r objects selected from n objects are ordered.

    • Permutations (A2)
    • Combinations and permutations (PC-CC.2)
    • Permutation notation (G)
    • Find probabilities using permutations (G)

  • 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 The student will use Pascal's Triangle to analyze numerical patterns and relationships.

  • DM.SNT.3.a Construct Pascal's Triangle.

    • Pascal's triangle (PC-E.9)

  • DM.SNT.3.b Expand binomials having positive integral exponents, using the Binomial Theorem and Pascal's Triangle.

    • Pascal's triangle and the Binomial Theorem (PC-E.10)
    • Binomial Theorem I (PC-E.11)
    • Binomial Theorem II (PC-E.12)

  • 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.

    • Pascal's triangle (PC-E.9)

DM.GT Graph Theory

• DM.GT.1 The student will represent problems using vertex-edge graphs. The concepts of degree, connectedness, paths, planarity, and directed graphs will be analyzed.

  • DM.GT.1.a Illustrate the basic terminology of graph theory.

  • 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 (F = E – V + 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 The student will solve problems through analysis and application of circuits, cycles, Euler paths, Euler circuits, Hamilton paths, and Hamilton circuits. Optimal solutions will be determined using existing algorithms and student-created algorithms.

  • 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 n vertices.

  • DM.GT.2.d Use an Euler circuit algorithm to solve optimization problems.

• DM.GT.3 The student will apply graphs to conflict-resolution problems, such as graph coloring, scheduling, matching, and optimization.

  • 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 The student will recognize and apply algorithms to solve configuration, conflict-resolution, and sorting problems.

  • 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 The student will use algorithms to schedule tasks to determine a minimum project time.

  • 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.

DM.CM Computational Methods

• DM.CM.1 The student will describe and apply sorting and searching algorithms used in processing and communicating information.

  • 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 The student will use recursive processes.

  • DM.CM.2.a Compare and contrast iterative and recursive processes.

    • Find a recursive formula (PC-AA.4)
    • Convert a recursive formula to an explicit formula (PC-AA.6)
    • Convert an explicit formula to a recursive formula (PC-AA.7)
    • Convert between explicit and recursive formulas (PC-AA.8)

  • DM.CM.2.b Use recursive processes to model growth and decay.

    • Exponential growth and decay: word problems (PC-K.5)

  • 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 The student will identify and apply cryptographic methods.

  • 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.

    • Prime factorization (A1)

  • DM.CM.3.d Describe how the complexity of prime factorization is used in cryptography.

  • DM.CM.3.e Describe modular arithmetic in context.

  • 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.

• DM.CM.4 The student will analyze the limitations of algorithms and their contextual relationships in computing.

  • 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.