Overview and Background

Students get an introduction to graphs using the Kevin Bacon Game. Then they will learn some vocabulary terms, including Hamiltonian circuit. Students use 123D Design to create graphs. This will lead to an introduction to The Traveling Salesman Problem. From there they will look at the efficiency of algorithms and P vs NP.

Objectives:
Students will learn the definitions and get practice for the following terms: Graphs, Hamiltonian circuit, The Traveling Salesman Problem, and algorithm efficiency.

Skills Learned (Standards):
Students learn what a graph is, how to recognize and create a Hamiltonian circuit, how to solve The Traveling Salesman Problem, and get an introduction to algorithm efficiency.

Lesson Plan and Activity

Further detail is provided in the student and teacher worksheets.
To introduce what graphs are go to https://oracleofbacon.org. Ask students to give you actor names to get a few connections and start drawing a graph on the board. Make the actors vertices and movies they were in together edges. Then explain that graphs are made up of edges (lines) and vertices (dots).
Show a clip from Good Will Hunting that has an example of a graph: https://www.youtube.com/watch?v=Bylkoiyz7Ww
Define a walk, a circuit, and a Hamiltonian circuit.
In groups students create a graph with a Hamiltonian circuit using 123D Design and measure the length of each edge. Then they trade with another group to locate the circuit.
Introduce the Traveling Salesman Problem and students us their graph to go through an example.
Students think about how many possibilities they have to check for a route with n cities.
Show a factorial, exponential, and polynomial graphed on the same set of axes to show that the polynomial function grows much slower than the other two.
Go through an example that is solved in polynomial time.
Explain P vs NP
Show clips from Elementary that go into P vs NP in further detail.

Duration of Lesson

1-2 days

Preparation

No specific background knowledge is needed.

Rubric and Assessment

Here is a sample rubric to use with the worksheet:

Question (points)
1 (2)
2 (6)
3 (4)
4 (2)
5 (8)
6 (1)
7 (2)

Total (25)

References

All the definitions and background you need is included in this activity.

Graphs, The Traveling Salesman Problem, and P vs NP