Teaching and learning

Detailed example

Algorithm challenge – Eating jellybeans

Mary likes to eat jellybeans. Her methods are rather idiosyncratic and follow the rules:

• Eats exactly one jellybean at a time.
• Eats a jellybean from a colour that has the most number of jellybeans left.
• If there is a tie on colours, selects by preference.
• Mary prefers red jellybeans the most, then green, and then blue.

For example if there are 3 red, 4 green, and 2 blue, which could be represented using two lists:

• ColourPreference={red,green,blue}
• ColourQuantity={3,4,2}

Then Mary will eat the jellybeans in the following order: green, red, green, red, green, blue, red, green, blue.

Write an algorithm to facilitate Mary’s jellybean eating methods. You will input a list in order of Mary’s preference of 1 to N distinct colours of jellybeans and a second list which contains the corresponding number of jellybeans of each colour.

• ColourPreference={red,green,blue,pink,yellow}
• ColourQuantity={3,3,4,2,7}

Sample partial solution as an algorithm as it would appear in Edgy using conditionals, iteration and defined functions

The pseudocode shows the blocks which define a function called MaryEatsJBs.

Detailed example

Developmental project – Analysing character relationships in text

Students create a data model to store information about relationships between characters in a text they are studying or have studied, and then create algorithms to analyse these relationships. This could be done in small groups and could be broken up into stages.

These are examples of prompts that could be used when students are creating a data model for the character relationships.

• Which characters are used to develop the theme? What role do they play in the unfolding action?
• What kinds of relationships exist between the characters? How many interactions exist between the characters in the story?
• What are the main events? Which characters are involved?
• Create a data model representing your characters and their characteristics. You can use Edgy to prototype your ideas.
• Model the relationships between characters (such as kinship, friendship, culture, shared traits / geography, number of conversations) and may include other factors (themes, settings) that may be particular to your story.

Students could be given an opportunity to peer-review each other’s data models.

These are examples of prompts that could be used when students are creating algorithms to analyse the character relationships.

• How could the graph algorithms you have studied be used to analyse relationships between characters in this text? You could consider grouping characters by certain characteristics or shared properties involving themes, traits and actions.
• Write an algorithm that determines who the central characters are in your text.
• Write an algorithm that ranks the characters in the text according to their importance. You could consider their proximity to other characters or to the themes or events in the text.

These are examples of prompts that could be used when students are justifying their proposed solutions.

• Discuss why you selected particular data models and algorithms for your design.
• What other designs might have also met the requirements?
• Provide a logical argument for the correctness of your solution for identifying shared properties and establishing importance and proximity of characters.
• Provide a conclusion, which is a reflection on how your model could be improved by comparing different models and algorithms that could have been used. Describe with the benefit of hindsight what you would have done differently if you could do this project again?

Sample text analysis – Macbeth

The pseudocode below identifies characters and action in an Act in Macbeth.

The pseudocode shows the blocks which define a function called EnquireAct which has a single argument called Act.

Figure 2

Image description

Detailed example

Investigating methods for solving recurrence relations

Students are required to be able to fluently solve recurrence relations by applying the Master Theorem. One way in which students could be supported to develop a deep understanding of the Master Theorem is by exploring how the three different cases in the Master Theorem arise. This can also assist students to improve their understanding of recurrence relations in general.
Consider a divide and conquer algorithm for finding the lowest item in a list of length n. It divides the list into two halves, finds the minimum of each half and then calculates the global minimum. The recurrence relation for this algorithm is shown below.

Consider also the mergesort algorithm. Its recurrence relation is shown below.

A third recurrence relation could also be considered.

The time complexity of algorithms with these algorithms can be investigated in a range of ways. One method is to draw their call tree and observe the running time in each call of the algorithm. For example:

Figure 3

It can be seen that for the first recurrence relation, the sum of each level of the call tree increases as the execution goes deeper into the call tree. It can also be observed that each level of the call tree is more than the sum of all previous levels. It can be concluded that for this type of algorithm, most of the work is being done in the leaves of the call tree.

The depth of the call tree is (n).

The sum of the rows is

A question that could lead students in their investigation is:

Under what conditions is most of the work done in the leaves of the call tree? When is most of the work done in the root of the tree? When is the work spread evenly at each depth of the tree?

Another method that students can use to analyse recurrence relations is repeated substitution. To do this, the recurrence relation is repeatedly substituted into itself until a recognisable pattern is noticed. For example:

At this point, the pattern 1 + 2 + 4 + 8 + … might be observed. Students who have studied sequences and series in mathematics will be able to apply those skills here.

Detailed example

Acting out the mergesort and quicksort algorithms

Required materials:

Either one set for a class demonstration or several sets for students to do the activity in groups following the teacher’s demonstration.

• A selection of 8–12 objects that can be ordered in some way, such as containers of different sizes or weights, or playing cards.
• If varying containers by weight, it is preferable to use a mechanical balance. Alternatively, students can compare weights by hand.

Activity

• Demonstrate the process of sorting the objects using the mergesort algorithm. At each step, students draw a diagram of the objects. After the demonstration, they try to describe the process in pseudocode.

Figure 4: An example diagram
(Original image created using card images from a public domain source
English_pattern_playing_cards_deck.svg)

Repeat this for the quicksort algorithm.

In small groups, students compare and contrast the divide and merge steps of the two algorithms. Prompts could include:

• What is similar and what is different about how the two algorithms divide the input list?
• What is similar and what is different about how the two algorithms merge the results of the recursive calls?

Detailed example

Visually explore margin-maximising linear classifiers

Required materials:

The key knowledge states that students are required to understand the geometric interpretation of applying SVM binary classification to one- or two-dimensional data. Student learning activities for this topic should focus on graphical analysis of one- and two-dimensional data.

For example, a network engineer needs to detect whether a user is a person or a robot. They record the number of requests made by some known users, some of which were people and some of which were robots. These are plotted below.

Figure 5

Students use a ruler to identify where the margin-maximising linear classifier would be for this data and illustrate it onto the chart. They also label the margin and estimate its size.

They should encounter data sets that cannot be separated by a linear classifier. For example, a road traffic engineer is trying to automate the detection of abnormal traffic conditions on a highway. They collect the following records of traffic volume during peak hour.

Figure 6

Visual tools can also be used to develop an understanding of how new features can be created from existing features in data. For example, if the traffic volume data is squared and this is a new dimension, then the two sets can be linearly separated.

Figure 7