Checkpoint - Course 2, Unit 5
Network Optimization

In each unit, there is a final lesson and Checkpoint that helps students summarize the key ideas in the unit. The final Checkpoint will generally be discussed in class, with the teacher facilitating the summarizing, and students making notes in their Math Toolkits (teachers may just refer to this as "notes") of any points they need to remember, adding illustrative examples as needed. If your student is having difficulty with any investigation in this unit, this Checkpoint and the accompanying answers may help you recall the concepts involved, and give you the big picture of what the entire unit is about. If your student has completed the unit, then a version of this should be in his or her notes or toolkit. Students should also have Technology Tips in their toolkits, which may be useful for this unit.

Possible Responses to Unit Summary Checkpoint
In this unit, students studied important concepts and methods related to network optimization. The bolded words are vocabulary and concepts your student should be familiar with.
a. Compare your concept map from Task 3 [Looking Back lesson in student text] with those of other students. Discuss similarities and differences.
Different students will make different connections among the ideas studied in this unit. Shown below is a map that shows major ideas.
b. Optimization or "finding the best" is an important theme throughout this unit. Describe three problem situations from the unit in which you "found the best." In each case, explain how you used a graph model to solve the problem.
Students investigated many different problems in class. For example:

Best Graph Model Type
Cheapest airfare Shortest path
Least amount of wire Minimal spanning tree
Shortest route between two cities Shortest path
Shortest circuit through a network of cities Traveling Salesperson Problem or minimal Hamiltonian circuit
Phone network Minimal spanning tree
Detecting clustering Minimal spanning tree
Traveler's Dodecahedron Hamiltonian circuit
c. Describe one similarity between minimal spanning trees and shortest paths. Describe one difference.
Minimal spanning trees and shortest paths are both the "shortest" in some sense, which could mean cheapest, or least in some way. But a minimal spanning tree is a shortest tree that includes all vertices as opposed to a shortest path that generally does not include all vertices.
d. Describe one similarity between minimal spanning trees and the Traveling Salesperson Problem. Describe one difference.
In both minimal spanning tree problems and the Traveling Salesperson Problem, you are looking for something that is minimal and spanning (includes all vertices). In one case, you want a minimal spanning tree, and in the other, you want a minimal spanning circuit (starts and ends at the same vertex).
e. Describe one similarity between the Traveling Salesperson Problem and shortest path problems. Describe one difference.
In both the Traveling Salesperson Problem and shortest path problems, you are looking for the "shortest," but in one case, it is a shortest circuit that includes all vertices, and in the other it is the shortest path (begins and ends at different vertices) that generally does not include all the vertices.
f. In this unit, you have explored a variety of algorithms and methods for solving network optimization problems, including best-edge algorithms and brute force methods. For each of these two solution procedures, do the following.
  • Describe the basic strategy.
    The best-edge algorithm starts with the shortest edge and adds the best possible edge at each step. The brute force method finds all possible networks, checks them all, and chooses the best.
  • Give some examples of problems that can be solved using the procedure.
    The best-edge algorithm will find a minimal spanning tree. It will not solve the Traveling Salesperson Problem. It was not discussed for shortest path problems. The brute force method will work for any finite problem, but is not practical for problems that have more than a few vertices and edges.
  • List some advantages and disadvantages of the procedure.
    The best-edge algorithm is easy to understand and apply; it will find minimal spanning trees, and is efficient. However, it does not solve the Traveling Salesperson Problem. The brute force method is also easy to understand, but it can be difficult to keep track of all possibilities and also time consuming, so not practical.

If you would like to see specific problems from Course 2, Unit 5, a link is provided to Examples of Tasks from Course 2, Unit 5. If you are interested in following up on the Discrete Mathematics strand in general, then the Scope and Sequence will help you see where different concepts are introduced. On the Discrete Mathematics page, you can read an explanation of the main discrete mathematics concepts as they are developed in all four courses.

Copyright 2008 Core-Plus Mathematics Project. All rights reserved.