Topic 1 — Data Modelling | Algorithmics 21

Warning — JavaScript Disabled

It appears that you have JavaScript disabled in this browser. Some content may not work properly. Please enable JavaScript to have the full Algorithmics 21 experience.

Unit 3 — Area of Study 1 (From the Study Design)

On completion of this unit the student should be able to devise formal representations for modelling various kinds of information problems using appropriate abstract data types, and apply these to a real-world problem.

Graph Theory

A large chunk of time in Algorithmics is devoted to the study of graphs, as they are a very useful way of representing data. Below is an example of a graph, you can drag it around and zoom in and out (all graph examples in Algorithmics 21 are interactive like this one).


    g.nodes("a,b,c,d,e".split(",")).add();
    const edgeLengths = {
      "a,b": 7,
      "b,c": 8,
      "a,d": 5,
      "d,e": 15,
      "b,e": 2
    };
    const edges = Object.keys(edgeLengths).map(k => k.split(','));
    g.edges(edges).data(Object.values(edgeLengths)).add({
      length: d => d,
      labels: d => ({ 0: { 'text': d } })
    });

Let’s go through the key things that make up a graph.

Nodes and Edges

These are nodes:


    g.nodes(["a", "b"]).add().size('1.25x');

Nodes (also sometimes called a vertices) represent some point of data (maybe a city, house, computer, or road intersection). To provide information about how two nodes are related we can connect them together with an edge.


    g.nodes(["a", "b"]).add().size('1.25x');
    g.edge(["a", "b"]).add({labels: {0: {'text': '10'}}});

Edges represent a connection between two things that themselves are represented as nodes (for example: roads connecting cities or network cables connecting computers). Notice that, in the above graph, there is a "10" over the edge? That’s the edge’s weight, it could be used to represent the distance between two places, or the number of changes between two states. The weight of an edge basically represents a characteristic of that connection between nodes.

Edges can also be directed, meaning that they have a direction by which the connection goes. This is represented by the arrow on the end of the edge. We call the node at the end of the arrow the target node, and the one at the start the source node.


    g.nodes(["a", "b"]).add().size('1.25x');
    g.edge(["a", "b"]).add({directed: true, labels: {0: {'text': '10'}}});

Nodes have another characteristic that is related to edges. Specifically, the number of edges connected to them describes their degree. Have a look at the degree 1, degree 2 and degree 3 nodes below (they’re the ones in green marked with an "X").


    g.edgelayout('jaccard').edgelength(40);
    g.label('deg 1').add({ pos: ['-0.6cx', '0.6cy'], text: 'degree 1' });
    g.label('deg 2').add({ pos: [0, '0.6cy'], text: 'degree 2' });
    g.label('deg 3').add({ pos: ['0.6cx', '0.6cy'], text: 'degree 3' });
    g.labels().duration(0).font('Source Serif Pro').size(18)

    g.node("X1").add({pos: ['-0.6cx', -30], labels:{0:{text: 'X'}}}).color('green');
    g.node(1).add({pos: ['-0.6cx', -10], labels:{0:{text: ''}}});
    g.edge(["X1", 1]).add();

    g.node("X2").add({pos: [0, -10], labels:{0:{text: 'X'}}}).color('green');
    g.node(2).add({pos: [-20, -10], labels:{0:{text: ''}}});
    g.node(3).add({pos: [20, -10], labels:{0:{text: ''}}});
    g.edge(["X2", 2]).add();
    g.edge(["X2", 3]).add();

    g.node("X3").add({pos: ['0.6cx', -30], labels:{0:{text: 'X'}}}).color('green');
    g.node(4).add({pos: ['0.6cx', 0], labels:{0:{text: ''}}});
    g.node(5).add({pos: ['0.6cx-20', -40], labels:{0:{text: ''}}});
    g.node(6).add({pos: ['0.6cx+20', -40], labels:{0:{text: ''}}});
    g.edge(['X3', 4]).add();
    g.edge(['X3', 5]).add();
    g.edge(['X3', 6]).add();

