Adult and Community Education
        Search FCPS:   


Program of Study for High School Mathematics

DISCRETE MATHEMATICS (315460, 315461)
Grade: 11-12
Prerequisite: Algebra 2 or Advanced Algebra GT
Credit: One-half (315460) or One (315461)

Overview

Required Basal Textbooks


Overview

315460: Course content includes management science, the mathematics of apportionment, matrix operations and applications, recursion, and discrete applications in the natural and social world.

315461: Course content includes management science, the mathematics of apportionment, matrix operations and applications, recursion, and discrete applications in the natural and social world. The course also includes theory of probability, description of statistical measurements, probability distributions, and statistical inference.

back to top


Required Basal Textbooks

· Crisler, Fisher, & Froelich. Discrete Mathematics Through Applications. W H Freeman. 2000.

· Tannenbaum & Arnold. Excursions in Modern Mathematics. Prentice-Hall. 2001.

· Scheinerman. Mathematics: A Discrete Introduction. Thompson Learning. 2000.


I. Management Science

Benchmark

None

Key Terms

none

Indicators

  1. Learn graph theory terminology.
    1. Define a graph and its parts.
      1. edges
      2. vertices
    2. Represent solutions with graphs.
    3. Use a matrix to represent a graph.
    4. Describe a directed graph.
    5. Describe a path, a circuit, and a cycle.
    6. Describe distance and the shortest path of a graph and weighted graph.

  2. Apply Euler’s graph theory.
    1. Recognize Euler paths and circuits.
    2. State Euler’s theorem.
    3. Use Euler’s theorem to find good Eulerizations.
    4. Apply Euler’s theorem to the Chinese postman problem.

  3. Apply Hamilton’s graph theory.
    1. Recognize Hamiltonian paths and circuits.
    2. Apply algorithms to Hamiltonian paths and circuits.
      1. nearest-neighbor algorithm
      2. sorted-edges algorithm
    3. Apply Hamiltonian graph theory to the traveling salesman problem.
    4. Construct a minimum spanning tree.
    5. Use Kriskal’s algorithm to solve minimum spanning trees.
    6. Perform critical-path analysis.
      1. order-requirement digraph
      2. list-processing algorithm
    7. Use the fundamental principle of counting to know when a problem is NP complete.
    8. Find Steiner points (optional).

  4. Apply principles of graph coloring.
    1. Describe how to “color a graph.”
    2. Find the chromatic number of a graph.
    3. Use graph coloring for scheduling problems.
    4. Use graph coloring to demonstrate the 4-color map conjecture.

back to top


II.Mathematics of Apportionment

Benchmark
None

Key Terms

none

Indicators

  1. Demonstrate the use of various methods for determining the outcome of an election.
    1. Compute election winners by:
      1. plurality method.
      2. runoff method.
      3. sequential runoff method.
      4. Borda method.
      5. Condorcet method.
    2. State and discuss the issue of fairness using Arrow’s theorem.

  2. Describe weighted voting systems.
    1. Determine winning coalitions.
    2. Compute the power index (Banzhaf).

  3. Use organizational procedures for fair division.
    1. Apply continuous case division for two or more participants.
    2. Apply discrete case division for two or more participants.

  4. Describe relationships involving apportionment.
    1. Compare and contrast the historical apportionment methods:
      1. Hamilton
      2. Jefferson
      3. Hill-Huntington
      4. Webster
    2. Apply apportionment methods to nongovernmental situations.
      1. scheduling
      2. sports salary caps

  5. Apply game theory strategies to situations involving conflict and cooperation. (Optional)
    1. Create a game matrix.
    2. Determine the value of the game matrix.
    3. Identify zero-sum and nonzero-sum games.
    4. Demonstrate the strategies behind:
      1. the prisoner’s dilemma.
      2. the game of chicken.
      3. inspection games.
      4. duel games.
      5. equilibrium.
    5. e. Discuss the definition of fairness as related to game theory.

back to top


III. Matrices

Benchmark
None

Key Terms

none

Indicators

  1. Identify and define terms relating to matrices.

  2. Create a matrix on paper, graphing calculator, and computer.

  3. Perform matrix operations of addition, subtraction, and multiplication on paper, graphing calculator, and computer.

  4. Find the inverse of a matrix and state its application.

  5. Apply the Leslie matrix model to population models.

  6. Apply the Leontief model to economic situations.

  7. Apply the Markov chain to probability models.

back to top


IV. Recursion

Benchmark
None

Key Terms

none

Indicators

  1. Define recursion.

  2. Model and describe classic recursion problems such as:
    1. hand shake
    2. Tower of Hanoi
    3. Pascal’s triangle
    4. Von Kock snowflake
    5. Sierpinski’s triangle or gasket

  3. Investigate difference equations.
    1. Write first- and second-degree difference equations.
    2. Use the process of finite differences to convert difference equations into explicit equations.
    3. Use mathematical modeling to prove difference equations (optional).

  4. Demonstrate cobwebbing (graphical iteration) manually and with a graphing calculator.

back to top


V. Patterns

Benchmark
None

Key Terms

none

Indicators

  1. Apply recursion to mathematical models.
    1. Explore dynamical systems.
      1. Sandefur’s drug model
      2. interest problems using spreadsheets
      3. population model
    2. Explore fractals and chaos (optional).
      1. Julia set
      2. Mandelbrot set

  2. Apply scalar relationships to the determination of physical limits (optional).

  3. Address the recursive nature of tilings and tesselations (optional).

back to top


VI. Coding (optional)

Benchmark
None

Key Terms

none

Indicators

  1. Investigate coding schemes.
    1. ISBN (International Standard Book Number)
    2. ZIP codes
    3. bar codes
    4. Social Security and census codes

  2. Encode and decode information for transmission (cryptography).

Craig Herring, Mathematics Specialist
Craig.Herring@fcps.edu

Alan Leis Instructional Center
7423 Camp Alger Ave.
Falls Church, VA 22042
703-208-7738


Last Updated
9/9/2004

Contact
Yvonne Griggs
Yvonne.Griggs
@fcps.edu
Adult & Community Education Early Childhood & Family Services
Elementary School Instruction English for Speakers of Other Languages
High School Instruction & K-12 Curriculum Services Instructional Technology Services
Middle School Instruction Professional Technical Studies Staff Development