Answers.Body: <p><strong>Classics</strong></p>
  <ul>
  <li>Reverse</li>
  <li>Rotate</li>
  <li>(Advanced) <code>reverse_until</code>, <code>rotate</code> revisited, and <code>inplace_merge</code>. However, without bisects, which you don't want, they make no sense.</li>
  </ul>
  <p><strong>Pure math</strong></p>
  <ul>
  <li>DCD</li>
  <li>Binary GCD</li>
  <li>Exponentiation by squaring</li>
  <li>Fibonacci
  <ul>
  <li>Naive</li>
  <li>In linear time</li>
  <li>In logarithmic time</li>
  </ul>
  </li>
  </ul>
  <p><strong>Misc</strong></p>
  <ul>
  <li>N Queens</li>
  <li>N-bit full adder</li>
  <li>(Advanced) <a href="https://www.jmeiners.com/efficient-programming-with-components/10_binary_counter.html#L10.-Balanced-binary-reduction" rel="nofollow noreferrer">Binary counter</a>. Read the link. It is a sheer pleasure and plenty of context/motivation.</li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-14T06:00:27.850Z
Answers.LastActivityDate: 2022-09-14T06:00:27.850Z
Answers.UserDisplayName: user58697
Answers.Body: <p><a href="https://rads.stackoverflow.com/amzn/click/com/032157351X" rel="nofollow noreferrer" rel="nofollow noreferrer">Algorithms 4ed by Sedgewick and Wayne</a> have a lot of exercices and projects. You can see some of them on the <a href="https://algs4.cs.princeton.edu/home/" rel="nofollow noreferrer">book site</a>.</p>
  <p><a href="https://www.beecrowd.com.br/" rel="nofollow noreferrer">Beecrowd</a> have a lot of <a href="https://www.beecrowd.com.br/judge/en/problems/index/1" rel="nofollow noreferrer">begginer</a> and <a href="https://www.beecrowd.com.br/judge/en/problems/index/2" rel="nofollow noreferrer">ad-hoc</a> problems. Since you need something less theoretical, I think it can help you.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-06T15:03:04.717Z