Circuits

A graph contains a circuit if there is more than one path that connects two nodes. This pops up when there is a "loop" or "circle" in the edges of a graph. Circuits themselves specifically contain no repeated edges (but they can contain repeated nodes) and start and end on the same node. Note that, in the graph below, there is a circuit following the path of "a", "b", "c" then "a" again. If there wasn’t an edge between "c" and "a", then there wouldn’t be a circuit in this graph.


    g.nodes("a,b,c,d".split(",")).add();
    const edgeLengths = {
      "a,b": 7,
      "b,c": 8,
      'c,a': 1,
      'd,a':1
    };
    const edges = Object.keys(edgeLengths).map(k => k.split(','));
    g.edges(edges).add();
    g.edges([["a", "b"], ["b", "c"], ["c", "a"]]).traverse('green')

Graphs

A Graph is a collection of nodes and edges that may or may not be joining those nodes. We’ve already explored what a graph looks like before, but here are a few specific categories of graph:

Connected Graphs: These graphs are ones where every node is connected to every other node, either directly or indirectly. That is, starting from any node, you can reach any other node by traversing one or more edges.
Directed Graphs: Directed graphs feature exclusively edges that are directed.
Weighted Graphs: A Weighted graph is one that has weights on all of its edges.
Labelled Graphs: A Labelled graph has got labels on all of its nodes.
Trees: A tree is a kind of graph that is connected, but does not contain any circuits.
Forests: Forests are a collection of tree graphs that are not joined to each other (although, you can connect them by just adding one edge).
Subgraphs: A Subgraph is a part of a larger graph. All edges and nodes in a subgraph must be in the original graph, but not all edges and nodes in the original graph have to be in the subgraph.

Graphs also have a property called their width. On weighted graphs, the width is the maximum of the minimum distance between two nodes (that is, where you sum up all the edge weights between those two nodes). So, for the graph below, the weight would be 19. This is because the minimum distance path between "b" and "d" is the longest of the paths in the graph.


    g.nodes("a,b,c,d,e".split(",")).add();
    const edgeLengths = {
      "a,b": 5,
      "a,c": 2,
      "b,c": 5,
      "d,c": 14,
      "c,e": 4,
      "d,e": 34,
      "b,e": 5
    };
    const edges = Object.keys(edgeLengths).map(k => k.split(','));
    g.edges(edges).data(Object.values(edgeLengths)).add({
      length: d => d,
      labels: d => ({ 0: { 'text': d } })
    });
    g.node("c").pos([10, 0]);
    g.node("d").pos([-50, 20])

Unfortunately for you, there is no good way of calculating the width of a graph. The quickest way is to go through every pair of nodes and find the minimum distance between them.

On an unweighted graph (that’s one without weights on any of its edges), the width is found by assuming that each edge has a weight of one.

Minimum Spanning Trees

A Minimum Spanning Tree (MST) is a subset of a connected, undirected and weighted graph that represents the tree that connects all nodes in that graph with the smallest distance possible. As an MST is a tree, it cannot have any circuits in it.

So, for the previous graph, the minimum spanning tree would look something like the tree highlighted in green here:


    g.nodes("a,b,c,d,e".split(",")).add();
    const edgeLengths = {
      "a,b": 5,
      "a,c": 2,
      "b,c": 5,
      "d,c": 14,
      "c,e": 4,
      "d,e": 34,
      "b,e": 5
    };
    const edges = Object.keys(edgeLengths).map(k => k.split(','));
    g.edges(edges).data(Object.values(edgeLengths)).add({
      length: d => d,
      labels: d => ({ 0: { 'text': d } })
    });
    g.node("c").pos([10, 0]);
    g.node("d").pos([-50, 20])

    g.edges([["a", "c"], ["c", "e"], ["e", "b"], ["c", "d"]]).color('green');

Note that the edge between the nodes "e" and "b" could be switched for the edge between "a" and "b" or the one between "c" and "b". This is because they all connect the tree to node "b" and have the same weight.

