<p>One small, but significant, algorithm is to find Euler's Number.</p>

<p>The irrational number $e$, also called Euler’s number, is approximately <code>2.71828</code>.  The number is significant both to the <a href="https://en.wikipedia.org/wiki/E_(mathematical_constant)#In_computer_culture" rel="nofollow noreferrer">culture of computing</a> and has a role in such functions as computing continually compounding interest.</p>

<p>Euler proved that this number was irrational by showing that it was equal to the infinitely expanding series $1 + \frac{1}{1} + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!}$…</p>

<p>Ask students, then, to create a function that, given a number of iterations, returns the approximation of $e$ given by that many steps.</p>

CC BY-SA 3.0
2017-12-15T00:39:36.220Z
Actually, approximating any infinite series could be adapted to this idea. Euler is interesting, however, in that both the sum and the factorial need to be captured in the same loop.
Buffy
CC BY-SA 3.0
2017-12-15T10:44:56.173Z
Possibly related: http://www.smbc-comics.com/comic/ellipsis
Buffy
CC BY-SA 3.0
2017-12-15T00:29:55.170Z
2017-12-15T00:29:55.170Z
Ben I.
<p>The Dutch National Flag problem is linear in running time. Essentially sort an array with only 3 distinct values each of which may appear 0 or more times. (not length 3). You are allowed only one pass over the array, so the solution is a single while loop with some prior initialization. </p>

<p>It was probably originally posed by Dijkstra. It is mentioned in David Grits's <em>The Science of Programming</em> where it can be solved very nicely by posing pre and post conditions using David's ideas of finding invariants from pre and post conditions. </p>

<p>You can also make it a simple object oriented problem if you like by using objects as the array elements, for example. </p>

<p>A more interesting formulation of the problem refers to the Dutch National Flag which is a Tricolor: Red over White over Blue. You have an array that has some jumbled up red and white and blue cells, zero or more of each. You want to move all of the red cells to the left end, all of the blue cells to the right end, with the white cells in the middle. The restriction is that you may make only a single pass over the array. The correct solution is very creative and demonstrates the power of loop invariants. </p>

<p>I have mentioned this problem in answers to other questions here. A search for "dutch" on the questions page will reveal them. </p>

<p>Solving it without hints can provide a gigantic a-ha moment for almost everyone. </p>

<p>If students can do the classic version, they can also think about a modification that will handle 4 values instead. From that you can talk about the inherent complexity of sorting values from any finite set. </p>

CC BY-SA 3.0
2017-12-15T00:28:45.203Z
2017-12-15T01:04:49.633Z
2017-12-15T01:04:49.633Z
Buffy
<p>A variant on the ENIGMA machine encryption works well in a single loop, and is sufficiently complex to give students a real challenge.</p>

<p>The core idea of the ENIGMA machine for this assignment is that (1) a number is given as an initial key, and (2) every prior letter used influences how the next letter will be encrypted.</p>

<p>So, use a modular circle of encryptable characters (I chose ASCII 32 (<code></code>) to 126 (<code>~</code>), and just like a Caesar cipher, take your first letter and move it over by the <code>key</code> values.  But now modify <code>key</code> itself by adding the ASCII value of the inputted letter that you just encrypted to it.</p>

<p>Unstated in that description is the idea of creating a modular circle that doesn't begin from 0.  This is a pretty complex idea for students at this level to work with, and it helps to give them some guidance in this department.</p>

<p>Following this formula with the initial key <code>16</code>, the statement</p>

<blockquote>
  <p>Four score and seven years ago our fathers brought forth on this continent, a new nation, conceived in Liberty, and dedicated to the proposition that all men are created equal.</p>
</blockquote>

<p>Should get you:</p>

<pre><code>Vf|0Pdhx,2RTch)=CZ`o0JPRey:&lt;DTt%;Nnuw-6&lt;Oc$':J`hq'GN^q'0P`o0ENXl-1APeo~%4Iu68Xgm&amp;FUWlv'6b#'7FJPZqw|=GVvcmpv*?Y&amp;FHW\|"(-7;=RX]}3Ccx"(HYl|.&gt;R\q{,;[py{1QS`m.&lt;BQqs'-MQdjl"(-MSe{}+Y 
</code></pre>

