17
$\begingroup$

I am to teach Algorithms and Data Structures. There are lots of books that teach how to do algorithms in language X or Y. But I would like to teach algorithmic thinking per se, independent of the underlying programming language.

Do you know any book or Internet resource for that? Especially that contains problems and exercises in the style of high school mathematics problems.

$\endgroup$
8
  • 13
    $\begingroup$ This is like wanting to train swimming, but without a body of water. Habitually applying algorithmic thinking in non-programming domains or situations comes from having efficiently honed it via programming, not vice versa. $\endgroup$
    – Kaz
    Aug 26, 2021 at 7:03
  • 6
    $\begingroup$ You could use English, but you'd end up structuring & formalising it to the point that it was basically pseudocode, which is arguably a programming language since you can program carbon units with it. So I'm not sure what you're asking is even possible. $\endgroup$ Aug 26, 2021 at 17:37
  • $\begingroup$ @Kaz That's just silly, go tell the ancient greeks that. en.wikipedia.org/wiki/Timeline_of_algorithms $\endgroup$
    – TCooper
    Aug 26, 2021 at 23:19
  • 2
    $\begingroup$ Pencil-and-paper arithmetic uses algorithms, such as long division. Students who can perform long division already have an algorithmic concept. Symbolic games and puzzles include algorithmic concepts. These things all have one thing in common: they provide some representation of the data structure, but the manipulations of it to search through the possible space are left to the human. $\endgroup$
    – Kaz
    Aug 26, 2021 at 23:48
  • 2
    $\begingroup$ If you want high school Mathematics style, there is this book The Teaching & Learning of Algorithms in School Mathematics. 1998 Yearbook eric.ed.gov/?id=ED419669. I just bought it out of curiosity or maybe as intellectual exercise $\endgroup$
    – ShAr
    Aug 29, 2021 at 12:58

9 Answers 9

33
$\begingroup$

When I attended a Mind, Brain, and Learning conference a few years ago, a lecturer posed the following question (paraphrased):

If I ask you to figure out the cube root of a number like 150 in your head, and ask Albert Einstein or Richard Feynman to do the same, they will probably come up with the answer faster than you do. But who will be using more of their brain to do it? You or the great physicists of the era?

The answer, he went on to explain, was that you would be using more of your brain to do it. He went on to explain that experts use surprisingly small numbers of neurons to accomplish tasks within their own field of expertise. Experts have invested a great deal of time and calories into streamlining those systems, and making them extremely efficient.

Novices, by contrast, engage relatively vast swaths of their brains in order to accomplish tasks.

The streamlining that the experts have done is mastering abstractions.

To my way of thinking, your stated goal sounds very nice, but it doesn't really work.

The problem is that we naturally move from concrete to abstract, which is done in three parts: (1) we learn how something works, (2) we make the observation that "this is kind of like that" and then (3) we continue with the questions, "what other things are like these things? What are the common features in how they behave or function?"

Within the brain, it is actually the same three part process: (1) understand a system, (2) use the common parts of two systems to create a streamlined version of their common, essential parts, and then (3) connect that streamlined system to many other ideas.

(Please note the order in which I created that abstraction for you in the previous two paragraphs, and consider whether it would have been somehow clearer if I reversed them.)

The second and third phases are actually cyclical. When we connect to a new system (phase 3), we frequently wind up revisiting the second phase as the new, connecting ideas provide insight into the abstraction that we didn't notice before. Also notice that the order remains concrete to abstract even here, when we already have a good, abstract construction.

When we do all this, we are building our abstraction, which can also be described as winnowing down a system to its essential features. This process is insanely useful! (More on that in a bit.)

We don't work from abstract to concrete naturally, unless we already have good, firm ideas of the particular abstract systems being used.

If you want to get a sense of how hard this is for humans, notice how we struggle to explain the process of quantum computing, which puts us all in a position of having to begin abstractly, and attempting to concretize from there. It's so hard for precisely this reason. Without concrete systems that behave like the quantum systems, it is almost impossibly difficult for us to build up useful abstractions in the first place.

Why we frequently want to teach this way

You're not at all alone in wishing to teach the abstractions from the outset. (It is a bit of a perennial issue here on CSEducators, actually.) Teachers often really want to begin from the abstraction. It's instinctive!