The easiest method to find the minimum spanning tree is Prim’s Algorithm. Below are the generalised steps for the algorithm. [JonesEtAl2016]

Choose a starting node (it doesn’t matter which one you go with).
Look at the edges coming out of that node and choose the one with the lowest weight (if there are multiple with the same weight, it doesn’t matter which one you pick). These nodes and the edge that connects them will form the start of the MST.
Now look at all the edges coming of from the nodes currently in your tree and select once again the edge with the smallest weight. But do not pick an edge that would connect the graph to itself.
Repeat this process until all the nodes are connected.

Walks, Trails, Paths and Cycles

When talking about graphs, we tend to spend a lot of time talking about collections of connected edges. And so, we have specific words that are used to describe specific instances of those edges. These are walks, trails, paths, and cycles (and circuits, but we’ve already talked about them in "circuits"). And there are subcategories of each of those categories.

A walk is a sequence of edges, each edge connecting successive nodes. A trail is a walk with no repeated edges. A path is a walk containing no repeated edges and no repeated nodes. A cycle is a path that starts and ends on the same node (that start and end node is the one exception to the rule of paths that there can be no repeated nodes). [JonesEtAl2016]

Now, let’s have a look at a specific type of trail: Eulerian Trails. They are basically just trails (meaning that they don’t contain repeated edges) that include all edges in a graph. Euler (pronounced oi-ler) said that, in order for an Eulerian trail to exist, the graph would need to have exactly zero or two odd-degree nodes (that is, nodes with a degree of 1, 2, 3, 5, 7, etc.). Only the start and end nodes of the trail can be the odd-degree nodes. This is because you need to be able to enter and exit every other node in order to move around the graph, and therefore their edges need to be even. Below is an example of an Eulerian trail where the blue node is the start, and the red node is the end. (You can click "run" to re-run the animation if you missed it.)


    g.nodes("a,b,c,d".split(",")).add();
    const edgeLengths = {
      "a,b":1,
      "b,c":1,
      "c,d":1,
      "d,a":1,
      "a,c":1
    };
    const edges = Object.keys(edgeLengths).map(k => k.split(','));
    g.edges(edges).data(Object.values(edgeLengths)).add({
      length: d => d,
    });
    g.node("a").color("blue");
    g.pause(0.5);
    g.edge(["a", "d"]).traverse("green");
    g.pause(0.5);
    g.edge(["d", "c"]).traverse("green");
    g.pause(0.5);
    g.edge(["c", "a"]).traverse("green");
    g.pause(0.5);
    g.edge(["a", "b"]).traverse("green");
    g.pause(0.5);
    g.edge(["b", "c"]).traverse("green");
    g.pause(0.2);
    g.node("c").color("red");

There are also Eulerian Circuits, which are just Eulerian trails, but that start and end at the same node. These circuits exist only if the graph is connected and if all the nodes of the graph have an even degree.

In paths, we have the Hamiltonian Path, which is a path (that is, contains no repeated edges or nodes) that includes all nodes in a graph. And in cycles, the Hamiltonian Cycle, which is just a Hamiltonian path that starts and ends at the same node. (note that the starting node is an exception to the no repeated nodes rule). Hamiltonian cycles are also said to be Hamiltonian paths that end at a node that is adjacent to the starting node. That is, the end node needs to have an edge connecting it with the start node. Below is an example of a Hamiltonian path.


    g.nodes("a,b,c,d".split(",")).add();
    const edgeLengths = {
      "a,b":1,
      "c,d":1,
      "c,d":1,
      "d,a":1,
      "a,c":1
    };
    const edges = Object.keys(edgeLengths).map(k => k.split(','));
    g.edges(edges).data(Object.values(edgeLengths)).add({
      length: d => d,
    });
    g.node("b").color("blue");
    g.pause(0.5);
    g.edge(["b", "a"]).traverse('green');
    g.pause(0.5);
    g.edge(["a", "c"]).traverse('green');
    g.pause(0.5);
    g.edge(["c", "d"]).traverse('green');
    g.pause(0.2);
    g.node("d").color("red");

