Tables, Lists, Datatypes, and Trees – Oh My!

This lab is an important junction for two reasons: it's where those aiming for 200 should start ramping up to harder problems, and it's our last lab before we start Python (on Monday). As a result, this lab is structured with some options for you to choose from.

Learning Objectives

Designing Data Structures (Required for Everyone)

In lecture, we have done a couple of problems where we give you a problem scenario and ask you to figure out how to use tables, lists, and datatypes to capture the data. And now we have trees too!

The ability to figure out the structure of data needed for a problem is a critical skill in computing. Even if you never write code again after you leave CS111, you may need to think about a collection of data for a project and what shape it has (with someone else writing the code to process that shape). The problems in this section have you practice this skill (which you can expect to be tested on the second quiz or the final exam).

You are not writing any functions for this section.

Warmup – Reviewing Data Structure Features

When we are matching a data structure to a scenario, questions we ask ourselves include:

1. Do the data feature a fixed number of components, or an unknown/inconsistent number of components? For example, say you're recording data on dogs. In one scenario, you are guaranteed to get each dog's name, age and breed. In another scenario, there are no guarantees about which dog attributes you will receive. For example:

Scenario 1:

Name	Age	Breed
Bowser	4	Bulldog
Crowley	2	Ferret
Spot	10	Lab

Scenario 2:

• Bowser
• Crowley, 2 years old, ferret, white and brown stripes, loves long walks on the beach
• Spot, Lab, blue collar, owner is Ashley

2. Is the data meant to represent a single object (one-dimensional) or some collection of n objects (two-dimensional)? For example, say we're representing an Item in a store versus a Shopping Cart, which contains some indefinite number of Items. What's different about how we need to represent these?
3. If there are sequence-style relationships across parts of the data, are there branches/options in those relationships? For example, say we're representing a Shopping Cart versus a Family Tree. Both need to contain some indefinite sequence of data, but are different in how the items in the sequence relate.

Task: For each of the above three questions, write out which data structure you should use in each case of the question. When you are done, check your work against the summary in the expandable section below.

Data structure summary

1. Use a datatype when the number of components is fixed or a list if the number of components is not fixed
2. Use a table when the data are two-dimensional with fixed number of components, datatype when one-dimensional with fixed number of components. Lists within lists can capture multiple dimensions with non-fixed numbers of components
3. Trees when there are branches/options, lists when there are no options and the sequences can vary in length, otherwise datatypes can work

---

CHECKPOINT: Call over a TA once you reach this point.

---

Scenario Exercises

For each of these scenarios, complete the following two tasks:

Task: Which combination of tables, lists, datatypes, and trees might you use to capture the data in the scenario? You might find it useful to sketch a picture of the scenario to help you think through this.

Task: Expand the section marked "Data Structure Proposals" to see some specific datatype proposals for the scenario. Write an evaluation of whether the data structure makes sense, citing strengths and weaknesses of the proposal.

A datatype "makes sense" if it:

• reflects the key relationships among data in the scenario
• can accommodate larger versions of the scenario
• makes choices consistent with the strengths of each data structure (the criteria from the warmup)

You will put your answers into a Google Form. We're doing this to get a sense of how the class is doing, and so we can review how to talk about data structure choices in a future lecture.

Here's the form for your answers: https://forms.gle/DZShgYLS86RsJ1mX7

Scenario 1: An Elimination-Round Tournament

Consider a tournament that is played in elimination rounds: Some number of teams (usually a power of 2 such as 2, 4, 8, 16, …) enters the tournament. Teams are paired up for round 1. The winner from each round advances to the next, playing another winner from that same round. Each team plays at most once per round. The tournament finishes after a round with only two teams (which gives the overall winner).

Data structure proposals

# option 1 (a feeder match refers to a previous match 
that some team won to qualify for their current match)
datatype Match:
  | first-round(team1 :: String, 
                team2 :: String)
  | later-round(team1 :: String, 
                team2 :: String,
                feeder1 :: Match, 
                feeder2 :: Match)
end

# option 2
table: round :: Number, team1 :: String, team2 :: String
  ...
end

Scenario 2: A Round-Robin Tournament

