# '15 -'16 General Discussion for Optional 6.2 **URL:** \ **Category:** Unit and Lesson Discussion\ **Tags:** csp-unit-4\ **Created:** [October 6, 2016, 12:19am UTC](https://forum.code.org/t/15-16-general-discussion-for-optional-6-2/5712 "2016-10-06T00:19:32Z")\ **Posts on this page:** 18\ **Page:** 1
**Author:** ![brook](https://sea2.discourse-cdn.com/flex016/user_avatar/forum.code.org/brook/32/88_2.png) [@brook](https://forum.code.org/u/brook)\ **Post date:** [October 6, 2016, 12:19am UTC](https://forum.code.org/t/15-16-general-discussion-for-optional-6-2/5712/1 "2016-10-06T00:19:32Z")
A collection of posts from the '15 -'16 school year related to this lesson ---
**Author:** ![caroline](https://sea2.discourse-cdn.com/flex016/user_avatar/forum.code.org/caroline/32/196_2.png) [@caroline](https://forum.code.org/u/caroline)\ **Post date:** [January 6, 2016, 6:54pm UTC](https://forum.code.org/t/15-16-general-discussion-for-optional-6-2/5712/2 "2016-01-06T18:54:46Z")
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 ---
**Author:** ![gtwrobel](https://sea2.discourse-cdn.com/flex016/user_avatar/forum.code.org/gtwrobel/32/3576_2.png) [@gtwrobel](https://forum.code.org/u/gtwrobel)\ **Post date:** [January 7, 2016, 3:15pm UTC](https://forum.code.org/t/15-16-general-discussion-for-optional-6-2/5712/3 "2016-01-07T15:15:58Z")
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 ---
**Author:** ![vijayshree\_sundar](https://avatars.discourse-cdn.com/v4/letter/v/d6d6ee/32.png) [@vijayshree\_sundar](https://forum.code.org/u/vijayshree_sundar)\ **Post date:** [November 9, 2015, 3:01am UTC](https://forum.code.org/t/15-16-general-discussion-for-optional-6-2/5712/4 "2015-11-09T03:01:31Z")
You can use the video resource on You Tube ,the link is [https://www.youtube.com/watch?v=7B8Sx\_nAxLk](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](https://www.youtube.com/watch?v=GE3dsA5S7M8). ---
**Author:** ![brook](https://sea2.discourse-cdn.com/flex016/user_avatar/forum.code.org/brook/32/88_2.png) [@brook](https://forum.code.org/u/brook)\ **Post date:** [October 6, 2016, 12:23am UTC](https://forum.code.org/t/15-16-general-discussion-for-optional-6-2/5712/5 "2016-10-06T00:23:00Z")
---
**Author:** ![vijayshree\_sundar](https://avatars.discourse-cdn.com/v4/letter/v/d6d6ee/32.png) [@vijayshree\_sundar](https://forum.code.org/u/vijayshree_sundar)\ **Post date:** [November 9, 2015, 2:38am UTC](https://forum.code.org/t/15-16-general-discussion-for-optional-6-2/5712/6 "2015-11-09T02:38:37Z")
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](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. ---
**Author:** ![tschlotterback](https://avatars.discourse-cdn.com/v4/letter/t/54ee81/32.png) [@tschlotterback](https://forum.code.org/u/tschlotterback)\ **Post date:** [November 11, 2015, 5:51pm UTC](https://forum.code.org/t/15-16-general-discussion-for-optional-6-2/5712/7 "2015-11-11T17:51:06Z")
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. ---
**Author:** ![tschlotterback](https://avatars.discourse-cdn.com/v4/letter/t/54ee81/32.png) [@tschlotterback](https://forum.code.org/u/tschlotterback)\ **Post date:** [November 11, 2015, 5:52pm UTC](https://forum.code.org/t/15-16-general-discussion-for-optional-6-2/5712/8 "2015-11-11T17:52:48Z")
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](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. ---
**Author:** ![tschlotterback](https://avatars.discourse-cdn.com/v4/letter/t/54ee81/32.png) [@tschlotterback](https://forum.code.org/u/tschlotterback)\ **Post date:** [November 11, 2015, 5:56pm UTC](https://forum.code.org/t/15-16-general-discussion-for-optional-6-2/5712/9 "2015-11-11T17:56:38Z")
![](https://cdck-file-uploads-us1.s3.dualstack.us-west-2.amazonaws.com/flex016/uploads/codeorgforum/original/1X/9923262a8c31bc40733592367044179da86f5a4c.png) ---
**Author:** ![nwatts](https://avatars.discourse-cdn.com/v4/letter/n/7cd45c/32.png) [@nwatts](https://forum.code.org/u/nwatts)\ **Post date:** [December 29, 2015, 6:49pm UTC](https://forum.code.org/t/15-16-general-discussion-for-optional-6-2/5712/10 "2015-12-29T18:49:18Z")
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. ---
**Author:** ![nwatts](https://avatars.discourse-cdn.com/v4/letter/n/7cd45c/32.png) [@nwatts](https://forum.code.org/u/nwatts)\ **Post date:** [December 29, 2015, 6:53pm UTC](https://forum.code.org/t/15-16-general-discussion-for-optional-6-2/5712/11 "2015-12-29T18:53:52Z")
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 > **[Knapsack problem](https://en.wikipedia.org/wiki/Knapsack_problem)** > > The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items. The problem often arises in resource allocation... Example Worksheet > **[DynamicProgrammingWorksheet.pdf](https://web.cs.ship.edu/~tbriggs/dynamic/DynamicProgrammingWorksheet.pdf)** > > 101.94 KB Example Code [http://www.maplesoft.com/applications/view.aspx?SID=100353&view=html](http://www.maplesoft.com/applications/view.aspx?SID=100353&view=html) ---
**Author:** ![nwatts](https://avatars.discourse-cdn.com/v4/letter/n/7cd45c/32.png) [@nwatts](https://forum.code.org/u/nwatts)\ **Post date:** [December 29, 2015, 7:04pm UTC](https://forum.code.org/t/15-16-general-discussion-for-optional-6-2/5712/12 "2015-12-29T19:04:38Z")
Example hotspot graph and key ![](https://us1.discourse-cdn.com/flex016/uploads/codeorgforum/original/1X/3f54a5638bc85c1c2d80cddc560627d66f0be4ce.png) ![](https://us1.discourse-cdn.com/flex016/uploads/codeorgforum/original/1X/71916656a90b310254659c94ce73331f274f1c2a.png) ---
**Author:** ![heatherpe](https://avatars.discourse-cdn.com/v4/letter/h/e480ec/32.png) [@heatherpe](https://forum.code.org/u/heatherpe)\ **Post date:** [January 20, 2016, 4:50am UTC](https://forum.code.org/t/15-16-general-discussion-for-optional-6-2/5712/13 "2016-01-20T04:50:40Z")
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](http://www.hoodamath.com/games/thetravellingsalesman.html) ---
**Author:** ![baker](https://sea2.discourse-cdn.com/flex016/user_avatar/forum.code.org/baker/32/1229_2.png) [@baker](https://forum.code.org/u/baker)\ **Post date:** [January 20, 2016, 2:08pm UTC](https://forum.code.org/t/15-16-general-discussion-for-optional-6-2/5712/14 "2016-01-20T14:08:17Z")
Neat! Thanks for the link! ---
**Author:** ![katherine\_pomeroy](https://avatars.discourse-cdn.com/v4/letter/k/a8b319/32.png) [@katherine\_pomeroy](https://forum.code.org/u/katherine_pomeroy)\ **Post date:** [January 25, 2016, 8:47pm UTC](https://forum.code.org/t/15-16-general-discussion-for-optional-6-2/5712/15 "2016-01-25T20:47:05Z")
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 😄 ---
**Author:** ![kaitie\_obryan](https://sea2.discourse-cdn.com/flex016/user_avatar/forum.code.org/kaitie_obryan/32/1304_2.png) [@kaitie\_obryan](https://forum.code.org/u/kaitie_obryan)\ **Post date:** [March 3, 2016, 3:41am UTC](https://forum.code.org/t/15-16-general-discussion-for-optional-6-2/5712/16 "2016-03-03T03:41:38Z")
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. ---
**Author:** ![jdinh](https://avatars.discourse-cdn.com/v4/letter/j/71c47a/32.png) [@jdinh](https://forum.code.org/u/jdinh)\ **Post date:** [March 24, 2016, 8:19pm UTC](https://forum.code.org/t/15-16-general-discussion-for-optional-6-2/5712/17 "2016-03-24T20:19:03Z")
This is the best lesson in this unit. Students got the lesson and did it on their own. ---
**Author:** ![awade](https://avatars.discourse-cdn.com/v4/letter/a/f6c823/32.png) [@awade](https://forum.code.org/u/awade)\ **Post date:** [May 9, 2016, 1:25am UTC](https://forum.code.org/t/15-16-general-discussion-for-optional-6-2/5712/18 "2016-05-09T01:25:37Z")
I had my students use the following website as an extension activity where they can create their own wifi problems. [http://bit.ly/wifigraphs](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.