Adjacency Matrices

We can also represent a graph in a much more boring — but very helpful — way. As an adjacency matrix. Adjacency Matrices records the number of connections between the nodes of a graph. Below is a graph and underneath it, is its adjacency matrix.


    g.nodes("a,b,c,d,e".split(",")).add();
    const edgeLengths = {
      "a,b":1,
      "b,c":1,
      "d,e":1,
      "b,d":1,
      "a,c":1,
      "a,e":1
    };
    const edges = Object.keys(edgeLengths).map(k => k.split(','));
    g.edges(edges).data(Object.values(edgeLengths)).add({
      length: d => d
    });
    g.edge(["a","b", "1"]).add();

\[\begin{array}{c c} & \begin{array}{c c c c c} a & b & c & d & e \\ \end{array} \\ \begin{array}{c c c c c} a \\ b \\ c \\ d \\ e \end{array} & \left[ \begin{array}{c c c c c} 0 & 2 & 1 & 0 & 1\\ 2 & 0 & 1 & 1 & 0\\ 1 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 1\\ 1 & 0 & 0 & 1 & 0 \end{array} \right] \end{array}\]

Every adjacency matrix has a row and a column for each node in the graph. The number represents the amount of edges connecting the node on the row to the node on the column. So, the 2 at the intersection of "a" and "b" means that there are two edges between the nodes "a" and "b".

Abstract Data Types

Abstract Data Types (ADTs) are containers for information. Each different type of ADT has specific "operators" defining how information in the ADT is created, accessed and deleted.

Each ADT has a specification associated with it, which informs the possible operations that can be performed involving the ADT. Note that the specification is not specific to any programming language, and does not tell us about how the ADT is implemented in code. For Algorithmics you do not need to know how individual ADTs are implemented.

There are two main categories of operators for an ADT: constructors and observers. Constructors are operators that are used to construct or build different values of the data type. And Observers are ones that are used to look up the data in the ADT.

The following specifications for the ADTs are for the 2021 Algorithmics course. The specifications tend to change year to year, so take them with a grain of salt. Although, the syntax used has been pretty constant throughout the years.

Arrays

Arrays are a method of storing elements in a collection that is of a fixed length. Elements in an array can only be accessed by their index in the array. You can think of it like a book: it has a fixed length, and you can get a page’s information by turning to that page number.

ADT_Specification

NAME: Array
IMPORTS: Element, Integer
OPERATORS:
  Create: Integer -> Array
  Set: Array × Integer × Element -> Array
  Get: Array × Integer -> Element

Lists

A list is similar to an array, but instead of having one unchangeable length, it is flexible and can have any length. Elements can be inserted to the list at any point and can be deleted at any point too. The list ADT is very similar to an actual list like you might have in your notes app: you can read and edit information at any point in the list, and add new elements to it in any way that you’d like.

ADT_Specification

NAME: List
IMPORTS: Element, Integer, Boolean
OPERATORS:
  Create: -> List
  IsEmpty: List -> Boolean
  Get: List × Integer -> Element
  Set: List × Integer × Element -> List
  Insert: List × Integer × Element -> list
  Delete: List × Integer -> List

Stacks

A Stack is an ordered collection of items that are retrieved in a last in, first out (LIFO) basis. That is, new elements are added to the top of the stack, and items are taken from the top of the stack also. You can only take items from the top of the stack, and cannot get them from anywhere else in the stack.

ADT_Specification

NAME: Stack
IMPORTS: Element, Boolean
OPERATORS:
  Create: -> Stack
  IsEmpty: Stack -> Boolean
  Push: Stack × Element -> Stack
  Peek: Stack -> Element
  Pop: Stack -> Stack

Note that — unlike in certain programming languages (like JavaScript) where pop() would take the item off the top of the stack and return itself — the Stack ADT requires that you first peek the element, then remove it via pop.

Queues