<p>Ask students to similarly create a <em>decrypt</em> method, but offer far less guidance than you did for encrypt.  It will require them to make sense of all of the mathematical operations that they performed in encrypt in order to successfully undo it.</p>

<p>You can also provide them with a few <em>mystery strings</em> to uncover.  The first student who successfully follows the directions given by the mystery strings gets some sort of prize or extra credit.  (The mystery strings themselves explain this; no need to give the secret away in advance.)</p>

CC BY-SA 3.0
2017-12-15T01:06:33.950Z
There is an opportunity here for connecting the problem to History. In HS, students may simultaneously be studying the history of the period in which the Enigma machine was a critical issue.
Buffy
CC BY-SA 3.0
2017-12-15T00:50:16.760Z
2017-12-15T00:50:16.760Z
Ben I.
<p>You could use introduce <strong><a href="https://en.wikipedia.org/wiki/Elementary_cellular_automaton" rel="nofollow noreferrer">elementary (one-dimensional) cellular automata</a></strong>.</p>

<p>Basically, you represent a single row of cells as a simple array. Then you write a function that takes an array and applies the rules of the cellular automata to each cell (usually based on the old value of the cell and its two neighbors) to return a new array representing the next generation.</p>

<p>It's dead simple, but still results in pretty cool patterns if you display (or just print to console) the generations one after another. Here are some examples:</p>

<p><img src="https://upload.wikimedia.org/wikipedia/commons/a/a3/Rule45rand.png" alt="Rule 45">
<img src="https://upload.wikimedia.org/wikipedia/commons/c/c6/Rule105rand.png" alt="Rule 105">
<img src="https://upload.wikimedia.org/wikipedia/commons/c/c2/Rule106rand.png" alt="Rule 106">
<img src="https://upload.wikimedia.org/wikipedia/commons/b/bd/Rule146rand.png" alt="Rule 146">
<img src="https://upload.wikimedia.org/wikipedia/commons/0/0a/Rule150rand.png" alt="Rule 150">
<img src="https://upload.wikimedia.org/wikipedia/commons/0/03/Rule154rand.png" alt="Rule 154"></p>

CC BY-SA 3.0
2017-12-20T01:27:20.477Z
To generate a pattern like that would take a nested loop, though.
Ben I.
CC BY-SA 3.0
2017-12-20T01:44:20.917Z
@BenI. I suppose that depends on the language. I could do this with a single loop in Processing.
Kevin Workman
CC BY-SA 3.0
2017-12-19T23:20:38.237Z
2017-12-19T23:20:38.237Z
Kevin Workman
<p>Grades. Works especially well around final exam time.</p>

<p>You can find the average. Find the highest and lowest. Find the average with the lowest dropped. Find the most common grade. Count how many are in the range 90-100%. </p>

<p>Given an array of grades assigned for each class, calculate GPA. </p>

<p>Given 3 arrays that represent labs, quizzes, and tests calculate the final average. Each array can be weighted differently to match whatever your grading scale is. Ex: I would have labs weighted at 10%, quizzes at 20% and tests at 70%. </p>

CC BY-SA 3.0
2017-12-16T13:50:13.973Z
2017-12-17T19:57:30.527Z
2017-12-17T19:57:30.527Z
Ryan Nutt
<p>I recommend to check out <code>&lt;algorithm&gt;</code>, <code>&lt;numeric&gt;</code>, and related C++ headers. There are literally tons of linear algorithms of utter significance. From the top of my head, <code>copy</code>, <code>reverse</code>, <code>find</code>, <code>lower_bound</code>, <code>accumulate</code>, <code>iota</code>, <code>partial_sum</code>, <code>adjacent_difference</code>, <code>inner_product</code> are well deserving much attention.</p>

CC BY-SA 3.0
2017-12-18T21:20:13.150Z
2017-12-18T21:20:13.150Z
user58697
<p>I give a lab on single-dimensional loops and arrays. By "single dimensional loops", I mean that there is no nesting of loops.  (I will later give a second lab on multi-dimensional loops and arrays, but that is not this lab.)</p>

