Martian substructures

🕑 2 min • 👤 Thomas Graf • 📆 May 06, 2020 in Discussions • 🏷 fun allowed

Sometimes students get hung up on the difference between substring and subsequence. But the works of Edgar Rice Burroughs have given me an idea for an exercise that might just be silly enough to permanently edge itself into students’ memory.

Enter John Carter, Jeddak of Jeddaks, Warlord of Mars, depicted here with his wife, Dejah Thoris, Princess of Helium, daughter of Mors Kajak, who is Jed of Helium and son to Tardos Mors, Jeddak of Helium.

John Carter and Dejah Thoris, as portrayed by Frank Frazetta
John Carter and Dejah Thoris, as portrayed by Frank Frazetta

And here we have two of John Carter’s most loyal friends. First, Tars Tarkas, Jeddak of Thark.

Tars Tarkas helps John Carter in his fight against the Plant Men of the Valley Dor, at the end of the River Iss; art by Michael Whelan
Tars Tarkas helps John Carter in his fight against the Plant Men of the Valley Dor, at the end of the River Iss; art by Michael Whelan

And next Kantos Kan, Jedwar of the Heliumetic navy.

Kantos Kan, in a Barsoomian painting of unmatched verisimilitude
Kantos Kan, in a Barsoomian painting of unmatched verisimilitude

Kantos Kan has the rare distinction of having a last name that is a substring of the first name. After all, Kantos = Kan + tos.

That’s not the case for Tars Tarkas. While the first name and last name share a common prefix Tar, there is no string that we can put before or after one of those strings to get the other one. But Tars is a subsequence of Tarkas, as the latter is Tar + ka + s. We can build Tarkas from Tars by splicing in additional material.

So remember, substrings are Kantos Kan strings, and subsequences are Tars Tarkas sequences. Okay, your turn. For each one of the following pairs, say whether one is

  • a Kantos Kan string of the other,
  • a Tars Tarkas sequence of the other,
  • neither.
  1. Jed and Jeddak
  2. Tars and Thark
  3. Jeddak and Jedwar
  4. Thoris and Tardos Mors
  5. Tars and Tardos Mors
  6. Dejah Thoris and Dor

Bonus exercise: Explain why I didn’t allow a fourth option “both” in the exercise.

Bonus bonus exercise: Design similar exercises for other entries from Appendix N.