A Queue is like a stack, in that it is an ordered collection of items, but unlike a stack, the items in a queue are retrieved in a first in, first out (FIFO) order. New elements are added to the end of the queue, and elements can only be retrieved if they are at the front of the queue.

ADT_Specification

NAME: Queue
IMPORTS: Element, Boolean
OPERATORS:
  Create: -> Queue
  IsEmpty: Queue -> Boolean
  Append: Queue × Element -> Queue
  Peek: Queue -> Element
  Serve: Queue -> Queue

Priority Queues

A Priority Queue is just a queue, but the order in which elements are considered for removal from the queue is determined by their "priority" value. So, for example, if all elements in a priority queue had a priority of one, and an element with priority of two was added to the queue, then that two priority element would be removed first. Priority Queues still follow the first in, first out, rule. But consider the highest priority values first, before moving on to lower ones.

Note that Priority Queues can consider both when the minimum value is the highest priority, or when the maximum value has the highest priority. For simplicity’s sake, the ADT specification assumes that the lower value has the higher priority.

ADT_Specification

NAME: Priority Queue
IMPORTS: Element, Integer, Boolean
OPERATORS:
  Create: -> Priority Queue
  IsEmpty: Priority Queue -> Boolean
  InsertWithPriority: Priority Queue × Element × Integer -> Priority Queue
  GetMin: Priority Queue -> Element
  RemoveMin: Priority Queue -> Priority Queue

Dictionaries

If you’ve used Python you’re probably already familiar with what a dictionary is. But if you haven’t, a Dictionary is an unordered collection of key-value pairs. That is, it contains a bunch of keys, where each key represents a specific value. In an actual real-life dictionary, the keys would be words, and the values would be their definitions. We call that connection between a key and a value a "key-value pair".

ADT_Specification

NAME: Dictionary
IMPORTS: Element, Boolean
Operators:
  Create: -> Dictionary
  HasKey: Dictionary × Element -> Boolean
  Add: Dictionary × Element × Element -> Dictionary
  Update: Dictionary × Element × Element -> Dictionary
  Remove: Dictionary × Element -> Dictionary
  Get: Dictionary × Element -> Element

Graphs

If you’ve read the previous section on graph theory, then you should be all good with what a graph is and how they work. If you haven’t read that section, you probably should.

ADT_Specification

NAME: Graph
IMPORTS: Element, Boolean, List
OPERATORS:
  Create: -> Graph
  AddNode: Graph × Element -> Graph
  AddEdge: Graph × Element × Element -> Graph
  Adjacent: Graph × Element × Element -> Boolean
  Neighbours: Graph × Element -> List

Challenges

Consider the following graph:
g.nodes("a,b,c,d,e,f,g".split(",")).add(); const edgeLengths = { "a,b":1, "b,c":2, "e,d":4, "c,d":5, "e,c":6, "d,f":6, "c,g":5, "e,g":4, "f,b":2 }; const edges = Object.keys(edgeLengths).map(k => k.split(',')); g.edges(edges).data(Object.values(edgeLengths)).add({ length: d => d, labels: d => ({ 0: { 'text': d } }) });
1. What is the degree of the nodes "a", "c" and "e"?
2. What is the minimum distance between node "g" and node "d"?
3. What is the graph’s width?
4. Describe two features of this graph.
Given the following graph, what is its adjacency matrix?
g.nodes("a,b,c,d,e".split(",")).add(); const edgeLengths = { "a,b": 2, "b,c":4, "c,a":1, "c,e":5, "c,d":2, "d,e":4, }; const edges = Object.keys(edgeLengths).map(k => k.split(',')); g.edges(edges).data(Object.values(edgeLengths)).add({ length: d => d, labels: d => ({ 0: { 'text': d } }) }); g.edge(["c", "e"]).directed(true)
Wei recently opened a hat store. His hat store has many different hats at many different price points. Wei wants to create a Point of Sale system where he can enter the type of hat, and it tells him what price to charge for it.
1. Name an appropriate abstract data type Wei should use to represent the hats and their prices.
2. What operations of the ADT you named would be useful for Wei’s hat store, and why?
What operation of a stack allows the program to get the top-most element?

