Discrete Mathematics Strand

Discrete mathematics is a contemporary field of mathematics that is widely used in business and industry. It is sometimes called the mathematics of computers, or the mathematics used to optimize finite systems. It is an important part of the high school mathematics curriculum. According to the National Council of Teachers of Mathematics (2000), "discrete mathematics should be an integral part of the school mathematics curriculum" (Principles and Standards for School Mathematics, p. 31). Discrete mathematics is used to answer questions like the following:

• What is the most efficient route to plow all the streets in this neighborhood after a snowstorm (or pick up all the trash)?

• What is the best way to schedule 8 committee meetings without any conflicts, given that some people are on more than one committee?

• How can we schedule all the tasks on this large project (like a construction project or a new product launch) so that the entire project is finished in the least amount of time?

• Will there be enough phone numbers available to accommodate all the phones, faxes, and mobile phones in this area?

• What is the optimal medicine dosage for a patient, in order to maintain the right amount of medicine in the body while it is naturally metabolized?

• How can we model and analyze a changing population, or the changing amount of money in an investment program?

There are 4 main discrete mathematics topics in the Core-Plus Mathematics curriculum, which are used to answer questions like those above.

1. Vertex-Edge Graphs - Diagrams consisting of points (vertices) and line segments (edges) connecting some or all of the points

These mathematical diagrams can be used to solve problems related to networks and paths. Also, you can use vertex-edge graphs to solve problems related to relationships, like conflict or prerequisite, among a finite number of objects. For example, the network might be a road network or a communication network, and you might want to find a shortest path through the network or a travel route that visits each designated city exactly once. Core-Plus Mathematics students also learn the most common application of vertex-edge graphs in business and industry - using critical path analysis (also called the PERT technique) to efficiently schedule large projects.

2. Recursive Formulas - Formulas that describe the current state of a system in terms of previous states

Recursive formulas can be used to solve problems related to sequential, step-by-step change. For example, you can use recursive formulas to compute the amount of money in a savings account over time, the monthly payment for a car loan, the changing chlorine concentration in a swimming pool, or the predicted population of a whale species ten years from now.

3. Counting - Using mathematical techniques to systematically count objects

For example, you might want to count the number of possible computer passwords or ATM personal identification numbers (PINs) to make sure there are enough possibilities for all the customers, and also enough so that someone can't break into the system simply by trying all possibilities. Counting also has important purely mathematical uses, such as determining the coefficients in the expansion of algebraic expressions like (a + b)¹².

4. Matrices - Rectangular arrays of numbers

Matrices are used in algebra, geometry, statistics, and probability, with many applications in science, business, and industry. For example, a matrix can be used to store and manipulate data, such as the statistics from a baseball game or the results of an experiment, to create computer animations, or to solve systems of linear equations.

These are the main topics of discrete mathematics contained in the Core-Plus Mathematics curriculum. They are included because they are important in mathematics, in real-world applications, and in contemporary life. The Mathematical Strands Chart shows the sequence of discrete mathematics units and provides links to more detailed overviews of the topics studied.

Course 1

Unit 4 - Vertex-Edge Graphs develops student understanding of vertex-edge graphs and ability to use these graphs to represent and solve problems involving paths, networks, and relationships among a finite number of elements, including finding efficient routes and avoiding conflicts.

Topics include: vertex-edge graphs, mathematical modeling, optimization, algorithmic problem solving, Euler circuits and paths, matrix representation of graphs, vertex coloring and chromatic number.

Course 2

Unit 2 - Matrix Methods develops student understanding of matrices and ability to use matrices to represent and solve problems in a variety of real-world and mathematical settings.

Topics include: constructing and interpreting matrices, row and column sums, matrix addition, scalar multiplication, matrix multiplication, powers of matrices, inverse matrices, properties of matrices, and using matrices to solve systems of linear equations.

Unit 6 - Network Optimization develops student understanding of vertex-edge graphs and ability to use these graphs to solve network optimization problems.

Topics include: optimization, mathematical modeling, algorithmic problem solving, digraphs, trees, minimum spanning trees, distance matrices, Hamilton circuits and paths, the Traveling Salesperson Problem, critical paths, and the PERT technique.

Course 3

Unit 7 - Recursion and Iteration extends student ability to represent, analyze, and solve problems in situations involving sequential and recursive change.

Topics include: iteration and recursion as tools to model and analyze sequential change in real-world contexts, including compound interest and population growth; arithmetic, geometric, and other sequences; arithmetic and geometric series; finite differences; linear and nonlinear recurrence relations; and function iteration, including graphical iteration and fixed points.

Course 4

Unit 8 - Counting Methods and Induction extends student ability to count systematically and solve enumeration problems, and develops understanding of, and ability to do, proof by mathematical induction.

Topics include: systematic listing and counting, counting trees, the Multiplication Principle of Counting, Addition Principle of Counting, combinations, permutations, selections with repetition; the binomial theorem, Pascal’s triangle, combinatorial reasoning; the general multiplication rule for probability; and the Principle of Mathematical Induction.

Unit 10 - Mathematics of Information Processing and the Internet develops student understanding of the mathematical concepts and methods related to information processing, particularly on the Internet, focusing on the key issues of access, security, accuracy, and efficiency.

Topics include: elementary set theory and logic; modular arithmetic and number theory; secret codes, symmetric-key and private-key cryptosystems; error-detecting codes (including ZIP, UPC, and ISBN) and error-correcting codes (including Hamming distance); and trees and Huffman coding.

Unit 11 - Mathematics of Democratic Decision Making develops student understanding of the mathematical concepts and methods needed to make decisions in a democratic society, as related to voting and fair division.

Topics include: preferential voting and associated vote-analysis methods such as majority, plurality, runoff, points-for-preferences (Borda method), and pairwise-comparison (Condorcet method); weighted voting; and fair division techniques, including apportionment methods.