Teaching ideas for string algorithm?

Question

When teaching algorithm (high school) I always go with some sorting & searching algorithms and believe that should be enough, or at least lay a good foundation for them.

But I have come to realize that teaching algorithms for string processing may also be necessary. For starters, a) every programming languages have the standard library for string processing. b) since we are Chinese we hit the Chinese garbled characters on webpages from time to time but kids in high school normally have a hard time to understand ascii vs unicode and all kinds encoding like UTF8, UTF16. c) I do believe they will deal with string process someday just like they will deal with sorting/searching.

So any advice how to teach string algorithm? Do I teach them KMP or some other substring searching algorithm? Do I teach them Regular Expressions, know what that is and how to use them? I don't have much experience in this and the only material I have now is https://algs4.cs.princeton.edu/50strings/ I feel it is quite difficult for high school kids.

From the comment I got I think I should make it clear my goal. I want to teach them some very basic string algorithms, i.e. some string algorithms that I will argue very programmer should know. Using sorting & searching algorithm as comparison, there are some very basic sorting & searching algorithms I think very programmer should know, elementary sorts if not Quicksort (if not Quicksort but the concept of divide and conquer), binary search, etc.

Joel Spolsky wrote an article a long time ago The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets "if you are a programmer working in 2003 and you don’t know the basics of characters, character sets, encodings, and Unicode, and I catch you ..." In 2022 now but I find the situation doesn't improve much.

What are the string algorithms very programmer should know ? Or is there any of, e.g does KMP or any substring search algorithm fit this category ?

Answer 1

Based on the question and follow-up comments, there appears to be uncertainty in your goals and student learning outcomes. If you clarify those goals, then it should be pretty apparent which string topics to cover.

Keep in mind that strings (or any other data structure, primitive data type, algorithm domain or just about anything else in computers) have no inherent value to anyone, especially students. They're a means to achieving other ends. The rule of thumb is to start with the goal, then teach only whatever is necessary for students to achieve that goal.

Perhaps your goals are to teach algorithms to improve critical thinking, prepare students for a CS degree in college and prepare them for job interviews (if job interviews still give Leetcode-style questions by the time they're entering the workforce). If so, determine their experience level and pick problems of an appropriate difficulty. Few high school students I know of are interested in or at a level where KMP or Sedgewick would be appropriate.

At a beginning level, students should be able to index, iterate, concat, split, join, slice, search, adjust case and be comfortable working with common string library functions in their language. Students in an algorithms-focused course can then reimplement these library functions from first principles. Then consider functions that build on top of these primitive operations such as palindrome and isogram detectors and command line projects like Mad Libs, Hangman ^{(possibly no longer a politically viable name)} and Wordle.

Keep in mind arrays and strings are pretty similar as sequences of characters, so you may wish to emphasize this and teach the two concepts more or less as one, especially if you're working with C.

Now, if your goal is student engagement with less of an interest in college prep, consider games, animations, creative coding and web apps. Here, teach strings on a purely pragmatic, as-needed basis rather than on an "every programmer should know" basis (paraphrasing Spolsky's quote which really refers to professional programmers in the early 2000s, not hobbyists or students). Algorithms are important, but if you're working in a high-level language and focused on high-level goals, they're a black box students can simply invoke.

Regex is probably too much, but if validation comes up in the process of making an app, I'll give students a simple regex pattern and explain the basics, like \d, ., ?, + and *. I know professional programmers who don't touch regex, so it seems safe to file away. For the CS prep folks, a bit of exposure to the concept is fine in high school, but that's about it. I don't recall using regex at all in graduate CS even though I'm the sort of person who'd be looking for opportunities to use it.

Unicode is a dry, messy industry/"real world" problem that doesn't need to be discussed much in high school. It's better to hide the ugly, dumpster fire side of programming for a bit. Unicode is a topic that regularly brings full-grown adult programmers with years of experience to tears¹. Students will have enough frustrations to keep them busy working within a well-scoped sandbox. Expand the bounds over time, try to avoid unnecessary contrivances and acknowledge when you are simplifying things, but try to keep the rails on the crib. Like dumping all of your problems and dark secrets on the first date, showing too much mess up front scares most people off.

I believe you're coming from a country and language where Unicode is a large part of everyday life. I live in the USA where we can pretty safely stuff Unicode under the table during high school and pretend it doesn't exist. Then when students enter the workforce, show them the mess, bait-and-switch style. By then, it's too late and they have to deal with uber-frustrating Unicode problems nobody else wants to touch so they can pay off their debt.

If you accept the terms and conditions and really want to go into Unicode, maybe an image-to-unicode converter or command-line interface that uses box-drawing characters would be exciting. You could maybe sneak some vegetables into the pizza if there are any pressing lessons you want students to learn. Emojis are another thing that seems fun and elegant until you try to use them in a real app and encounter the edge cases, but they can be OK for education².

^{1. See this animation of Twitter giving an internal server error when tweeting a zero-width Unicode character.}

^{2. As long as you're ready for them to inexplicably show up funny on Jane or Jimmy's computer and spend 3 hours trying to figure out why.}

Answer 2

A few ideas:

You can use bitwise operations to have students change text from lowercase to CAPS and back. It's a pretty neat illustration of some of the cleverness that went into the original ASCII table.

You could have them try to convert an int to a string manually, and back.

You could have them create a standard, four-function calculator. I once gave this lab as a way to teach students how to do GUIs in Java, but I quickly discovered that what I had actually given was a String processing lab, because that was where the students had all of their challenges.

There is a lot of processing around the string in the screen. What happens on the screen, for instance, as you type the sequence 0 0 0 - 1 0 = . . 0 0 5 . =? You would want to provide a pre-coded interface that already has pressable buttons, and enough demonstration code to show how to get a button to change what's on the screen and the current "remembered" number. (The On/Off button is a good one to implement in advance as model code.)

Answer 3

In modern systems we have separated text processing into two levels.

At the high-level, we deal with "strings", which have an opaque underlying encoding. This is a useful place to teach things like sorting, searching, and find-replace. It could also involve regex, in some sort of lesson looking for patterns in text fragments.

At the low-level, we have text-encodings, such as ASCII, UTF-8, UCS-2, etc. etc. I recommend avoiding this in any youth programming class, unless students are pushing for it, or you have a very specific text-processing task in mind. Character encodings (outside of ASCII) are very very complex, and have many dirty real world issues that are not suitable for students doing early programming education. They can learn this if they are doing advanced university research or paid programming.

Answer 4

Right-justify text in a monospaced font. If you give the input as a long string, this requires searching for spaces, breaking into substrings, and then inserting more spaces.