After all, a firm abstraction is absolutely wonderful. It is a little key that opens vast swaths of thought to the key holder.

The abstraction is also much simpler than any of the derived systems, which have little details that can be hard to understand without thoroughly understanding the abstraction that makes the whole system work in the first place.

Once you have the abstraction in place, all of those confusing little details hardly need to be remembered. They can be quickly and trivially re-derived when we need them.

It makes sense that, almost as soon as we learn a good abstraction, we switch over to using it very heavily in our thinking. It vastly simplifies and streamlines our thought process when faced with complex systems. Win-win!

It is natural to want to get your students to think this way as well. After all, if they can see the bigger picture the way that you do, they will be able to take advantage of how simple it all is, just like you do. Why not start there, show them the beautiful simplicity, and then show them how trivial it is to now understand a lot of wonderful things?

Hopefully you can see the answer: the students can't do it. That mode of thinking is unlocked only by having at least one, and hopefully more, concrete, well-understood examples first, because those concrete examples are what permit us to comprehend the key secondary features.

Looking at it from a neural basis, the novice mind lacks the information that must be winnowed and simplified in order to create the streamlined pathways.

We teachers can absolutely help guide students along the path to these kinds of abstractions. But the first step to make it manageable for a human brain is to make sure that brain has a few concrete examples to work off of.

What we can really do

So how can you help your students get to the abstract part? You (1) journey through a topic concretely. You (2 and 3) regularly point out when something they're learning is similar to something they've already learned. You regularly discuss the abstract elements that are coming up.

Start concrete, move slowly towards the abstract.

It feels positively glacial to work this way, but that's partly an illusion. We simply forget how long it took us to find, winnow down, and make our own beautiful abstractions. The slow pace is really just the time it takes to build the abstraction in the students mind.

$\endgroup$
11
  • 1
    $\begingroup$ Though if you want to look at a really prodigious mental calculator, I'd suggest John von Neumann. He looked to have the ability innately like a savant as it was there ever since his youngest years; meaning it was genetic pot luck - lots of it, like winning the jackpot. For the rest of us without such luck to be able to "just know", then it has to be built up, as you suggest, like a building. But in this case, the question I believe could be asked as "can you 'build that building' without a programming language specifically?" not "can you skip building the building?" $\endgroup$ Aug 25, 2021 at 23:58
  • 1
    $\begingroup$ (Note: just to get in before anyone objects to my characterization, yes JvN also had to go through much rigorous education and learning and stuff too, but it was all atop that innate foundation. Which is what put him above all the rest, even others considered "geniuses" of his time. It's like everyone's building a building, but his was being built atop a mountain. Guess which one reaches higher, and/or who has to build more and who has to build less?) $\endgroup$ Aug 25, 2021 at 23:59
  • $\begingroup$ @The_Sympathizer TIT somehow JvN "won the genetic lottery" is dangerous and closeminded. It's not even clear if humans compared to those that don't have cognitive disorders can be geniuses to other people in the sense that they are strictly more intelligent on the basis of genetics. IQ tests basically never transfer to other groups of people, and even the idea of thinking about numbers linearly is not how humans naturally think about numbers. What does appear to happen, is that all these "prodigies" are well exposed to ideas and practice in these fields well before anyone else does. $\endgroup$
    – Krupip
    Aug 26, 2021 at 18:50
  • 3
    $\begingroup$ @The_Sympathizer Often, a child has a slight inclination for something and an adult sees it and is amazed, and feels they have a "genius" on their hand, then gives that child all the resources in the world to succeed in that thing. JvN and co's "intelligence" is far more likely explained by the opportunity complex than anything else. If you taught an 8 year old calculus, would you not expect to be better at calculus than other kids? Assumptions otherwise are pedestal lifting, lionizing and hubris. It's the same sort of thinking that lead people to believe in superior races of people. $\endgroup$
    – Krupip
    Aug 26, 2021 at 18:54
  • 1
    $\begingroup$ @lightning_missile I've never used SICP for beginners, only for 3rd year students. Is that even a thing? It seems inappropriate to me. OTOH, some college and university classes try to winnow out students that aren't exceptional in their intro classes, so maybe that's a good technique to eliminate students who would need a lot of support. $\endgroup$
    – Ben I.
    Aug 27, 2021 at 19:32