<p>The problem is that few of the problems on my lab right now are of any consequence.  What I <em>want</em> is to provide activities that are significant in computer science.  These students are still early enough that I'm not requiring nested loops, but that doesn't mean that they can't be exposed to significant ideas.  The trouble is, what are those ideas?</p>

<p>Good activities would either <em>be</em> algorithms of significance, or they will set the stage for later comprehension of deep and important ideas in CS.</p>

<p><strong>What are lab activities that can be done without nested loops that reflect important problems in Computer Science?</strong></p>

CC BY-SA 3.0
2017-12-15T00:12:20.883Z
There is a meta conversation that refers to this question [here](https://cseducators.meta.stackexchange.com/questions/340/the-list-nature-of-lesson-ideas?noredirect=1#comment643_340).
Ben I.
CC BY-SA 3.0
2017-12-15T01:01:08.813Z
I'll note that many problems that can be one with a simple (non-nested) loop can also be done recursively.
Buffy
<labs><algorithms><cs-theory><looping><arrays>
Single-dimensional array and simple looping activities of significance
# Single-dimensional array and simple looping activities of significance

(Asked by: username_0 on 2017-12-15)

I give a lab on single-dimensional loops and arrays. By "single dimensional loops", I mean that there is no nesting of loops. (I will later give a second lab on multi-dimensional loops and arrays, but that is not this lab.)

The problem is that few of the problems on my lab right now are of any consequence. What I *want* is to provide activities that are significant in computer science. These students are still early enough that I'm not requiring nested loops, but that doesn't mean that they can't be exposed to significant ideas. The trouble is, what are those ideas?

Good activities would either *be* algorithms of significance, or they will set the stage for later comprehension of deep and important ideas in CS.

**What are lab activities that can be done without nested loops that reflect important problems in Computer Science?**

**Tags:** labs, algorithms, cs-theory, looping, arrays

> **Comments:**
> **username_0**: There is a meta conversation that refers to this question [here](https://cseducators.meta.stackexchange.com/questions/340/the-list-nature-of-lesson-ideas?noredirect=1#comment643_340).  
> **username_1**: I'll note that many problems that can be one with a simple (non-nested) loop can also be done recursively.  

---

## 6 answers

### Answer by username_1 on 2017-12-15. Score: 7

The Dutch National Flag problem is linear in running time. Essentially sort an array with only 3 distinct values each of which may appear 0 or more times. (not length 3). You are allowed only one pass over the array, so the solution is a single while loop with some prior initialization.

It was probably originally posed by Dijkstra. It is mentioned in David Grits's *The Science of Programming* where it can be solved very nicely by posing pre and post conditions using David's ideas of finding invariants from pre and post conditions.

You can also make it a simple object oriented problem if you like by using objects as the array elements, for example.

A more interesting formulation of the problem refers to the Dutch National Flag which is a Tricolor: Red over White over Blue. You have an array that has some jumbled up red and white and blue cells, zero or more of each. You want to move all of the red cells to the left end, all of the blue cells to the right end, with the white cells in the middle. The restriction is that you may make only a single pass over the array. The correct solution is very creative and demonstrates the power of loop invariants.

I have mentioned this problem in answers to other questions here. A search for "dutch" on the questions page will reveal them.

Solving it without hints can provide a gigantic a-ha moment for almost everyone.

If students can do the classic version, they can also think about a modification that will handle 4 values instead. From that you can talk about the inherent complexity of sorting values from any finite set.


---

### Answer by username_0 on 2017-12-15. Score: 7

A variant on the ENIGMA machine encryption works well in a single loop, and is sufficiently complex to give students a real challenge.
The core idea of the ENIGMA machine for this assignment is that (1) a number is given as an initial key, and (2) every prior letter used influences how the next letter will be encrypted.
So, use a modular circle of encryptable characters (I chose ASCII 32 () to 126 (~), and just like a Caesar cipher, take your first letter and move it over by the key values.  But now modify key itself by adding the ASCII value of the inputted letter that you just encrypted to it.
Unstated in that description is the idea of creating a modular circle that doesn't begin from 0.  This is a pretty complex idea for students at this level to work with, and it helps to give them some guidance in this department.
Following this formula with the initial key 16, the statement

Four score and seven years ago our fathers brought forth on this continent, a new nation, conceived in Liberty, and dedicated to the proposition that all men are created equal.

Should get you:
Vf|0Pdhx,2RTch)=CZ`o0JPRey:R\q{,;[py{1QS`m.
Ask students to similarly create a decrypt method, but offer far less guidance than you did for encrypt.  It will require them to make sense of all of the mathematical operations that they performed in encrypt in order to successfully undo it.
You can also provide them with a few mystery strings to uncover.  The first student who successfully follows the directions given by the mystery strings gets some sort of prize or extra credit.  (The mystery strings themselves explain this; no need to give the secret away in advance.)

> **Comments:**
> **username_1**: There is an opportunity here for connecting the problem to History. In HS, students may simultaneously be studying the history of the period in which the Enigma machine was a critical issue.  

---

### Answer by username_2 on 2017-12-19. Score: 3

You could use introduce **[elementary (one-dimensional) cellular automata](https://en.wikipedia.org/wiki/Elementary_cellular_automaton)**.

Basically, you represent a single row of cells as a simple array. Then you write a function that takes an array and applies the rules of the cellular automata to each cell (usually based on the old value of the cell and its two neighbors) to return a new array representing the next generation.

It's dead simple, but still results in pretty cool patterns if you display (or just print to console) the generations one after another. Here are some examples:

![Rule 45](https://upload.wikimedia.org/wikipedia/commons/a/a3/Rule45rand.png)
![Rule 105](https://upload.wikimedia.org/wikipedia/commons/c/c6/Rule105rand.png)
![Rule 106](https://upload.wikimedia.org/wikipedia/commons/c/c2/Rule106rand.png)
![Rule 146](https://upload.wikimedia.org/wikipedia/commons/b/bd/Rule146rand.png)
![Rule 150](https://upload.wikimedia.org/wikipedia/commons/0/0a/Rule150rand.png)
![Rule 154](https://upload.wikimedia.org/wikipedia/commons/0/03/Rule154rand.png)

> **Comments:**
> **username_0**: To generate a pattern like that would take a nested loop, though.  
> **username_2**: @BenI. I suppose that depends on the language. I could do this with a single loop in Processing.  

---

### Answer by username_3 on 2017-12-16. Score: 2

Grades. Works especially well around final exam time.

You can find the average. Find the highest and lowest. Find the average with the lowest dropped. Find the most common grade. Count how many are in the range 90-100%.

Given an array of grades assigned for each class, calculate GPA.

Given 3 arrays that represent labs, quizzes, and tests calculate the final average. Each array can be weighted differently to match whatever your grading scale is. Ex: I would have labs weighted at 10%, quizzes at 20% and tests at 70%.


---

### Answer by username_4 on 2017-12-18. Score: 2

I recommend to check out , , and related C++ headers. There are literally tons of linear algorithms of utter significance. From the top of my head, `copy`, `reverse`, `find`, `lower_bound`, `accumulate`, `iota`, `partial_sum`, `adjacent_difference`, `inner_product` are well deserving much attention.


---

### Answer by username_0 on 2017-12-15. Score: 1

One small, but significant, algorithm is to find Euler's Number.

The irrational number $e$, also called Euler’s number, is approximately `2.71828`. The number is significant both to the [culture of computing](https://en.wikipedia.org/wiki/E_(mathematical_constant)#In_computer_culture) and has a role in such functions as computing continually compounding interest.

Euler proved that this number was irrational by showing that it was equal to the infinitely expanding series $1 + \frac{1}{1} + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!}$…

Ask students, then, to create a function that, given a number of iterations, returns the approximation of $e$ given by that many steps.

> **Comments:**
> **username_1**: Actually, approximating any infinite series could be adapted to this idea. Euler is interesting, however, in that both the sum and the factorial need to be captured in the same loop.  
> **username_1**: Possibly related: http://www.smbc-comics.com/comic/ellipsis  

---

