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