9
$\begingroup$

About 20 years ago, I interviewed at a rather well known American software company. I met with about a dozen people over a day that lasted from 8:30 to 4:30.

One of the questions was to come up with an algorithmic solution to blindly traversing a space that looked like this, from one end to the other:

+----+
|    |
|    |
|    +---------+
|              |
+---------+    |
          |    |
          |    |
          +----+

The solution it to take a step forward. If you bump into anything, rotate to the right (or to the left, just be consistent). if you bump into something again, rotate 180 degrees. If you don't bump into anything after any of these actions, take another step forward. You'll eventually get to the end.

You could draw something like that on the board and let suggest possible solutions. Then you could see if the algorithm works in other maze-like shapes.

I think coming up with simple exercises like this is a good way to stimulate algorithm thinking.

You could also do this in groups, drawing the outline on the floor with tape. Initially, a guider guides the person, giving instructions to a blind-folded (or pretend blind-folded) walker. Once the walker gets to the end, the group gets to figure out how the walker could do this algorithmically, without a guider.

Update: Another Tape-On-The-Floor Example

Tape off N cells in a row, each big enough for someone to stand in. Then tape off one more square not part of the array of cells. Label that last one T for temporary.

+----+----+----+----+----+----+----+---'+
|    |    |    |    |    |    |    |    |
|    |    |    |    |    |    |    |    |
|    |    |    |    |    |    |    |    |
+----+----+----+----+----+----+----+---'+

      +----+
      |    |
      |  T |
      |    |
      +----+

Randomly select N students and put them in the cells of the array. Tell them that the goal is to sort them out by height. Give them a few rules.

  1. A cell (including the temporary one) can be empty or full
  2. A student must always be in a cell (or be transitioning between cells)
  3. Only one student can move at a time.

See if they come up with a sorting algorithm. If not, coach them into coming up with a bubble sort. The temporary cell is to enable swapping (otherwise rule 3 is broken).

Note, you are also talking about variables and possibly memory.

Once they get sorted. Have them apply the same algorithm with a different comparator function and sort them out by first name.

Then, get random stuff from the classroom (a pen, a stapler, a sheet of paper, etc). Now they can apply the same algorithm to different types with a different comparator.

I'm trying to think of how to refactor out the swapping function.

$\endgroup$
7
$\begingroup$

When I was about eight years old, my teacher asked the class to describe fool-proof ways to make a cup of tea, or to strike a match then use it to light something like a gas-flame or a cigarette.

How would that not meet your citeria?

$\endgroup$
4
  • $\begingroup$ For me it was drawing a smiley face on a whiteboard. Imo this is the correct answer. This really shows how the "programmer mindset" is. $\endgroup$ Aug 25, 2021 at 21:57
  • 10
    $\begingroup$ For a concrete example of how such teaching might go, try the "can you teach me to make a PB&J sandwich?" video. $\endgroup$ Aug 26, 2021 at 4:29
  • $\begingroup$ Tnx @Danielwagner that was worth an answer! $\endgroup$
    – Rushi
    Aug 26, 2021 at 16:54
  • 1
    $\begingroup$ Yes, I remember the days. You could not see the black-board for all the smoke. $\endgroup$ Aug 28, 2021 at 9:30
4
$\begingroup$

But I would like to teach algorithmic thinking per se, independent of the underlying programming language.

The current classic book is

"Introduction to Algorithms" Third Edition by Thomas H. Cormen (WorldCat)

It is a collage level book but then again so are computer algorithms.

