Algorithm Discovery with Venn Diagrams

Abstract

This lesson is designed to enhance students' ability to analyze problems and create solutions, while reinforcing their understanding of sets, Venn diagrams, and box plots.

Objectives

Upon completion of this lesson, students will:

  • have practiced developing their own algorithms from a problem-solving process
  • have used box plots to analyze data from the activity
  • have practiced determining the placement of an element in a Venn diagram
  • have practiced sorting objects

Standards

The activities and discussions in this lesson address the following NCTM standards:

Geometry and Measurement

Analyze characteristics and properties of two- and three-dimensional geometric shapes and develop mathematical arguments about geometric relationships

  • precisely describe, classify, and understand relationships among types of two- and three-dimensional objects using their defining properties

Data Analysis and Probability

Formulate questions that can be addressed with data and collect, organize, and display relevant data to answer them

  • select, create, and use appropriate graphical representations of data, including histograms, box plots, and scatterplots

Select and use appropriate statistical methods to analyze data
  • discuss and understand the correspondence between data sets and their graphical representations, especially histograms, stem-and-leaf plots, box plots, and scatterplots

Links to other standards.

Student Prerequisites

  • Geometry: Students must be able to:
    • name basic two-dimensional objects
  • Data Analysis: Students should know:
    • what the components of a Venn diagram and of a box plot represent
  • Technological: Students must be able to:
    • perform basic mouse manipulations such as point, click and drag
    • use a browser such as Netscape for experimenting with the activities

Teacher Preparation

Teachers may want to set up their computers with two copies of a browser open:

  • The first copy of the browser would be opened to the site where the class generally starts or to Venn Diagram Shape Sorter.
  • The second copy of the browser would be opened to Box Plot 1 or Box Plot 2 (depending on whether or not you use the median in computing the interquartile range).
    • Change the menu options to "My Data" and "Graph, by Category."
    • Enter an appropriate title for the plots.
    • Enter scores for 2 fictitious students. The format is "Score, student". A good example to use is that Student A scored 10, 15, 18, 21, while Student B scored 15, 19, 21, 22. (So B is more consistent but does worse when the objective is to have a low score).

Students will need:

Key Terms

This lesson introduces students to the following terms through the included discussions:

Lesson Outline

  1. 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).

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. Guided Practice

    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 1 or Box Plot 2 (depending on which Box Plot used), 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.

  7. Independent Practice

    • 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.

  8. 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.

Alternate Outlines

This lesson can be rearranged in several ways.

  • Instead of talking about algorithms, you may want to spend more time on Venn diagrams. Sets and Venn Diagrams is more of an introduction to Venn diagrams.
  • In a workshop, you can combine introductions and the review of Venn diagrams by asking students where their name goes in a Venn diagram with circles labeled "begins with A-L," "begins with M-Z," and "has at most 5 letters."
  • Have the students cooperate on the golf game instead of competing.
  • The material on comparing algorithms can be skipped.
  • If only one computer is available for the classroom:
    • The teacher may do this activity as a demonstration. Choose the version (one circle, etc.) and allow students to decide individually, or in groups, which object to move onto the diagram and where to move it.
    • Groups may take turns completing the patterns with the Pattern Generator applet for 10 minutes each.
    • In either case, students should complete the worksheet.

Suggested Follow-Up