Jessie uses a queue to represent their schoolwork. Starting from an empty queue on Monday, Jessie performs the following sequence to their queue over the week.

pseudocode

// Monday
Queue.Append("Algo study")
Queue.Peek()
Queue.Serve()

// Tuesday
Queue.Append("Email CJ")
Queue.Append("Enviro Natural Systems Sheet")
Queue.Append("Methods SUP")
Queue.Peek()
Queue.Serve()

// Wednesday
Queue.Append("Lang Sheet")
Queue.Peek()
Queue.Serve()

// Thursday
Queue.Append("More Methods SUP")

// Friday
Queue.Peek()
Queue.Serve()

What does the queue look like at the end of Monday?
What does the queue look like at the end of Tuesday?
What does the queue look like at the end of Friday?

Given the following graph, draw its Minimum Spanning Tree.
g.nodes("a,b,c,d,e,f".split(",")).add(); const edgeLengths = { "a,b":2, "a,c":1, "c,b":4, "c,d":1, "d,e":2, "d,f":3 }; const edges = Object.keys(edgeLengths).map(k => k.split(',')); g.edges(edges).data(Object.values(edgeLengths)).add({ length: d => d, labels: d => ({ 0: { 'text': d } }) });
Write a brief explanation of the following ADTs.
1. Array
2. List
3. Priority Queue
Valerii has been trying to import vaccines from Russia. And he wants to use a graph to represent their shipment from Russia and around Australia. Below is the data he has for how many thousand vaccines are going where.

\[\begin{matrix} from \backslash to & Rus. & VIC & NSW & QLD & WA & SA & TAS & NT & ACT \\ Rus. & 0 & 1000& 2000& 0 & 0 & 0 & 0 & 0 & 0\\ VIC & 0 & 0 & 0 & 0 & 0 & 300& 200 & 0 & 0\\ NSW & 0 & 0 & 0 & 1000& 0 & 0 & 0 & 0 & 75\\ QLD & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 500& 0\\ WA & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ SA & 0 & 0 & 0 & 0 & 100& 0 & 0 & 0 & 0\\ TAS & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ NT & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ ACT & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}\]
1. Create the graph that shows how the vaccines are being shared around Australia.
2. What type of graph is this?
3. Using your graph, which state or territory receives the fewest vaccines?
4. Given that it takes one month for vaccines to be passed from one location to another, how many months would it take for the vaccines to reach the state you just said from Russia.

Answers

Consider the following graph:
g.nodes("a,b,c,d,e,f,g".split(",")).add(); const edgeLengths = { "a,b":1, "b,c":2, "e,d":4, "c,d":5, "e,c":6, "d,f":6, "c,g":5, "e,g":4, "f,b":2 }; const edges = Object.keys(edgeLengths).map(k => k.split(',')); g.edges(edges).data(Object.values(edgeLengths)).add({ length: d => d, labels: d => ({ 0: { 'text': d } }) });
1. Node "a": 1; node "c": 4; node "e": 3.
2. The minimum distance between "g" and "d" is 8.
3. The width of the graph is 10. (From node "e" to "f")
4. The graph is connected, weighted and labelled.
Here is the adjacency matrix. Be sure to note the edge between "c" and "e" is a directed edge.

\[\begin{array}{c c} & \begin{array}{c c c c c} a & b & c & d & e \\ \end{array} \\ \begin{array}{c c c c c} a \\ b \\ c \\ d \\ e \end{array} & \left[ \begin{array}{c c c c c} 0 & 2 & 1 & 0 & 0 \\ 2 & 0 & 4 & 0 & 0 \\ 1 & 4 & 0 & 2 & \bold{5} \\ 0 & 0 & 2 & 0 & 4 \\ 0 & 0 & \bold{0} & 4 & 0 \end{array} \right] \end{array}\]
Wei’s hat store
1. A Dictionary ADT is the most appropriate for storing a hat’s name, and it’s cost. (name as a key, and cost as a value).
2. Wei could use the Get operation to get the cost of a hat, given its name. (the name could also be a barcode or something similar).
The Peek operation allows the program to get the top-most element.

