Identify properties of simple graphs, complete graphs, bipartite graphs, complete bipartite graphs, and trees.
Solve problems involving networks through investigation and application of existence and nonexistence of Euler paths, Euler circuits, Hamilton paths, and Hamilton circuits. Note: Real-world contexts modeled by graphs may include roads or communication networks.
Example: show why a 5x5 grid has no Hamilton circuit.
Students know:
Students are able to:
Students understand that:
Develop optimal solutions of application-based problems using existing and student- created algorithms.
Give an argument for graph properties.
Example: Explain why a graph has a Euler cycle if and only if the graph is connected and every vertex has even degree. Show that any tree with n vertices has n - 1 edges.
Apply algorithms relating to minimum weight spanning trees, networks, flows, and Steiner trees.
Example: traveling salesman problem
Students know:
Students are able to:
Students understand that:
Use shortest path techniques to find optimal shipping routes.
Show that every connected graph has a minimal spanning tree.
Use Kruskal’s Algorithm and Prim’s Algorithm to determine the minimal spanning tree of a weighted graph.
Use vertex-coloring, edge-coloring, and matching techniques to solve application-based problems involving conflict.
Examples: Use graph-coloring techniques to color a map of the western states of the United States so that no adjacent states are the same color, determining the minimum number of colors needed and why no fewer colors may be used; use vertex colorings to determine the minimum number of zoo enclosures needed to house ten animals given their cohabitation constraints; use vertex colorings to develop a time table for scenarios such as scheduling club meetings or for housing hazardous chemicals that cannot all be safely stored together in warehouses.
Students know:
Students are able to:
Students understand that:
Determine the minimum time to complete a project using algorithms to schedule tasks in order, including critical path analysis, the list-processing algorithm, and student-created algorithms.
Students know:
Students are able to:
Students understand that:
Use the adjacency matrix of a graph to determine the number of walks of length n in a graph.
Students know:
Students are able to:
Students understand that:
Analyze advantages and disadvantages of different types of ballot voting systems.
Students know:
Students are able to:
Students understand that:
Identify impacts of using a preferential ballot voting system and compare it to single candidate voting and other voting systems.
Analyze the impact of legal and cultural features of political systems on the mathematical aspects of elections.
Examples: mathematical disadvantages of third parties, the cost of run-off elections
Apply a variety of methods for determining a winner using a preferential ballot voting system, including plurality, majority, run-off with majority, sequential run-off with majority, Borda count, pairwise comparison, Condorcet, and approval voting.
Students know:
Students are able to:
Students understand that:
Identify issues of fairness for different methods of determining a winner using a preferential voting ballot and other voting systems and identify paradoxes that can result.
Example: Arrow’s Theorem
Students know:
Students are able to:
Students understand that:
Use methods of weighted voting and identify issues of fairness related to weighted voting.
Example: determine the power of voting bodies using the Banzhaf power index
Students know:
Students are able to:
Students understand that:
Distinguish between weight and power in voting.
Explain and apply mathematical aspects of fair division, with respect to classic problems of apportionment, cake cutting, and estate division. Include applications in other contexts and modern situations.
Students know:
Students are able to:
Students understand that:
Identify and apply historic methods of apportionment for voting districts including Hamilton, Jefferson, Adams, Webster, and Huntington-Hill. Identify issues of fairness and paradoxes that may result from methods.
Examples: the Alabama paradox, population paradox
Students know:
Students are able to:
Students understand that:
Use spreadsheets to examine apportionment methods in large problems.
Example: apportion the 435 seats in the U.S. House of Representatives using historically applied methods
Students know:
Students are able to:
Students understand that:
Critically analyze issues related to information processing including accuracy, efficiency, and security.
Students know:
Students should be able to: Give examples of information processing where accuracy, efficiency or security may be an issue.
Students understand that:
Apply ciphers (encryption and decryption algorithms) and cryptosystems for encrypting and decrypting including symmetric-key or public-key systems.
Students know:
Students are able to:
Students understand that:
Use modular arithmetic to apply RSA (Rivest-Shamir-Adleman) public-key cryptosystems.
Use matrices and their inverses to encode and decode messages.
Apply error-detecting codes and error-correcting codes to determine accuracy of information processing.
Students know:
Students are able to:
Students understand that:
Apply methods of data compression.
Example: Huffman codes
Students know:
Students are able to:
Students understand that:
Define the constant e in a variety of contexts.
Example: the total interest earned if a 100% annual rate is continuously compounded.
Explore the behavior of the function $y=e^x$ and its applications.
Explore the behavior of the function $y=e^x$ and its applications.
Find the conjugate of a complex number; use conjugates to find moduli and quotients of complex numbers.
Represent complex numbers on the complex plane in rectangular and polar form (including real and imaginary numbers), and explain why the rectangular and polar forms of a given complex number represent the same number.
Represent addition, subtraction, multiplication, and conjugation of complex numbers geometrically on the complex plane; use properties of this representation for computation.
Example: $(-1 + \sqrt{3i})^3 = 8$ because $(-1 + \sqrt{3i})$ has modulus 2 and argument $120^{\circ}$.
Represent addition, subtraction, multiplication, and conjugation of complex numbers geometrically on the complex plane; use properties of this representation for computation.
Example: $(-1 + \sqrt{3i})^3 = 8$ because $(-1 + \sqrt{3i})$ has modulus 2 and argument $120^{\circ}$.
Analyze possible zeros for a polynomial function over the complex numbers by applying the Fundamental Theorem of Algebra, using a graph of the function, or factoring with algebraic identities.
