Unit 2:   Introduction to Data Structures

imageUnit 2Introduction to Data Structures
Unit Overview

Students discover the need for data structures and they practice defining them.

Product Outcomes:
  • Students identify real-world behaviors that require data structures

  • Students make use of a complex data structure: Cake

  • Students define variables bound to Cakes

  • Students will generalize their understanding of function constructors and accessors

  • Students write code that extracts each field from those Cakes

Standards and Evidence Statements:

Standards with prefix BS are specific to Bootstrap; others are from the Common Core. Mouse over each standard to see its corresponding evidence statements. Our Standards Document shows which units cover each standard.

    Length: 90 minutes
    Glossary:
    • calling: Using a function by giving it inputs

    • data structure: A group of values that can be returned as a single datatype

    • domain: the type of data that a function expects

    • dot-accessors: A way to extract values from a data structure

    • instances: Specific values of data

    • name: how we refer to a function or value defined in a language (examples: +, *, star, circle)

    • purpose statement: a brief description of what a function does

    • range: the type of data that a function produces

    • variable: something that changes

    Materials:
    • Pens/pencils for students, fresh whiteboard markers for teachers

    • Class poster (List of rules, language table, course calendar)

    • Language Table (see below)

    • Student Workbook folders with names on covers, and something to write with

    Preparation:
    • Write Agenda on board

    • Display class posters, Language Table, Design Recipe

    • Seating arrangements: ideally clusters of desks/tables

    • The Parachute Jumper file preloaded on student machines

    • The Bakery file preloaded on students’ machines

    Types

    Functions

    Number

    + - * / num-sqr num-sqrt

    String

    string-append string-length

    Image

    rectangle circle triangle ellipse star text


    Review

    Overview

    Learning Objectives

    • Students will deepen their understanding of function definitions and the Design Recipe

    Evidence Statements

    Product Outcomes

    Materials

    • Pens/pencils for students, fresh whiteboard markers for teachers

    • Class poster (List of rules, language table, course calendar)

    • Language Table (see below)

    • Student Workbook folders with names on covers, and something to write with

    Preparation

    • Write Agenda on board

    • Display class posters, Language Table, Design Recipe

    • Seating arrangements: ideally clusters of desks/tables

    Review (Time 15 minutes)

    • In the previous unit, you reviewed almost everything from Bootstrap:1 including Datatypes, Contracts, and the Design Recipe. In this unit you will go above and beyond all that, and learn an entirely new datatype that will be the basis for everything you’ll do in Bootstrap:2.

      Ask a few introductory review questions to test students’ understanding:

      • What are the three parts of a Contract?

      • What is the Pyret code to draw a solid, green triangle of size 22?

      • Why is it important to write at least 2 examples before defining a function?

    • To make sure the material from the previous unit is fresh in your mind, tackle the following activity:

      Turn to Page 8 in your workbook. Write a function called double-radius, which takes in a radius and a color. It produces an outlined circle of whatever color was passed in, whose radius is twice as big as the input.

      If walking through this example as a class, use a projector so kids can see the function being written on the computer.

    • Remember how to use the design recipe to work through word problems?
      • What is the Name of this function? How do you know?

      • How many inputs does it have in its Domain?

      • What kind of data is the Domain?

      • What is the Range of this function?

      • What does this function do? Write a Purpose Statement describing what the function does in plain English.

       

      Review the purpose of Contracts: once we know the Name, Domain, and Range of a function, it’s easy to write examples using those datatypes.

    • Using only the Contract and Purpose Statement, see if you can answer the following questions:

      • Every example begins with the name of the function. Where could you find the name of the function?

      • Every example has to include sample inputs. Where could you find out how many inputs this function needs, and what type(s) they are?

      • Every example has to include an expression for what the function should do when given an input. Where could you look to find out what this function does?

      • Write two examples on your paper, then circle and label what is changing between them. When labeling, think about what the changing things represent.

      Don’t forget to include the lines examples: and end! Your examples should look similar to:  

      Each one of these answers can be found in the Contract or Purpose Statement. Suggestion: Write these steps on the board, and draw arrows between them to highlight the process. The goal here is to get students into the habit of asking themselves these questions each time they write examples, and then using their own work from the previous step to find the answers.

    • Once you know what is changing between our two examples, you can define the function easily. The things that were circled and labeled in the examples will be replaced with variables in the function definition.

      Underneath your examples, copy everything that doesn’t change, and replace the changing things with the variable names you used. (Don’t forget to add the fun and end keywords, as well as the colon (:) after the function header!)

       

      For more practice, turn to Page 9 in your workbook and complete the Design Recipe for the double-width function.

      Check students understanding: Why do we use variables in place of specific values? Why is it important to have descriptive variable names, as opposed to n or x? Remind students about nested functions: A function whose range is a number can be used inside of a function requiring a number in its domain, as in circle(2 * 25, "solid", "red").

    Introducing Structures

    Overview

    Learning Objectives

    • Students will understand the limitations of atomic datatypes

    Evidence Statements

    Product Outcomes

    • Students identify real-world behaviors that require data structures

    Materials

    Preparation

    Introducing Structures (Time 30 minutes)

    • Open this link on your computer and press ’Run’. What happens?

      The parachute jumper jumps out of the airplane and falls straight down, into the water! It’s much safer to land on the shore. Let’s take a look at the code to see why he falls into the water instead.

      Look at the function defined here called next-position.

      • What is this function’s Domain? Its Range?

      • What does next-position do with its inputs?

      This function takes in two numbers, representing the x and y coordinate of the jumper, but it only changes and returns the y-coordinate, by subtracting 5 from it. But if only the y-coordinate is changing, he’ll always fall straight down, landing in the water every time. To reach the land, he’ll have to fall diagonally. How could we make that happen?

      How should the jumper’s x-coordinate change if he moves diagonally to the right (toward the land)? How should his y-coordinate change?

    • Functions can only return one thing at a time, but we need to return both an x and a y-coordinate in order to make the jumper move diagonally. Thankfully, we have a way to combine multiple things within one container, called a Data Structure.

      For this activity we’ll be working with a data structure called a Coord, which contains just two Numbers, representing an x and a y-coordinate. You make Coords using a function called coord.

       

      Point out the difference in capitalization: Coord (capital C) is the name of the data structure, while coord (lowercase c) is the name of the function that creates a Coord. Make sure students understand the difference, because this is a required distinction between the structure name (capitalized) and constructor function (always lowercase).

    • Now it’s up to us to protect the parachute jumper, and make sure he lands safely on the shore.

      Turn to Page 10 in your workbook, read the word problem, and fill in the Contract and Purpose Statement for the function next-position.

       

      Now for our two examples. Using, or calling next-position with two numbers is easy, but what happens to those numbers? We can’t return both at the same time... unless we use a data structure! To do so we’ll need to use the constructor function to make a structure from data we already have.
      • According to the definition for Coord, what function makes a Coord?

      • coord(.....)

      • What two things are part of a Coord? Do we have values for those things as part of our first example?

      • We don’t want our Coord to contain the same x and y values we gave the next-position function. How will the values change? (Remember to show your work!)

      • Your first example should look something like:  

      • Once your first example is complete, write one more example with different inputs for the x and y coordinates.

      Remind students to show every step of their work in the example step of the design recipe: if the x-coordinate increases by 5 while the y-coordinate decreases by 5, they should show the addition and subtraction within the Coord data structure, instead of just returning the new numbers.

    • Now that you have two examples, it’s time to define the function. You know the drill: circle and label everything that changes between your two examples, copy everything that stays the same, and replace the changing things with the variables you chose.

      When you finish, your function definition should look like:   Now, instead of just changing and returning one number (a y-coordinate), we can return both the x and y-coordinates of the parachute jumper within a Data Structure.

      Open the Parachute Jumper code again and replace the original next-position function with the one in your workbook to make the jumper land safely on the shore!

    • In Bootstrap:1, you could only have a function return one thing: either a Number, String, Image, or Boolean. In Bootstrap:2, our functions will still return one thing, but that thing can be a Data Structure, (or just "structure" for short) containing any number of things within it. This way we could return both the x and y-coordinate of a player using a Coord, or create new structures and return even more detail about a player, like their health, position, amount of armor, or inventory.

      In Bootstrap:1, students’ games were made by keeping track of only a few numbers: the x-positions of the danger and target, and y-position of the player. In Bootstrap:2, students’ games will be much more complex, and will require many more values to move characters, test conditions, keep track of the score, etc. Data structures simplify code by organizing multiple values: You couldn’t represent every part of a player (position, health, inventory, etc.) with one number or string, but you can refer to all these things collectively with a data structure. This way, we can have one value (a data structure) containing multiple other values for easy access.

    Cakes

    Overview

    Learning Objectives

    Evidence Statements

    Product Outcomes

    • Students make use of a complex data structure: Cake

    • Students define variables bound to Cakes

    • Students will generalize their understanding of function constructors and accessors

    Materials

    Preparation

    • The Bakery file preloaded on students’ machines

    Cakes (Time 30 minutes)

    • Suppose you own a famous bakery. You bake things like cookies, pastries, and tarts, but you’re especially known for your world-famous cakes. What type of thing is a cake? Is it a number? String? Image? Boolean? You couldn’t describe all of the important things about a cake with any one of those data types. However, we could say that we care about a couple of details about each cake, each of which can be described with the types we already know.

      For each of the following aspects of a cake, think about what datatype you might use to represent it:

      • The flavor of the cake. That could be "Chocolate", "Strawberry", "Red Velvet", or something else.

      • The color of the cake

      • The message on top of the cake

      • The number of layers

      • Whether or not the cake is an ice cream cake.

      What datatype could we use to represent the entire cake?

      image Now that we know everything that is part of a Cake, we can use a data structure to represent the Cake itself. Let’s take a look at how this works.

      Open your workbook to Page 11.

      At the top of this page we see a comment, stating what things are part of a Cake. Below that is a line that says data Cake:, which begins the definition of a new data structure, called Cake. On the next line, we define the function that makes a Cake (cake), and how exactly to make a Cake - the names of each thing in a Cake structure, and their data types.

      What is the first part of a Cake structure? What data type can we use to represent it?

      There is a little bit of new syntax involved in defining structures. On the first line on Page 11, we want to write flavor :: String,, which tells Pyret that the first element of any Cake will be its flavor, represented by a String.

      What is the second part of a Cake structure? What data type can we use to represent it?

      On the next line, write color :: String, which tells Pyret that the second element of any Cake will be its color, represented by a String.

      List each of the other fields of a cake (message, layers, and is-ice-cream), and note what data types will represent them. Don’t forget commas to separate each field!

      On your paper, you should have:   This is the code that defines the Cake data structure. It tells the computer what a Cake is and what goes into it. It also defines its constructor function, called cake. To make a Cake, you must call the constructor function with five things: a flavor, which is a String, color, a String, messgae, another String, layers, a Number, and is-iceCream, which is a Boolean. Remember that order matters! For now, these are the only things that we’re going to keep track of in a cake, but you can imagine how you might extend it to include other information.

      Stress the importance of being able to define your own datatypes to students: no longer are they bound by the single values of numbers, strings, or booleans! Pyret allows you to define brand new Data Structures, containing any combination of values.

    • Open the Bakery file and look at lines 3 - 10. Do they match what you have on your paper?

      Now take a look farther down, at line 12: cake2 = cake("Chocolate", "brown", "Happy birthday!", 8, false)

      • What is the name of this variable?

      • What is the flavor of cake2?

      • What is the color of cake2?

      • What is the message on cake2?

      • How many layers does cake2 have?

      • Finally, is cake2 an ice cream cake, or not?

      Below the data definition for Cake there are four Cakes defined and assigned to the variables cake1, cake2, cake3, and cake4. Ask students questions about these Cakes to get them thinking about how they would define their own.

    • Define another Cake, called cake5. To start,

      • how would you define this variable?

      • What function is used to make a Cake?

      • Which thing comes first in a Cake structure?

      Now what do you expect to happen when you type cake5 into the interactions area? Click ’Run’ and try it out.

      cake5 = cake("Peanut Butter", "brown", "Congratulations!", 2, true)

      Have students walk you through the process of defining a variable called cake5 and making a Cake with whatever flavor, color, message, etc. they like.

    • Define two new variables for some of your favorite Cakes. You can call them cake6 and cake7, or whatever names you prefer. You can make any kind of Cakes that you want, as long as your structure has the right types in the right orders!

      Repetition is key in this lesson. Have students identify each part of the Cake struct for every Cake they’ve defined. What is the flavor of their first Cake? Its messagee? Ensure that students are using their inputs in the right order!

    • At this point, you’ve worked with two different Data Structures: Coords and Cakes, and you’ve created different examples, or instances, of these structures. Throughout this course you’ll create many more instances of structures than you will define whole new structures. For now, the important point is to recognize the difference between a structure definition (the data.... piece of code) and specific instances of a data structure (like cake1, or coord(44, 75).

    • Based on these instances of Cakes you just wrote:
      • What is the name of the function that creates a Cake?

      • What is the Domain of this function?

      • How many things are in the domain?

      The five things in the domain of cake are, in fact, the five things that we have already listed on Page 11! With data structures, the order is very important: we always want the first string in cake to be the Cake’s flavor, the first number to be its number of layers, etc.

      Cakes are the first example of defining a new datatype that students will see, but Pyret allows you to define any number of new data structures to hold any combination of values. The important points to remember about structures is that whenever the constructor function is called (in this case, cake), it must take in the same number and type of values as in the structure’s definition, and its inputs must be in the same order as the definition. Unit Three introduces students to even more data structures, and in Unit Four they begin defining their own.

    • After clicking the "Run" button, in Pyret, type cake1 into the interactions area and hit enter. What do you get back?

      Does this make sense? What happens when you type just a number into the interactions area? We get that same number back! What about Strings? Images? Booleans? If we don’t do anything to our input, or use any function on it, we get back exactly what we put in! Here, you put in a Cake, and got back that Cake!

      Remind students that values will always evaluate to themselves. 4 evaluates to 4, the string "pizza" evaluates to "pizza", and cake1 evaluates to cake("Vanilla", "white", "Happy wedding!", 4, false)

    • You can see what your Cakes look like by calling the function provided at the bottom of the file. It’s called draw-cake, and it takes a Cake as input and gives you back an Image of your Cake.

      In the interactions window, type draw-cake(cake1) and see what happens. Use the function with the Cakes YOU defined!

      image

      Students will spend lots of time "drawing" their Cakes. Encourage them to define some new Cakes, and to alter the color, message, layers, etc. to see their changes reflected in the images. Don’t forget to remind them to click "Run" after making any changes!

    Dot-Accessors

    Overview

    Learning Objectives

      Evidence Statements

        Product Outcomes

        • Students write code that extracts each field from those Cakes

        Materials

          Preparation

            Dot-Accessors (Time 10 minutes)

            • Suppose you want to get the flavor OUT of cake4. You don’t care about the message, color, or anything else - you just want to know the flavor. Pyret has syntax for that, called .flavor.

              If you type cake4.flavor into the interactions window, what should it evaluate to? Try it out!

              • What kind of thing did it return: A Number, String, Image, Boolean, or structure?

              • Practice taking the flavor out of EVERY Cake you have defined, using .flavor

              Of course, there are ways to access any part of a Cake, not just the flavor! What do you think you would get if you typed cake4.color in the interactions area?

              Try using the dot-accessors .color, .message, .layers and .is-iceCream on your Cakes! Do they do what you expect?

              A way to prompt students to use these accessors is to ask: "How do you get the message out of a Cake?" or "How do you get the layers out of a Cake?" Throughout the course you can set up a call and response system with students, where the question "How do you get the X out of a Y?" will prompt the name of the accessor.

            • The previous syntax is known as Dot-Accessors. They allow you to specify exactly what part of a structure you want. If we want to know if we can fit a certain Cake through a doorway, we probably only care whether the number of layers is less than a certain amount. Likewise, if we want to know whether or not a character in our game has died, we only need to know if his health is less than 0: we might not care what his location is, or the color of his armor. Programmers use accessors a lot, because they often need to know only one piece of information from a complex data structure.

            • Our Cake structure is defined using data Cake and the cake(...) line, which tells the computer what things make up that structure, and what order and type each thing is. In return, we get new functions to use. Until we write these two lines, we don’t have cake(...) (to make a Cake), .flavor (to get the flavor out of the Cake), .color, or any of the other dot-accessors, because Pyret doesn’t know what a Cake is- we haven’t defined it.

              To see this for yourself, type a pound sign (#) before the line which begins with cake(...). This comments it out, so that the computer ignores it. Hit run, and see what happens.

              When the cake(...) line is commented out, Pyret returns some errors, saying you’re trying to use cake before its definition. It doesn’t know what cake is or does, because we defined a Cake structure with no constructor. Make sure students understand that the line beginning with data and a line similar to cake(...) are needed in order to create and work with any structure.

            Closing

            Overview

            Learning Objectives

              Evidence Statements

                Product Outcomes

                  Materials

                    Preparation

                      Closing (Time 5 minutes)

                      • Data Structures are a powerful tool for representing complex data in a computer program. Simple videogames, like Pong, might only need to keep track of a few numbers at once, like the position of the ball, position of each paddle and the score. But if a game has many different enemies, each with their own position and health, or multiple levels with their own background image, the game can get very complicated very fast, and structures are a great way to manage and make sense of all the data. Programmers can do a LOT with data structures, and in the upcoming lessons you will create your own structures to make a customized videogame.

                        Have students volunteer what they learned in this lesson!