Algorithm Discovery with Venn Diagrams

Lesson Outline

Focus and Review

Remind students what has been learned in previous lessons that will be pertinent to this lesson and/or have them begin to think about the words and ideas of this lesson:

• Start by asking students, "What are some geometric shapes that we know?" Draw pictures of circles, squares, and so on.
• Prompt students with the question, "We often want to classify objects like the collection of things we have on the board into different sets. Can anyone tell me what a Venn diagram is?" Have students think of examples of Venn diagrams describing geometric objects. The Venn diagrams may be for disjoint sets (for example, polygons and non-polygons) or for intersecting sets (for example, regular polygons and quadrilaterals).

Objectives

Let the students know what they will be doing and learning today. Say something like this:

• Today, class, we are going to practice using Venn diagrams, but in the process, we will learn about the efficiency of different methods for solving problems.
• We are going to use the computers to do this but please do not turn your computers on until I ask you to. I want to show you a little about this activity first.

Teacher Input

Lead the students in a short discussion about algorithms.

Explain to the students how the applet works if they are not familiar with how to use our computer applets.

• Open your browser to Venn Diagram Shape Sorter in order to demonstrate this activity to the students.
• Begin to explain the applet to the students by showing the different versions (intersecting circles, one circle, and so on) and kinds of rules (for example, big, triangle) for the Venn diagram.
• Choose two rules with settings of "Make a rule" and intersecting circles. Show the students how to move objects into the circles by letting them choose objects and telling you where to put them. This will also reinforce the concept of Venn diagrams. Show them that "outside both of the circles" is where to put objects that do not satisfy either rule.
• Point out there are at least two algorithms they could be using:
  • Try each object in the first row (small circles) in each area of the Venn diagram to see where it goes. Now start on the second row (big circles). In this case, you don't miss anything but it is very slow. (This is known as "brute force" or "exhaustive search.")
  • Think about which objects satisfy the rule and where they go before you try to move them. In this case, you have to think more, but move less.

Guided Practice

Tell the students that today they will be letting the computer choose the rule and trying to guess what rule the computer is using. They will be trying to find at least some of the steps in an algorithm for guessing the rule as quickly as possible.

Show how to use the applet with the setting "Guess the Rule".

• Using the one-circle version, let the students choose objects to try.
• After 4 to 8 objects have been tried, ask students if they want to guess what the rule is. Let them guess the rule.
• Show the students the location of the "Check Answer" button. Check whether their guess is correct.
• Ask the students some algorithms they could use in finding out what the rule is. Some examples would be "Try objects randomly," "Try rules randomly and check the results." and "Get all the triangles in the right place on the Venn diagram, then try other shapes."
• If necessary, do an example together with 2 circles.
• Pass out the Shape Sort Golf Scorecard and the Shape Sort Algorithm Worksheet.

Independent Practice

• Allow the students to play the game and complete the worksheet. They should work in pairs or small groups so one person can keep score while another is playing.
• Monitor the room for questions and to be sure the students are on the correct website.
• Students may need help with some of the later questions. Encourage them to think about what information they have at any point and what additional information they need to determine which rule the computer is using.

Guided Practice 2

Tell the students to close their computers for a while. Ask them to compare their scores and their methods for choosing what to try next. Show the students how to use Box Plot to compare the games of two players.

• If you have not previously opened a browser with Box Plot, open one now.
• If you have not previously entered scores into the Box Plot applet, change the menu options to "My Data" and enter scores from two volunteers. Change the setting to "Graph, by Category."
• Press the "Update Boxplot" button.
• Lead the students in discussing what the box plots mean -- for example, more spread out means less consistent, box further to left means better scores.

Independent Practice 2

• Tell the students they will now be comparing algorithms. You might want to lead a quick discussion about good algorithms.
• Tell the students to choose one version of the game (one circle, two circles, etc.) and write down at least two algorithms for guessing what rule the computer is using. One of the algorithms can be random guessing. The students should play at least 5 rounds with each of their methods (algorithms) and make box plots showing the results for each algorithm.
• Allow the students to work in pairs or small groups. Again monitor the room for questions and to be sure that the students are on the correct web sites.

Closure

• Ask the students to close their computers.
• Bring the class back together for a discussion of the findings. Once the students have been allowed to share what they found, summarize the results of the lesson.
• Point out that if the students were trying to program one computer to find out what rule another was using, they would need to have an algorithm. Their worksheet answers give rules they could use as some of the steps in such an algorithm.