1
$\begingroup$

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 ?

$\endgroup$
16
  • $\begingroup$ Ultimately I believe that it heavily depends on your goal. How did you come to a conclusion that teaching algorithms for string processing may be necessary? I can see a curriculum that heavily relies on them, but I also can see a curriculum that is completely agnostic to the fact that some algorithms can be applied for demanded text-based problems. Teaching algorithms helps with developing logical thinking, but to divide and consider them into such specific groups requires either a concrete goal or a lot of free time. Not assumptions. $\endgroup$
    – Fureeish
    Sep 8, 2022 at 6:20
  • $\begingroup$ I said in my question, "teaching algorithms for string processing may also be necessary..." That is my goal and I had thought it was quite obvious but your comment said otherwise. $\endgroup$ Sep 8, 2022 at 9:50
  • $\begingroup$ My counter argument is that what is your goal to teach "sorting & searching algorithms" or any algorithm then? $\endgroup$ Sep 8, 2022 at 9:52
  • 2
    $\begingroup$ @Qiulang邱朗 I think that Fureeish is getting at missing information -- you appear to be missing a goal. "String algorithms" is too broad, especially since all that computers do really reduces to string manipulation. What skills are you hoping they strengthen? What do you want them to be able to do? What do you want them to understand? What do you wish them to learn? $\endgroup$
    – Ben I.
    Sep 8, 2022 at 15:15
  • 2
    $\begingroup$ "not prepare them for jobs but to whet their interests" and "better to know" seem somewhat at odds to me. Regardless of your goals, unicode seems likely to destroy kids' interest in programming. $\endgroup$
    – ggorlen
    Sep 9, 2022 at 3:19

4 Answers 4

4
$\begingroup$

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 tears1. 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 education2.

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.

$\endgroup$
10
  • 1
    $\begingroup$ I wish I had my StackOverflow reputation here so I could give additional points to this answer... $\endgroup$
    – Fureeish
    Sep 9, 2022 at 17:53
  • $\begingroup$ @Fureeish You can upvote once you have 15 rep. You far exceed that! Feel free to vote. $\endgroup$
    – Ben I.
    Sep 9, 2022 at 17:59
  • 1
    $\begingroup$ Thanks for the detailed answer. It gives me a lot to think about. As for the goal as I said several times I just wanted to teach them some basic string processing algorithm that every programmer should know. But I find this statement still causes quite some confusion. Maybe that is because there is no such thing in string process that everyone should know as compared to array, hash table, binary search, elementary sorts which I would argue that most of us would agree that is the very basic everyone does programming should know. $\endgroup$ Sep 10, 2022 at 4:10
  • 1
    $\begingroup$ No pressure to accept at all and thanks for the response. I would be very careful with the "every programmer should know" phrase. To me, it's all about goals, and there are few universal truths. Sure, all programmers should know what strings are and how to call library functions to do basic manipulation on them, but (depending on their goals) they may not need to know this right now, in high school. Many programmers who are writing CRUD apps or UIs probably don't need to know a whole lot about how string algorithms work unless they need them for a CS degree or job interview. $\endgroup$
    – ggorlen
    Sep 10, 2022 at 4:21
  • 2
    $\begingroup$ Rather than asking "what are the string skills every programmer should know?", why not "what are the goals of my course and which string skills will my students need to achieve these goals?" $\endgroup$
    – ggorlen
    Sep 10, 2022 at 4:27
2
$\begingroup$

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.)

$\endgroup$
1
  • $\begingroup$ I think another exercise that can go with lowercase/uppercase is to implement isalpha() by themselves. Several programming languages have builtin isalpha(). $\endgroup$ Sep 13, 2022 at 6:13
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yes, as other answers have suggested I won't touch text-encoding, I won't touch regex either as @ggorlen suggested. So do you have specific example for high-level string algorithm ? $\endgroup$ Nov 10, 2022 at 8:51
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.