Event Report : Tree Algorithm – Let’s play with trees

by SIJP staffin Education、English、Event、Event Reporton 投稿日:

Introduction

SIJP has been teaching computer science to students in Seattle, as well as to students in Japan’s Kumamoto and Fukuoka prefectures via a teleconference system called Zoom. On Nov 17th, we held a class called “Let’s play with trees -Tree Algorithms”. I hope everyone who was able to attend enjoyed it. This document is the report for those who missed the class. This is our 5th installment of the SIJP classes.

Main Theme of the class

We developed the class material with the goal of enabling students to learn one of the basics of computer science – trees. Tree algorithms are important due to advancements in machine learning and AI technology that sometimes deal with trees. Tree algorithms are usually taught in high school AP classes and university CS classes. But, we wanted to give it a try. So, do not worry if it is too difficult!

Assignments

We prepared and assigned two assignments ahead of class as practice for the students. We know Xmas is coming up and people are setting up Xmas trees soon. So, we used Xmas trees.

 

Create a binary tree from a Xmas tree

 

You can click the image to use it in your class

We had 63 submissions! Thank you for the submissions.

 

Typical answers were:

We wanted to give the kids a preview of what binary trees look like and also, most importantly, see that there are several correct answers to this question as you can see above. Hopefully the kids are reminded of tree algorithms when they see Xmas trees this holiday season.

Create a Numbered Binary Tree

You can click the image to use it in your class

 

In this assignment, the kids created another binary tree, but this time with a decoration conversion table to convert decorations to numbers in preparation for the tree algorithms.

Typical answers were:

The rightmost one is not a binary tree since it does not have edges. We hope these assignments give kids a sense of what trees look like in computer science.

Ice-breakers

 

First, we explained we have four classrooms today with distance. We had students from each classroom introduce their location to the other classrooms.

This time we welcomed new students from Hokkaido. We loved Hokkaido because of the amazing food and beautiful scenery. Please visit Hokkaido if you have time.

We worked on creating a Kahoot quiz from Kumamoto/Fukuoka/Kumamoto/Hokkaido. Here is the quiz we created and played together.  Please give it try.

 

Introduction

Yoga Tree Pose

 

We started off doing a Yoga tree pose together. Kenji is into Yoga recently and he really enjoys it.

We used the following video for reference.

It was interesting to see all the classrooms in Japan and Seattle become and feel like trees.

We also identified where the “root” and “leaves” were which we discussed in more detail later in the class.

Tree structure around us

Then, we discussed tree examples around us.

  • A family tree starting from you, your parents, your grandparents….
  • A company structure starting from CEO
  • A decision tree (such as “Are you happy” advice support tree)
  • Food chain starting from human like the one below

  • A web page in HTML

Data Structure

Then, we talked about data structures, which is an important concept in Computer Science. The leading teachers used school lockers in US and coin lockers in Japan as an examples. They store items for people and you can get items when they need to.  These are real life examples of data structures.

Data structures have three key ideas according to Wikipedia

  • a collection of data values
  • the relationships among them
  • the functions or operations that can be applied to the data

New Tree Algorithm Vocabrary

After that, we defined the following terms relating to tree data structure.

  • Node
  • Root
  • Leaves
  • Paren nodet
  • Child node
  • Edges

The following slide explains these terms.

We created the follow Seesaw activity to let kids review these.

You can click the image to use it in your class

Tree traversal

Tree traversal is a method to visit all nodes in a tree. In class, we used an example of collecting all decorations after Xmas day.

 

There are two algorithms: Depth-first traversal and breadth-first traversal. The following figure shows the difference.

To implement these algorithms, other data structures (Queue and Stack) are needed. Queue is used for breadth-first traversal (pseudocode) and Stack is used for depth-first traversal (pseudocode).  

Unplugged Activity

It is hard to understand these algorithms just by listening to them. So, we have decided to work on an unplugged activity. Here are videos that explain the process in detail (sorry in Japanese).

In this activity, kids become nodes and go through Queue/Stack and Output.  

We prepared

  • Numbered jersey uniforms – kids wear them for tree numbers
  • Jumbo cards – leave them at node to identify the child
  • Blue tape – to draw trees on the floor

The steps are:

  • Layout all jumbo numbers on the nodes
  • Each kid go to node with corresponding uniform
  • Starting from root, they will go to Queue (breadth-first) or Stack (depth-first)
  • When they leave Queue or Stack
    • they have to look for their Jumbo card and identify their node’s children
    • Call out their children to put into Queue or Stack
  • They will go into Output

The pseudocode can be found here.

We did several times after we shuffle jumbo cards to rearrange kids

 

We hope the kids understood the algorithms better by going through the data structures by themselves.

Seesaw Activity

After the kids understood the algorithms, they worked on Seesaw activities.

You can click the image to use it in your class

 

You can click the image to use it in your class

According to the submissions, we think that most of the kids understood both algorithms. Of course, coding it is not very easy. But, at least, we believed they felt and enjoyed the algorithms.


Kahoot time

As usual, we did Kahoot quiz show about Trees. I hope they enjoyed the show.

 

Feedback (mostly from Japan)

Kids

 

After the class, we asked for evaluations. Here are the results.

Comparing this to the last class (which was about bugs), it looks like comprehension score went down. We think it is because of the difficulty of the subject matter and the unfamiliarity with the  jargon/words (such as nodes)

 

Good

  • Enjoy Kahoot
  • Teacher’s detailed explanation
  • Activities using our body
  • Understanding computers
  • Using iPad
  • Work on the same activities from different places
  • Teaching assistant at tables

Improvements

  • Needs Japanese translation
  • Microphone noise was there
  • Screen is too small
  • Need more time to help each other

 

Comments

  • Tree is everywhere
  • I want to join next one


Parent

Motivation for joining

  • Collaboration of interesting subjects (English and Computer Science)
  • Taught by Engineers
  • Keep English skills
  • Looks interesting

Comments

  • We reviewed after we went home
  • Please explain why we do this in English
  • My kids enjoyed so much so forget they are doing this class in English

We are planning to have class in December 15 about hour of code. So, please stay tuned.