Answers.Text: 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...
Answers.UserDisplayName: BenBar
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-06T17:11:20.210Z
Answers.Text: @BenBar I updated my answer.
Answers.UserDisplayName: davidbuzatto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-05T21:04:24.723Z
Answers.LastActivityDate: 2022-09-06T17:10:42.643Z
Answers.LastEditDate: 2022-09-06T17:10:42.643Z
Answers.UserDisplayName: davidbuzatto
Answers.Body: <ul>
  <li>Experimental test of the Collatz conjecture (no data: just a couple of nested loops)</li>
  <li>Experimental test that each prime is equi-distant between two other primes (corollary of the Goldbach conjecture</li>
  <li>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 &quot;*&quot; if the modulo is nonzero, space otherwise. Instant fractal!</li>
  </ul>
  <p>Random thought: algorithms are usually taught in the context of a programming language (as opposed to &quot;article in journal of algorithms&quot; 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.</p>
  <p>In that spirit:</p>
  <ul>
  <li>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.</li>
  </ul>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-06T14:56:20.083Z
Answers.Text: 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.
Answers.UserDisplayName: BenBar
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-05T13:54:51.847Z
Answers.LastActivityDate: 2022-09-05T14:13:57.400Z
Answers.LastEditDate: 2022-09-05T14:13:57.400Z
Answers.UserDisplayName: Victor Eijkhout
Body: <p>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.</p>
  <p><strong>What should be exluded</strong></p>
  <ul>
  <li>Algorithms that sort/search, because this is educated seperately.</li>
  <li>Algorithms using a tree or graph data structure, because these data structures are only for advanced courses.</li>
  <li>Algorithms that need more than one (or two) hours to teach.</li>
  <li>Algorithms which are &quot;classic&quot;. Meaning I am searching for not so well known algorithms.</li>
  </ul>
  <p><strong>What I have so far</strong></p>
  <p>The following german page <a href="https://algo.rwth-aachen.de/%7Ealgorithmus/liste.php" rel="nofollow noreferrer">Algorithm of the week</a> has some very interesting algorithms. I like especially:</p>
  <ul>
  <li><p>Algorithm 6: Pledge-Algorithm for finding the exit of a Labyrinth. Perhaps this is too complicated. The movement of the &quot;roboter&quot; 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.</p>
  </li>
  <li><p>Algorithm 13: Explaines the computation of the ISBN of books (error detection code). This algorithm does not need any data structure.</p>
  </li>
  <li><p>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.</p>
  </li>
  <li><p>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.</p>
  </li>
  <li><p>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 &quot;traveling salesman&quot; this is too artificial, because the distances between points are &quot;flying distances&quot;. 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.</p>
  </li>
  <li><p>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.</p>
  </li>
  </ul>
  <p>The following book was suggested: <a href="https://algs4.cs.princeton.edu/home/" rel="nofollow noreferrer">Algorithms 4ed by Sedgewick and Wayne </a></p>
  <p>I try to explain, why this is not exactly what a I am searching.</p>
  <ul>
  <li><p>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 &quot;there are houses on a plane and the people are arguing, where the new hospital/fire station should be build&quot;.</p>
  </li>
  <li><p>Chapter II: Sorting --&gt; I excluded this.</p>
  </li>
  <li><p>Chapter III: Searching --&gt; I forgot to excluded this, its educated together with sorting.</p>
  </li>
  <li><p>Chapter IV: Graphs --&gt; 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.</p>
  </li>
  <li><p>Chapter V: Strings --&gt; 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).</p>
  </li>
  <li><p>Chapter VI: Nice! But for my course, way too complicated. I will have a look at &quot;Particle Collisions&quot;. I am teaching quite early the collisions against the &quot;wall&quot; (only horizontal and vertical). But the collisions against other particals would be interesting.</p>
  </li>
  </ul>
  <p>To clarify: I am searching for a good <strong>problem/context</strong>. A particle collision would be still an abstract algorithm. The problem/context would be for example: Simulating how a virus distributes.</p>
  <p>Thank you for your ideas/help!
  Benjamin</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-09-09T18:52:56.180Z
Comments.Text: 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...
Comments.UserDisplayName: Solomon Slow
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-09-09T18:54:16.423Z
Comments.Text: ...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.)
Comments.UserDisplayName: Solomon Slow
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-10-13T07:15:10.040Z
Comments.Text: you may check my question & answer here for another example https://cseducators.stackexchange.com/questions/6699/what-are-good-practical-labs-and-activities-for-loops
Comments.UserDisplayName: Qiulang 邱朗
Tags: <programming><secondary-education><student-motivation><algorithms><data-structure>
Title: Searching for algorithms using array, stack, queue, List or no data structure solving interesting problems
ThreadText: # Searching for algorithms using array, stack, queue, List or no data structure solving interesting problems
  
  (Asked by: username_0 on 2022-09-04)
  
  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](https://algo.rwth-aachen.de/%7Ealgorithmus/liste.php) 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](https://algs4.cs.princeton.edu/home/)
  
  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
  
  **Tags:** programming, secondary-education, student-motivation, algorithms, data-structure
  
  > **Comments:**
  > **username_1**: 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...  
  > **username_1**: ...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.)  
  > **username_2**: you may check my question & answer here for another example https://cseducators.stackexchange.com/questions/6699/what-are-good-practical-labs-and-activities-for-loops  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_4 on 2022-09-05. Score: 3
  
  [Algorithms 4ed by Sedgewick and Wayne](https://rads.stackoverflow.com/amzn/click/com/032157351X) have a lot of exercices and projects. You can see some of them on the [book site](https://algs4.cs.princeton.edu/home/).
  
  [Beecrowd](https://www.beecrowd.com.br/) have a lot of [begginer](https://www.beecrowd.com.br/judge/en/problems/index/1) and [ad-hoc](https://www.beecrowd.com.br/judge/en/problems/index/2) problems. Since you need something less theoretical, I think it can help you.
  
  > **Comments:**
  > **username_0**: 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...  
  > **username_4**: @username_0 I updated my answer.  
  
  ---
  
  ### Answer by username_5 on 2022-09-05. Score: 2
  
  * 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.
  
  > **Comments:**
  > **username_0**: 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.  
  
  ---
  
  ### Answer by username_3 on 2022-09-14. Score: 1
  
  **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](https://www.jmeiners.com/efficient-programming-with-components/10_binary_counter.html#L10.-Balanced-binary-reduction). Read the link. It is a sheer pleasure and plenty of context/motivation.
  
  
  ---
  
  