Now consider a round-robin tournament, in which every team plays every other team, and the team with the best statistics (combination of points scored, score differences, etc) is the winner.

Data structure proposals

# option 1
table: team1 :: String, team2 :: String, score1 :: Number, score2 :: Number
  ...
end

# option2
data Match:
  | match(team1 :: String, team2 :: String, score1 :: Number, score2 :: Number)
end
Tournament is a List<Match>

Scenario 3 – A Guessing Game

Imagine a guessing game, in which a player is asked to think of an object/item/etc. The computer then asks a series of yes/no questions before making a guess as to what the object might be. Here are two sample sequences of questions and answers.

Computer: Does it have four legs?
Player: yes
Computer: Does it fit in your hand?
Player: yes
Computer: I guess a mouse

Computer: Does it have four legs?
Player: no
Computer: Does it have two legs?
Player: yes
Computer: Is it active at night?
Player: yes
Computer: I guess an owl

The guessing game program needs a data structure to capture the questions that the computer will ask, including the different "next" questions depending on the answer (yes or no). The question sequences could be long.

Data structure proposals

datatype GuessingGame1:
  | questions(first-ques :: String,
              yes-questions :: List<String>,
              no-questions :: List<String>)
end

datatype GuessingGame2:
  | guess(item :: String)
  | question(ques :: String, 
             if-yes :: GuessingGame2, 
             if-no :: GuessingGame2)
end

Scenario 4: Multiple-choice Guessing Game

Imagine a similar guessing game, but now the questions are multiple choice, with different numbers of answers per question. For example, now the computer might ask "How many legs does it have", with answers 0, 2, 4, and 100 all being acceptable answers.

Data structure proposals

# option 1
data MCGuessing1:
  | guess(item :: String)
  | question(choice1 :: MCGuessing1,
             choice2 :: MCGuessing1,
             choice3 :: MCGuessing1,
             choice4 :: MCGuessing1)
end

# option 2
data MCGuessing2:
  | guess(item :: String)
  | question(ques :: String, 
             options :: List<MCGuessing2>)
end

# option3
data MCGuessing3:
  | guess(item :: String)
  | question(ques :: String, 
             options :: List<Choice>)
end
data Choice:
  | choice(label :: String, 
           nextques :: MCGuessing3)
end

Scenario 5: Friends in a Social Network

Consider the connections between friends in a social network. Each person has some number of friends, who in turn have other friends, and so on. There may be multiple "friendship chains" that connect one person to another.

Data structure proposals

# option 1
data Person:
  | person(name :: String, friends :: List<Person>)
end
A social network is a List<Person>

# option 2
table name :: String, friends :: List<String>
  ...
end

---

CHECKPOINT: Call over a TA once you reach this point.

---

Matching Ads, One Last Time

The trees for the guessing game are examples of what are called decision trees: a series of questions about characteristics of an object or situation are asked, working down the tree until a decision (or guess) is reached at the bottom of the tree.

Some real-world ad-matching systems are based on decision trees. When a user is logged into a site, a program asks the site (e.g. Google) the questions in the tree about the user (e.g., "what gender are they", "what age-range are they", "where do they live", etc): the bottom of the tree contains the ads to show with users with traits from the answers.

In theory, we have shown you enough programming at this point to write an ad-matcher based on decision trees. In practice, that program would be a bit harder than what you're prepared for. Those who come to CS200, however, will do a course project that constructs a decision-tree from a table of data about ad-like information.

Option 1: Practice with Lists in Datatypes

Consider the following datatype, which represents information about a single course:

data Course:
  | lecture(name :: String, roster :: List<String>)
end

For now, we're just considering lecture-based courses, where each course contains the list of names of students who are taking the course.

Task: Copy this datatype into your file and make a couple of example courses.

Task: Write a function that takes a Course and a student name and returns a course. The returned course should have the student name added to the roster.

Task: Some years, it feels like certain students' first names appear many times. Write a function count-name which takes a Course and a name and returns the number of students with that first name who are in the course roster. Assume every name in the roster is formatted like this 'FIRSTNAME LASTNAME'.

Do this with explicit recursion, rather than built-ins.

