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 BY-SA-NC

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.

This page requires you to be logged in to access it. Please login and try again.
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 non-linear data structures! This is where data gets fun and a bit creative.
  • Non-linear data structures include node graphs and trees.
  • Check out the following video for an intro to data structures:

5 mins
Trees
Theory

Check out: What is a tree?

5 mins
Traversing the Tree
Example
  • Trees are non-linear, 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.
10 mins
Graphs
Theory

Check out: What is a Graph?

5 mins
Traversing the Graph
Example
  • Graphs, also called node graphs, are another non-linear 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.
10 mins
Linked Lists
Theory
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.
There are no records to display.
Powered by Gibbon v25.0.00dev | © Ross Parker 2010-2022
Created under the GNU GPL at ICHK | Credits | Translators