Graphs, The Traveling Salesman Problem, and P vs NP

thingiverse

This activity is for a computer science class or a discrete math class when students first learn about graphs and efficiency of algorithms. This could also be used as an enrichment activity for high school students since it is self-contained with all definitions given and there isn’t any specific background knowledge needed. Print Settings Printer Brand: MakerBot Printer: MakerBot Replicator Rafts: Yes Supports: Yes Resolution: standard Infill: 10% How I Designed This I used 123D Design to create a graph using circles and polyline for lines. I used the measure tool to get all the lengths. If you want students to be able to print their graphs you will need to use an object instead of just a line to be able to extrude the graph. I used polyline to create rectangles. My graph only took 6 minutes to print, but it is fragile. You could scale it up. I chose not to so that it would print with the same dimensions I measured for the project. 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=Bylkoiyz7WwDefine 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 NPShow 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.