Hint: The question here is how to write a recursive function to process a list that is inside of a datatype. You will need two functions here: a recursive one on a list of strings, and a non-recursive one on the datatype that calls your recursive one.

Task: Try to write down an explanation of why you needed two functions here. Why can't the count-name function that takes the datatype as input be recursive?

Task: If you have time (while still giving yourself time to get Pycharm installed), change the datatype so that the items in the roster aren't strings, but a new Student datatype with a student name and semester level.

Task: Where in your count-name function would you need to make edits in order to accommodate this change in datatype? You don't need to write the code (unless you want the practice). The point is to think about what parts of your original code would change or stay the same with this extended definition.

Option 2: Working with Trees (200-bound/Challenge)

You will write several tree programs as part of the bridge work for CS200. For this lab, we want to make sure that you understand how recursion works on trees before you start writing programs to process them.

Consider the following program, which returns the name of one person with the given eye color from the given tree. Your goal is to understand which name gets returned and why.

Task: Look at the program and the where cases. Without running the code, predict what the code will produce on each case.

data AncTree:
  | noInfo
  | person(name :: String, born :: Number, eye :: String, parent-1 :: AncTree, parent-2 :: AncTree)
end

robert-tree = person("Robert", 1893, "brown", noInfo, noInfo)
laura-tree = person("Laura", 1920, "blue", noInfo, noInfo)
john-tree = person("John", 1920, "green", noInfo, robert-tree)
ellen-tree = person("Ellen", 1945, "brown", laura-tree, john-tree)
bill-tree = person("Bill", 1946, "green", noInfo, noInfo)
susan-tree = person("Susan", 1971, "blue", ellen-tree, bill-tree)
charlie-tree = person("Charlie", 1972, "green", noInfo, noInfo)
anna-tree = person("Anna", 1997, "blue", susan-tree, charlie-tree)

NOBODY-FOUND = "Nobody was found!"

fun find-eye(at :: AncTree, with-color :: String) -> String:
  doc: "return name of one person with given eye color (assume there is one)"
  cases (AncTree) at:
    | noInfo => NOBODY-FOUND
    | person(n, b, e, p1, p2) =>
      if (e == with-color): n
      else:
        find-eye-p1 = find-eye(p1, with-color)
        if not(find-eye-p1 == NOBODY-FOUND): find-eye-p1
        else: find-eye(p2, with-color)
        end
      end
  end
where:
  find-eye(anna-tree, "green") is ...
  find-eye(anna-tree, "brown") is ...
end

Task: As you did two weeks ago in the recursion lab, draw a nested-box diagram for the program execution from the first where example, until the point when the if-expression evaluates to true.

As you did last week, upload a picture of your diagram to this form.

Note: The biggest mistake that students made on the nested-box diagrams in the recursion lab was not writing out the whole expression that surrounds the function call in the box. In Wednesday's class, when we wrote out the boxes for in-tree, notice that the pending use of or before the inner box and the pending call to in-tree(parent-2, name) after the inner box are both in the picture. Many students omitted these details last time.

Task: What is the sequence of values for parent-1 across the calls to in-tree, assuming we search for a name that is not in the tree? Assume we start with the call in-tree(anna-tree, "X"). Make a list of the calls to in-tree that occur in order, in a form like:

• in-tree(anna-tree, "X")
• in-tree(susan-tree, "X")
• …

Then annotate each call with the value that parent-1 will have in the directory at the time that the call gets made. What do you notice about that sequence after you've finished it?

Task: Write a program all-blue-eyed that takes an AncTree and returns a list of the names of all people with blue eyes.

Task: If you have time, make a copy of all-blue-eyed and modify it to take a predicate (function that returns boolean) that indicates which people to include in the output list (like a form of filter on trees).

---

CHECKPOINT: Call over a TA once you reach this point.

---

Optional: Installing Pycharm

The course switches to Python on Monday. If you would like help getting Pycharm installed on your computer, feel free to use lab time to get set up. Follow our Pycharm setup guide.

Do we have to use Pycharm? If you are already comfortable with a different Python programming environment, you are welcome to use it, as long as you are able to set it up to work with pytest, the Python testing framework. Course staff will only support Pycharm, however, so if you decide to use another tool, you have to be able to get it working on your own.