$\endgroup$
9
  • 2
    $\begingroup$ The OP asked for something other than "books that teach how to do algorithms in language X or Y". CLRS is a book that teaches how to do algorithms in pseudocode. How is this not a "book that teaches how to do algorithms in language X or Y"? Except the added disadvantage that you can't even run the code in the book to see how it works. $\endgroup$ Aug 25, 2021 at 19:24
  • 1
    $\begingroup$ @JörgWMittag Please read the question again, carefully. The OP states Do you know any book or Internet resource for that? $\endgroup$
    – Guy Coder
    Aug 25, 2021 at 19:44
  • $\begingroup$ The point is when u teach using pseudo code, u concentrate on the ideas irrelevant of the Programming language the students learn/use that could vary through the years. What usually happens when I used to teach is the TA in the lab (there r secs&labs associated with the course) might help the students in the their assignments of turning pseudo code to program. The language differs thru the years (or faculties)Pascal,C,C++,Java. However, now Python is much easier since it's Algorithmic in nature; both MIT & Tim Roughgarden use it in their Algorithms & Data Structures courses $\endgroup$
    – ShAr
    Aug 26, 2021 at 9:09
  • $\begingroup$ Let me add that, the idea that I give u the grade on this course according to ur understanding of the concepts choosing the right algorithm technique or data structure to approach the problem irrelevant of ur practice or excellence in programming skills as a developer, that's the responsibility of other courses. If I am a company to hire u according to ur grades either in a developer or a designer job I should know which evaluates which, although they're connected. $\endgroup$
    – ShAr
    Aug 26, 2021 at 9:16
  • 1
    $\begingroup$ @BlokeDownThePub: Prolog (it's pretty purely declarative), AWK, the combination of Lex and YACC. Not every problem is best described/solved by a user-written algorithm. $\endgroup$
    – Flydog57
    Aug 26, 2021 at 19:54
4
$\begingroup$

My go-to answer for this question would be CS Unplugged, an open-source "collection of free learning activities that teach Computer Science through engaging games and puzzles that use cards, string, crayons and lots of running around". It has been around and maintained for at least 18 years now... and even if it may be a bit low-level for high school students, I expect that you can at least find inspiration there.

$\endgroup$
3
$\begingroup$

The "Introduction to Algorithms" text by Cormen, Leiserson, Rivest, and Stein uses pseudocode (so, not any particular programming language), but assumes an introductory programming course as a prerequisite.

If you want students to develop algorithmic thinking skills as part of an introductory programming course, consider the textbook "Introduction to Computation and Programming using Python" by John Guttag. Many interesting problems are discussed there, including bisection search, Newton-Raphson, and sorting and searching algorithms. Most introductory programming texts place too much emphasis on syntax, whereas this book by Guttag introduces a minimal amount of Python syntax and focuses on computational and algorithmic thinking.

$\endgroup$
2
$\begingroup$

check this https://youtu.be/8hly31xKli0 Algorithms and Data Structures - Full Course for Beginners from Treehouse

freeCodeCamp.org

$\endgroup$
0
2
$\begingroup$

My go-to source for algorithmic thinking is The Science of Programming by David Gries (one of my mentors in CS). Algorithms are expressed in an abstract language that was also used (and made popular for exposition) in the papers of Dijkstra.

The basis of the algorithmic thinking was to examine preconditions and postconditions for a problem and to work from either end toward a solution. The technique is useful, also, in establishing the theoretical efficiency of an algorithm.

Unfortunately, the book is hard to come by, and expensive if you can find it.

$\endgroup$
2
$\begingroup$

I preferred to wrap up what in the comments & what is new here

This course is usually called Algorithms Design & Analysis, I haven't taught say in 10 yrs but those are classics:

-The famous K-nuth The art of Computer Programming vols 2,3

-Sartaj Sahni book, I can't remember the name now, but it exactly explains the point; it starts with an outline of the main techniques hill climbing, dynamic Programming, Divide-and-Conquer,...

-The Hardest Problems by Sara Baase, but I don't recall now if this is under-graduate or post-graduate (sorry the book name is Computer Algorithms: Introduction to Analysis & Design, it is just that chapter about P, NP, NPC,... we copied when were students 30yrs ago and is just became like built in my mind)

-The grey book with navy blue tree leaves on it, probably by Ullman Hopcroft; sorry I can't remember the exact title.

»»» In all cases programming languages differ in nature; I mean sure you can realize there's some differences between C++, Java, Python,...

We do not want the student to mix the properties of the language ( for example what's easy & hard in it), the difficulty of coding with the abstract complexity of the Algorithm you are using.

That's like a basic concept when you teach algorithm to explain the difference between the complexity of different algorithms Vs the running time of different implementations of the same algorithm

I also found this book, although for high school, it might give an intuition of what you are asking about, or was it your original starting point??? https://www.amazon.com/Teaching-Learning-Algorithms-School-Mathematics/dp/0873534409 https://eric.ed.gov/?id=ED419669

$\endgroup$
0

Your Answer

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

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