|
+ or - |
STANDARD 4.4
(DATA ANALYSIS, PROBABILITY, AND DISCRETE MATHEMATICS) ALL
STUDENTS WILL DEVELOP AN UNDERSTANDING OF THE CONCEPTS AND TECHNIQUES OF
DATA ANALYSIS, PROBABILITY, AND DISCRETE MATHEMATICS, AND WILL USE THEM
TO MODEL SITUATIONS, SOLVE PROBLEMS, AND ANALYZE AND DRAW APPROPRIATE
INFERENCES FROM DATA. |
| |
D.
Discrete Mathematics—Vertex-Edge Graphs and Algorithms |
| |
By the end of Grade
2, students will: |
| |
1.
Follow
simple sets of directions (e.g., from one location to another, or from a
recipe). |
| |
2.
Color simple
maps with a small number of colors. |
| |
3.
Play simple
two-person games (e.g., tic-tac-toe) and informally explore the idea of
what the outcome should be. |
| |
4.
Explore
concrete models of vertex-edge graphs (e.g.
vertices as “islands” and edges as “bridges”).
·
Paths from
one vertex to another |
| |
Building upon knowledge and
skills gained in preceding grades, by the end of Grade 3, students will: |
| |
1.
Follow, devise, and describe practical sets of directions
(e.g., to add two 2-digit numbers). |
| |
2.
Explore vertex-edge graphs
·
Vertex, edge
·
Path |
| |
3.
Find the
smallest number of colors needed to color a map. |
| |
Building upon knowledge and
skills gained in preceding grades, by the end of Grade 4, students will: |
| |
1.
Follow,
devise, and describe practical sets of directions (e.g., to add two
2-digit numbers). |
| |
2.
Play
two-person games and devise strategies for winning the games (e.g.,
“make 5" where players alternately add 1 or 2 and the person who reaches
5, or another designated number, is the winner). |
| |
3.
Explore
vertex-edge graphs and tree diagrams.
·
Vertex,
edge, neighboring/adjacent, number of neighbors
·
Path,
circuit (i.e., path that ends at its starting point) |
| |
4.
Find the
smallest number of colors needed to color a map or a graph. |
| |
Building upon knowledge and
skills gained in preceding grades, by the end of Grade 5, students will: |
| |
1.
Devise
strategies for winning simple games (e.g., start with two piles of
objects, each of two players in turn removes any number of objects from
a single pile, and the person to take the last group of objects wins)
and express those strategies as sets of directions. |
| |
Building upon knowledge and
skills gained in preceding grades, by the end of Grade 6, students will: |
| |
1.
Devise
strategies for winning simple games (e.g., start with two piles of
objects, each of two players in turn removes any number of objects from
a single pile, and the person to take the last group of objects wins)
and express those strategies as sets of directions. |
| |
2.
Analyze vertex-edge graphs and tree diagrams.
·
Can a picture or a vertex-edge graph be drawn with a
single line? (degree of vertex)
·
Can you get from any vertex to
any other vertex? (connectedness) |
| |
3.
Use
vertex-edge graphs to find solutions to practical problems.
·
Delivery
route that stops at specified sites but involves least travel
·
Shortest
route from one site on a map to another |
| |
Building upon knowledge and
skills gained in preceding grades, by the end of Grade 7, students will: |
| |
1.
Use vertex-edge graphs to represent and find solutions to
practical problems.
·
Finding the shortest network connecting specified sites
·
Finding the shortest route on a map from one site to
another
·
Finding the shortest circuit on a map that makes a tour of
specified sites |
| |
Building upon knowledge and
skills gained in preceding grades, by the end of Grade 8, students will: |
| |
1.
Use vertex-edge graphs and algorithmic thinking to
represent and find solutions to practical problems.
·
Finding the shortest network connecting specified sites
·
Finding a minimal route that includes every street (e.g.,
for trash pick-up)
·
Finding the shortest route on a map from one site to
another
·
Finding the shortest circuit on a map that makes a tour of
specified sites
·
Limitations of computers (e.g., the number of routes for a
delivery truck visiting n sites is n!, so finding the
shortest circuit by examining all circuits would overwhelm the capacity
of any computer, now or in the future, even if n is less than 100) |
| |
Building upon
knowledge and skills gained in preceding grades, by the end of Grade 12,
students will: |
| |
1.
Use vertex-edge graphs and algorithmic thinking to
represent and solve practical problems.
·
Circuits that include every edge in a graph
·
Circuits that include every vertex in a graph
·
Scheduling problems (e.g., when project meetings should be
scheduled to avoid conflicts) using graph coloring
·
Applications to science (e.g., who-eats-whom graphs,
genetic trees, molecular structures) |
| |
2.
Explore strategies for making fair decisions.
·
Combining individual preferences into a group decision
(e.g., determining winner of an election or selection process)
·
Determining how many Student Council representatives each
class (9th, 10th, 11th, and 12th
grade) gets when the classes have unequal sizes (apportionment) |