A collection of posts from the '15 -'16 school year related to this lesson
In class today a student asked why can’t we make an easy to solve TSP? The idea was to create a set of points, then assign the weights of the edges in a way that you know what the TSP solution is. Then put in higher weights on the other edges so that you know your solution is the best solution.
Would that work? If not how do I explain why?
Thanks
Hey Caroline,
It’s exciting to hear your students are asking such great questions. A short answer to your question is “yes” if someone naively approached your graph they would need to try all possible paths while you would immediately know the correct answer. Unfortunately this doesn’t make for a very secure protocol since as students learned from the lesson on the Vigenere Cipher, typically the methods (though not the specific keys) used for encryption are known publicly. In the case you’re describing someone cracking your encryption would know to just sort the edge weights from smallest to largest and then pick the smallest edges in order to form the shortest cycle. In fact you would know with certainty this is the shortest cycle since there would be no shorter set of edges you could have used.
Your next instinct might be to slightly obscure the shortest path by adding a few edges shorter than the ones used in your cycle. Unfortunately now you’re probably not sure that you have the shortest cycle anymore and would need to check with, you guessed it, a brute force search.
Let me know if you want to talk more, thanks for sharing this great question, and I hope things are going well.
GT
You can use the video resource on You Tube ,the link is https://www.youtube.com/watch?v=7B8Sx_nAxLk to show what the travelling salesman problem is and explain how it is not a one way function.
Here is a video link for one way function, https://www.youtube.com/watch?v=GE3dsA5S7M8.
Notes: I would recommend that you should take at least two days to complete this lesson. The students need to understand that there do exist problems that even computers cannot solve. Some problems require brute force for finding the solution. Try to explain this lesson using the travelling salesman problem.You can use the video resource on You Tube ,the link is https://www.youtube.com/watch?v=7B8Sx_nAxLk. Then begin by drawing three nodes and showing the connections, then increasing the nodes and determining the number of routes. Once the students understand the concept, you can introduce the problem for determining the number of hotspots required for connecting a small town to the Internet. After the students have determined the number of hotspots for the town, ask them to design their own hotspot problem. The students will have fun sharing their problem sheets with the other groups in the class.
1 Like
Notes: Make sure that students understand the vocabulary presented in this lesson and lesson 16. Heuristics and brute force are both concepts that students will need to understand before undertaking this lesson. I can see some of my students becoming frustrated with the assignment when they need to figure out someone else’s hotspot graph. I may need to modify this by limiting the number of spots each graph can contain. This way students will still work through the concepts. I may even have students just go to the make your own graphs extended learning already listed and try to crack the functions there first.
Extension Lesson: Students can practice creating a one-way function by reading the non-mathematical explanation at http://blog.jgc.org/2013/04/a-non-mathematical-explanation-of-one.html then trying to create a key using a dictionary. Working in pairs, students can then try to “break” the functions by working backwards.
Some students will not intuitively be able to create their own graph, even with the worksheet and a verbal explanation. You should model how to make a graph and be sure to point out how to add other spots and connect them so that the key is difficult to solve. Also, they forget to save a copy of the key before making all the spots the same.
Also, I had several students come up with different solutions to the subset sum problem.
Another brute force problem that can related to cryptography is the Knapsack problem. It is fun to consider and is solved using dynamic programming.
Internet resources for the Knapsack problem:
Explanation
Example Worksheet
Example Code
http://www.maplesoft.com/applications/view.aspx?SID=100353&view=html
Thanks for sharing the Travelling Salesman youtube link! I found this Travelling Salesman Game online that is kind of fun & got my kids really into that problem. The link is http://www.hoodamath.com/games/thetravellingsalesman.html
1 Like
Neat! Thanks for the link!
My students needed a lot of repetition about what a one-way function was, and what it meant to be a one-way function. Most of them initially thought the traveling salesperson was a one-way function because the salesperson only went one-way around his route to do his sales 
I think scaffolding this with students to create a 5 hot-spot solution problem, and then a 6 hot-spot solution problem, etc. would be helpful. My students tried to make really hard ones but the way they connected them almost made it easier for students to see the original hotspots. This demonstrated why the heuristic can be a good strategy. However, if students got multiple attempts, I think their self-designed problems would have been more challenging to their peers.
This is the best lesson in this unit. Students got the lesson and did it on their own.
I had my students use the following website as an extension activity where they can create their own wifi problems.
http://bit.ly/wifigraphs
The students use this graphing websites and it makes it easier to plot the edges and the nodes and join them. The students had fun sharing their own problems for other students to solve.
1 Like