Scrabble tiles: each set should consist of multiple letters, multiple instances of the same letter, though not every letter need have the same number of instance. But each set should contain a fair number of "repeats."
If attendance allows, participants can work in groups.
Outline
Define palindrome; discuss as example of computational structure (something defined by a strict procedure, an algorithm).
Each group/participants (g/p) creates a palindrome. You don't have to use all your tiles. Your palindrome doesn't have to be a word.
Share and discuss results. What cases can we identify?
Even number of letters.
Odd number of letters.
Single letter (edge case).
Define the (computational) problem: Is a given sequence a palindrome?
A sequence will consist of at least one letter/tile.
The program should return a "true" value if the sequence is a palindrome, regardless of how many letters it contains. Otherwise, it should return a "false" value.
Each g/p creates a "program": a list of logical instructions. The following rules (handout) should guide your process:
You can use any number of variables.
A variable can hold single letters, sequences of letters, or numbers.
A variable can also be null, e.g., empty, if it holds no value.
You can modify variables:
replace one letter or number with another;
insert a letter into a sequence, either at the beginning or the end;
do any math with numbers you like.
You can compare two variables, testing for equality, greater than, or less than.
Two sequences are the same if they have the same letters in the same order.
You can find the length of a sequence, the result of which operation will be a number.
You can move backwards and forwards through a sequence, but only one letter at a time.
You can keep track of where you are in a sequence using a variable to record either the current letter or its numeric position relative to the beginning of the sequence.
You can do any of the above operations conditionally, that is, in response to whether a particular comparison between variables is "true" or "false."
Before g/p's start working on the exercise above, it might be useful to demonstrate what is meant by variable as well as by the last three rules. For example, model a program to identify if a letter appears twice in a row in the sequence, using two variables, one for the current letter, one for the last letter, with loop and conditional.
G/p's can write their programs either as a list of instructions or as a flow chart. Demonstrate the above example with a flow chart.
Each g/p exchanges their program with another g/p. Test the program:
Does it work?
Does it work for all cases?
Does it follow the rules?
How could it be improved?
Step through implementation in Python, using Google Colab.
If there is enough time, repeat the exercise for run-length encoding.
Run-length encoding is a method whereby, for a given sequence of letters, each subsequence of repeated letters is replaced by one instance of the repeated letter and a number indicating the length of the subsequence. So "aaabbcdddd" would be encoded as "a3b2c1d4", "abcd" would be encoded as "a1b1c1d1", and "a" would be encoded as "a1".
Write a program to produce the run-length encoding of a given sequence.
Ideas for Practice Session 1
Constraints for the Scrabble exercises:
Palindrome problem
Run-length encoding
Grouping data