Data Structures & Graphs
Time
1.8 hrs
Difficulty
Intermediate
Prerequisites
Elevator Challenge
Departments
Science
Authors
Sandra Kuipers
Groupings
Individual
Minimum Year Group
None
Blurb
Data Structures
License
This work is shared under the following license: Creative Commons BYSANC
Outline
Learner Outcomes Students will:


Competency Focus

Interdisciplinary Connections

Reflection What was successful? What needs changing? Alternative Assessments and Lesson Ideas? What other Differentiation Ideas/Plans could be used?


Credits Any CC attribution, thanks, credit, etc.

You do not have access to this action.
10 mins
Structuring Data
Introduction
 What is a data structure?
 So far, we've already used data structures in our code: Arrays.
 Arrays are a linear data structure, like a list, where we access items in order with an index.
 There are also nonlinear data structures! This is where data gets fun and a bit creative.
 Nonlinear data structures include node graphs and trees.
 Check out the following video for an intro to data structures:
5 mins
Traversing the Tree
Example
 Trees are nonlinear, and at first it can be hard to see how they'd be useful.
 A Decision Tree is a type of tree structure, and a great way to visualize trees.
 Consider the following situation:
 Lets say I wanted to know what month you were born in, but I could only ask you yes or no questions.
 I could technically start at the beginning and ask...
 "Is is January? Is it February? Is it March?" etc... all the way to December.
 To get the right answer, I'd end up asking between 1 to 11 questions.
 This isn't very efficient! And programming is all about efficiency.
 Instead, we could structure the questions into a decision tree:
 With this structure, no matter which month it is, we would only ask 3 or 4 questions.
 To traverse a decision tree, start at the top, then work your way down until you reach a leaf node: the end result is your decision.
 This particular tree is a Binary Tree because each decision has two options.
5 mins
Traversing the Graph
Example
 Graphs, also called node graphs, are another nonlinear type of data structure.
 They're great for representing things that have connections to each other.
 This could be physical connections, like roads on a map or wires in a network.
 This could also be conceptual connections, like friends in a social network.
 For an example of a node graph, lets consider the board game Risk.
 In risk, the map is divided into six continents, each a different colour.
 Not all continents can reach each other: they're connected by land borders, or dotted lines for water connections.
 If we were programming a digital version of the Risk game, we'd need to know which continents can reach each other.
 To do this, we could represent the map as a node graph, below.
 Each continent is a node, and the connections between them are edges.
 To traverse a node graph, any one node can use it's edge to reference the next node, and so on and so forth.
 If you wanted to ensure you reached each node, you'd flag them as 'visited', then move onto the next unvisited node, until they're all visited.
5 mins
Traversing the List
Example
 Linked lists are a linear data structure.
 To traverse the list, you start as the head of the list, then move to the next item, until you reach the end.
 Linked lists can become circular if the end points back to the head.
 A singly linked list only has a single reference per node, which points to the next node.
 A doubly linked list has two references: a next node, and a previous node. This enables traversing the list in either direction.
60 mins
Data Structures
Evidence
 These are just three common data structures, there are others.
 The goal of this unit isn't to memorize them all, but to consider how they might be useful.
 Open up your slideshow from the beginning of this course.
 Pick any three of the following data structures and add some new slides to your slideshow:
 Tree
 Graph
 Linked List
 Stack
 Queue
 Array
 Hash
 For each slide, add:
 A short definition, in your own words.
 An image to illustrate this concept.
 Describe one idea of how you might use this data structure. Feel free to be creative :)
 The images and videos in the unit here will get you started, but you'll need to do some more research of your own to complete these slides.
 Once you have finished, submit the link to your slideshow as evidence of learning in this unit.
Links
Images
Embeds
There are no records to display.