2
$\begingroup$

rI am a teacher in germany (high school) and I am searching for algorithms, that solve interesting problems using no data structure or linear data structures only. The goal is to motivate the students and to show them use cases which are not artificial. The algorithm need to be easy to understand and should be explainable/programmable in one (or two) lessons.

What should be exluded

  • Algorithms that sort/search, because this is educated seperately.
  • Algorithms using a tree or graph data structure, because these data structures are only for advanced courses.
  • Algorithms that need more than one (or two) hours to teach.
  • Algorithms which are "classic". Meaning I am searching for not so well known algorithms.

What I have so far

The following german page Algorithm of the week has some very interesting algorithms. I like especially:

  • Algorithm 6: Pledge-Algorithm for finding the exit of a Labyrinth. Perhaps this is too complicated. The movement of the "roboter" is easy, but one has to prepare the labyrinth software and the students program only a part of the software. Therefore the students need to get along in an already programmed code, which might be too difficult.

  • Algorithm 13: Explaines the computation of the ISBN of books (error detection code). This algorithm does not need any data structure.

  • Algorithm 33: Detects in an election, if some person has over 50 % of the votes using a stack only. The algorithm is quite clever and does not count the votes for each person.

  • Algorithm 36: Schedules a tournament of n teams (n even) where each team has to play against all other teams. The algorithm does this in the minimal amount of rounds (n-1) and in each round there are n:2 parallel games. This can be implemented with a queue or a list.

  • I also like Algorithm 41 (simulated annealing) but this may be too difficult, it depends on the problem. I don't like the use case "traveling salesman" this is too artificial, because the distances between points are "flying distances". If one takes real places - e.g. from the area the stundents know - on a map, then it gets to complicated, because only strees can be used.

  • I also like Algorithm 42 (smallest circle containing a set of points), it is randomized and very clever, but the implementation would be far too difficult.

The following book was suggested: Algorithms 4ed by Sedgewick and Wayne

I try to explain, why this is not exactly what a I am searching.

  • Chapter I: Everything is abstract here, there is no context. The data structures are there but they are not used to solve anything. I really like the 3-Sum problem, for teaching nested loops. But also, here is missing the context. What is beeing solved with 3-sum? Out of my head would be the smallest circle of a set of points. But this is still no context. The context would be "there are houses on a plane and the people are arguing, where the new hospital/fire station should be build".

  • Chapter II: Sorting --> I excluded this.

  • Chapter III: Searching --> I forgot to excluded this, its educated together with sorting.

  • Chapter IV: Graphs --> I excluded this, because its a beginner course. I really like to teach dijkstra, breadth-first-search, etc... there are many cool real life examples.

  • Chapter V: Strings --> Nothing there I see, which has a nice context. Many algorithms there need trees/graphs. Although I favour Huffmann-Encoding. Implementing it is really hard. That would be possible at the end of the course (3rd year).

  • Chapter VI: Nice! But for my course, way too complicated. I will have a look at "Particle Collisions". I am teaching quite early the collisions against the "wall" (only horizontal and vertical). But the collisions against other particals would be interesting.

To clarify: I am searching for a good problem/context. A particle collision would be still an abstract algorithm. The problem/context would be for example: Simulating how a virus distributes.

Thank you for your ideas/help! Benjamin

$\endgroup$
3
  • $\begingroup$ Re, "I don't like the use case "traveling salesman" this is too artificial." I read about one interesting real-world application of traveling salesman: It was an astronomy team, using an old was-once-cutting-edge-but-no-longer telescope to do a nightly "sky survey." They wanted the scope to dwell on a few hundred different targets each night for maybe a minute each. They had a different list of targets each night, and they wanted to minimize the amount of time spent moving from target to target. Problem is made more interesting by the fact that the search space is spherical rather than... $\endgroup$ Sep 9, 2022 at 18:52
  • $\begingroup$ ...planar, and also by the fact that different parts of the sky are only visible at certain times during the night (stars are rising in the east and setting in the west throughout the night.) $\endgroup$ Sep 9, 2022 at 18:54
  • $\begingroup$ you may check my question & answer here for another example cseducators.stackexchange.com/questions/6699/… $\endgroup$ Oct 13, 2022 at 7:15

3 Answers 3

3
$\begingroup$

Algorithms 4ed by Sedgewick and Wayne have a lot of exercices and projects. You can see some of them on the book site.

Beecrowd have a lot of begginer and ad-hoc problems. Since you need something less theoretical, I think it can help you.

$\endgroup$
2
  • $\begingroup$ I read the chapter titles and the short description. This is all context I would use to teach a course in university not in school. I am searching for a direct real life connection/benefit. And this is abstract context. I am searching for examples using that abstract context to solve something. And this is the hard part. I am editing my post... $\endgroup$
    – BenBar
    Sep 6, 2022 at 15:03
  • $\begingroup$ @BenBar I updated my answer. $\endgroup$ Sep 6, 2022 at 17:11
2
$\begingroup$
  • Experimental test of the Collatz conjecture (no data: just a couple of nested loops)
  • Experimental test that each prime is equi-distant between two other primes (corollary of the Goldbach conjecture
  • Store Pascal's triangle in a linear array (hey, we don't have triangular arrays and a square array is wasteful) and print the values modulo some int. In fact, print "*" if the modulo is nonzero, space otherwise. Instant fractal!

Random thought: algorithms are usually taught in the context of a programming language (as opposed to "article in journal of algorithms" style) so you can not entirely divorce the discussion of an algorithm from a discussion of the programming language. And then there are algorithms that are not overly deep, but where the implementation is interesting.

In that spirit:

  • Write a zero finder, first by bisection, then by Newton. Implementation aspects: 1. dealing with a function pointer 2. in the Newton method dealing with the fact that you may not have the derivative function.

See my point? Given a function it's not hard to write a program to find its zeros (or at least one), but writing a general purpose piece of software is harder and more interesting.

$\endgroup$
1
  • $\begingroup$ Thank you for your toughts. I like and do the Collatz conjecture in lower classes. Everything else is "too mathematical"... it would destroy the motivation, except for maybe 1-4 students of 25. I do primes algorithmns.... but I am searching for algorithmns, where the students benefit in their real life. Making a tournament list, is a direct benefit. Understand the ISBN of a book too. $\endgroup$
    – BenBar
    Sep 6, 2022 at 14:56
1
$\begingroup$

Classics

  • Reverse
  • Rotate
  • (Advanced) reverse_until, rotate revisited, and inplace_merge. However, without bisects, which you don't want, they make no sense.

Pure math

  • DCD
  • Binary GCD
  • Exponentiation by squaring
  • Fibonacci
    • Naive
    • In linear time
    • In logarithmic time

Misc

  • N Queens
  • N-bit full adder
  • (Advanced) Binary counter. Read the link. It is a sheer pleasure and plenty of context/motivation.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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