Jessie’s schoolwork queue

At the end of Monday: the queue is empty.

pseudocode

Queue.Append("Algo study") // Queue = ["Algo study"]
Queue.Peek() // Queue doesn't change
Queue.Serve() // Queue = []

At the end of Tuesday: the queue looks like ["Enviro … Sheet", "Methods SUP"].

pseudocode

Queue.Append("Email CJ") // Queue = ["Email CJ"]
Queue.Append("Enviro Natural Systems Sheet") // Queue = ["Email CJ", "Enviro ... Sheet"]
Queue.Append("Methods SUP") // Queue = ["Email CJ", "Enviro ... Sheet", "Methods SUP"]
Queue.Peek() // Queue doesn't change
Queue.Serve() // Queue = ["Enviro ... Sheet", "Methods SUP"]

At the end of Friday: ["Lang Sheet", "More Methods SUP"].

pseudocode

Queue.Append("Lang Sheet") // Queue = ["Enviro ... Sheet", "Methods SUP", "Lang Sheet"]
Queue.Peek() // Queue doesn't change
Queue.Serve() // Queue = ["Methods SUP", "Lang Sheet"]

Queue.Append("More Methods SUP") // Queue = ["Methods SUP", "Lang Sheet", "More Methods SUP"]

Queue.Peek() // Queue doesn't change
Queue.Serve() // Queue = ["Lang Sheet", "More Methods SUP"]

Here’s the MST. (You might have to drag it around to see it)
g.nodes("a,b,c,d,e,f".split(",")).add(); const edgeLengths = { "a,b":2, "a,c":1, "c,d":1, "d,e":2, "d,f":3 }; const edges = Object.keys(edgeLengths).map(k => k.split(',')); g.edges(edges).data(Object.values(edgeLengths)).add({ length: d => d, labels: d => ({ 0: { 'text': d } }) }); g.edges([ ["a", "b"], ["a", "c"], ["c", "d"], ["d", "e"], ["d", "f"] ]).color("green")
Brief descriptions of ADTs
1. Array — A fixed length, ordered collection of items that can each be accessed by their index (position) in the array. Items can be updated or removed.
2. List — A (theoretically) infinite ordered collection of items that can each be accessed by their index in the list. Items can be added, changed, or deleted.
3. Priority Queue — Items are added to the queue and are assigned a priority value. Items are then served following normal queue conventions, but with the highest priority items being served first.
Valerii’s Vaccines
1. Graph (you may have to zoom out to see it fully)
  g.edgelayout('individual'); g.nodes("Rus.,VIC,NSW,TAS,QLD,WA,SA,NT,ACT".split(",")).add().size('1.5x'); const edgeLengths = { "Rus.,VIC":1000, "VIC,TAS":200, "VIC,SA":300, "SA,WA":100, "Rus.,NSW":2000, "NSW,QLD":1000, "QLD,NT":500, "NSW,ACT":75 }; const edges = Object.keys(edgeLengths).map(k => k.split(',')); g.edges(edges).data(Object.values(edgeLengths)).add({ length: 100, labels: d => ({ 0: { 'text': d } }), directed: true });
2. It is a directed tree.
3. The Australian Capital Territory gets the fewest amount of vaccines. (For each node, the amount of vaccines they receive is determined by the weight of the incoming edge minus the weights of edges leaving the node)
4. Two months. (Count edges)

References

[JonesEtAl2016] https://www.cambridge.edu.au/education/titles/Further-Mathematics-VCE-Units-34-Revised-print-and-interactive-textbook-powered-by-HOTmaths%3ACambridge-Senior-Mathematics-Australian-Curriculum-VCE/ (Graphs and networks are covered in Unit 4 of Further Mathematics)