Answers.Body: <p>Note that the following are intended for the instructor, not always directly for the student. If used well they require some analysis, not just coding, from the student.</p>
  <p>Use the fact that the sum of the first <em>n</em> odd numbers is <span class="math-container">$n^2$</span> to compute the integer square root of an integer.</p>
  <p>Test data should include 63, 64, and 65 to catch edge cases.</p>
  <p>This can be extended past the decimal point and optimized in various ways to compute more accurate approximations of square roots.</p>
  <hr />
  <p>Notes on the above, but I suggest you try it before peeking:</p>
  <blockquote class="spoiler">
  <p>To make it a bit more obvious, this involves using inverse functions and computing inverses. The loop actually needs to count subtractions and uses facts about perfect squares to compute square roots. That same idea might be exploited for other problems.
  
  Note that <span class="math-container">$\lfloor$</span>  <span class="math-container">$\sqrt 65$</span> <span class="math-container">$\rfloor$</span> = 8.</p>
  </blockquote>
  <hr />
  <p>Other simple things:</p>
  <ul>
  <li><p>How many digits does an integer have?</p>
  </li>
  <li><p>How many bits are required to represent an integer? (Note that the structure is the same as the above)</p>
  </li>
  <li><p>How many times does zero (for example) appear in the decimal representation of an integer.</p>
  </li>
  <li><p>Sum of the digits of a given integer.</p>
  </li>
  <li><p>Is the number of 1 bits in a binary representation of an integer even or odd?</p>
  </li>
  <li><p>Read a real value x from input. Then read the successive coefficients of a polynomial from input and evaluate the polynomial at x. Note that the stopping condition needs to be specified and by varying it you can have different systems. Reading it from input is one of the obvious variations. Hardcoding it is another. Later on, the coefficients can be in an array, of course.</p>
  </li>
  <li><p>In teaching loops it is important to also give exercises where the correct number of iterations is zero. For example, give x and y, find the number of multiples of 3 that are larger than x but less than y. Don't exclude the initial condition y &lt; x.</p>
  </li>
  <li><p>Nested loops: Once you have the solution to &quot;is X prime?&quot;, how many primes are there between a given x and y?</p>
  </li>
  </ul>
  <hr />
  <p>A bit harder:</p>
  <p><a href="https://en.wikipedia.org/wiki/Euclidean_algorithm" rel="nofollow noreferrer">Euclid's algorithm</a>.</p>
  <hr />
  <p>Extensions:</p>
  <ul>
  <li><p>Use other similar sums (than the sum of odds) to compute other things.</p>
  </li>
  <li><p>Look at the <a href="https://en.wikipedia.org/wiki/Taylor_series" rel="nofollow noreferrer">Wikipedia article on Taylor Series</a> to get some ideas about how to approximate some interesting functions with sums.</p>
  </li>
  </ul>
  <hr />
  <p>A solution to the square root problem follows, using a personal (executable) pseudocode:</p>
  <blockquote class="spoiler">
  <p> <pre><code>    $ &quot;Computes the integer square root of a non-negative number&quot;;
      With
        value; current; count; odd; // integer variables
      Program
        Read value;
        current &lt;- value;
        count &lt;- 0;
        odd &lt;- 1;
  <br />
        While current &gt;= odd {
            current &lt;- current - odd;
            odd &lt;- odd + 2;
            count &lt;- count + 1;
        }
  <br />
        Print &quot;The integer square root of &quot;, value, &quot; is &quot;, count;
      End </code></pre></p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-21T19:27:44.583Z
Answers.LastActivityDate: 2020-12-24T17:45:34.240Z
Answers.LastEditDate: 2020-12-24T17:45:34.240Z
Answers.UserDisplayName: Buffy
Answers.Body: <p>I'm adding in a second answer to look at a few heftier assignments, worthy of a lab.  These were created by a truly fantastic colleague of mine.</p>
  <p>The game <strong>Nim</strong> is excellent for a loop with no arrays.  You can use just three variables to keep track of the state of the game, and a variable and an <code>if</code> statement to deal with the player.  (Kids at this level will <em>often</em> try to simply copy their code from player 1 for player 2, and won't think to simplify the structure by using a variable -- that's a good segue into the idea of defensive coding, wherein you assume that your code is always <em>somehow</em> buggy, and you make efforts not to proliferate the bugs all over the place.  That same idea dovetails nicely into function calls as well.)</p>
  <p>We also have an <strong>Electronic Piggy Bank</strong> assignment where the user can add in <code>p</code> (penny), <code>n</code> (nickel), <code>d</code> (dime) and <code>q</code> (quarter) as many times as they want.  The program will keep a running tally of the amount in the piggy bank.  The user can then type <code>exit</code> to finish up and see the final report.  Again, this is a lab that requires keeping track of several variables, and motivated the use of loops and branching, but doesn't require arrays to be effective.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-22T02:33:45.860Z
Answers.Text: I feel the piggy bank assignment is bit easy for high school kids. Besides, for prime number I introduce for loop, for the answer about quotient/remainder I can introduce while loop, for piggy back, what is the main purpose ? Keeping track of several variables ?
Answers.UserDisplayName: Qiulang 邱朗
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-22T02:50:40.450Z
Answers.Text: @Qiulang I'm not sure what to tell you, other than that we do it.  `while (! input.equals("exit") )` can be a surprisingly hard structure for HS kids to suss out. Figuring out where to collect input, the placement of the `!`, and that you have to use `.equals` are all minor challenges, but they add up when they're put together like that. And, of course, we're talking about *beginner beginners* here -- if they had background, they wouldn't have to be practicing loops without arrays in the first place. The banking aspect is just a way to practice with strings, really.
Answers.UserDisplayName: Ben I.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-22T03:46:57.467Z
Answers.Text: On a side note do you explain to them why array index starts from 0 ?
Answers.UserDisplayName: Qiulang 邱朗
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-22T04:36:24.563Z
Answers.Text: @Qiulang Not that early, no, but eventually we do.  (We have the benefit of a multi-year program.)  On our first pass-through, it is a lot about the mechanics and the Big Ideas -- we don't delve much into smaller details until our second big pass, when they're ready to begin to absorb a lot of the logic behind the mechanisms they've built up practical experience with.
Answers.UserDisplayName: Ben I.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-21T22:24:45.293Z
Answers.LastActivityDate: 2020-12-21T22:24:45.293Z
Answers.UserDisplayName: Ben I.
Answers.Body: <p>Now I have another favorite example called &quot;Buy Low, Sell High&quot;, all the credit go to this article <a href="https://realpython.com/numpy-array-programming/#buy-low-sell-high" rel="nofollow noreferrer">https://realpython.com/numpy-array-programming/#buy-low-sell-high</a></p>
  <blockquote>
  <p>Given a stock’s price history as a sequence, and assuming that you are only allowed to make one purchase and one sale, what is the maximum profit that can be obtained? For example, given prices = (20, 18, 14, 17, 20, 21, 15), the max profit would be 7, from buying at 14 and selling at 21.</p>
  </blockquote>
  <p>There are some challenges  to the high school kids, e.g. some came up with an idea to do it in 2 loops, first find the min then  the max or just 1 loop to find max &amp; min. But what if max comes before min ? And the solution there as &quot;find the difference between each price and a running minimum (element-wise), and then take the max of this sequence&quot; is quite clever.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-07-15T10:53:08.230Z
Answers.LastActivityDate: 2021-07-16T03:36:25.927Z
Answers.LastEditDate: 2021-07-16T03:36:25.927Z
Answers.UserDisplayName: Qiulang 邱朗
Answers.Body: <p>Write a loop that reverses the characters of a string.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-23T07:10:13.900Z
Answers.Text: I will let them do a in-place reverse, otherwise it is too easy. But that introduces another problem, we use python and string is immutable. If I then introduce list and string conversion I fear sidetracking the teaching of loop.
Answers.UserDisplayName: Qiulang 邱朗
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-23T04:38:28.140Z
Answers.LastActivityDate: 2020-12-23T04:38:28.140Z
Answers.UserDisplayName: paw88789
Answers.Body: <p>Since we introduce loops before we introduce arrays, we will often do simple programs like ask a user how many numbers they want to enter, and then find the sum of the numbers entered.</p>
  <p>Similarly, they can practice these concepts a few times to find the maximum, minimum, and average of the numbers entered.  Having a few very similar tiny projects like this can be useful as a way to let the kids internalize the structure a little and begin to feel comfortable with it.</p>
  <p>You can also have them make a nice, rolling report of compound interest for a retirement calculator.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-22T02:43:46.747Z
Answers.Text: I think finding the max, min, avg do have "practical" application.
Answers.UserDisplayName: Qiulang 邱朗
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-07-16T03:37:55.633Z
Answers.Text: I have further challenged my students about max & min, check my answer about "Buy Low, Sell High" :D
Answers.UserDisplayName: Qiulang 邱朗
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-21T19:51:35.223Z
Answers.LastActivityDate: 2020-12-21T22:17:42.613Z
Answers.LastEditDate: 2020-12-21T22:17:42.613Z
Answers.UserDisplayName: Ben I.
Body: <p>I am teaching some high school students, also the first time programmers, some basic programming concepts and applications.  When introducing loop I find that using it to <strong>check prime number</strong> (and find prime numbers within a number range with nested loop) is a good example. It teaches them the concept of loop but also make them think, e.g. it just need to loop to <span class="math-container">$\sqrt{n} + 1$</span>, no need to loop to <span class="math-container">$n$</span>.</p>
  <p>I would like to know other examples like that to introduce loop, not too easy or too hard (for high school students) and better to have some practical application.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-05-04T02:05:10.673Z
Comments.Text: The smallest factor (if it exists) if $n$ is guaranteed  to be at most $\lfloor \sqrt{n} \rfloor$
Comments.UserDisplayName: vonbrand
Tags: <lesson-ideas><secondary-education><algorithms><looping>
Title: What are good, practical labs and activities for loops?
ThreadText: # What are good, practical labs and activities for loops?
  
  (Asked by: username_0 on 2020-12-21)
  
  I am teaching some high school students, also the first time programmers, some basic programming concepts and applications. When introducing loop I find that using it to **check prime number** (and find prime numbers within a number range with nested loop) is a good example. It teaches them the concept of loop but also make them think, e.g. it just need to loop to $\sqrt{n} + 1$, no need to loop to $n$.
  
  I would like to know other examples like that to introduce loop, not too easy or too hard (for high school students) and better to have some practical application.
  
  **Tags:** lesson-ideas, secondary-education, algorithms, looping
  
  > **Comments:**
  > **username_1**: The smallest factor (if it exists) if $n$ is guaranteed  to be at most $\lfloor \sqrt{n} \rfloor$  
  
  ---
  
  ## 5 answers
  
  ### Answer by username_2 on 2020-12-21. Score: 4
  
  Note that the following are intended for the instructor, not always directly for the student. If used well they require some analysis, not just coding, from the student.
  
  Use the fact that the sum of the first *n* odd numbers is $n^2$ to compute the integer square root of an integer.
  
  Test data should include 63, 64, and 65 to catch edge cases.
  
  This can be extended past the decimal point and optimized in various ways to compute more accurate approximations of square roots.
  
  ---
  
  Notes on the above, but I suggest you try it before peeking:
  
  > To make it a bit more obvious, this involves using inverse functions and computing inverses. The loop actually needs to count subtractions and uses facts about perfect squares to compute square roots. That same idea might be exploited for other problems.
  > Note that $\lfloor$ $\sqrt 65$ $\rfloor$ = 8.
  
  ---
  
  Other simple things:
  
  * How many digits does an integer have?
  * How many bits are required to represent an integer? (Note that the structure is the same as the above)
  * How many times does zero (for example) appear in the decimal representation of an integer.
  * Sum of the digits of a given integer.
  * Is the number of 1 bits in a binary representation of an integer even or odd?
  * Read a real value x from input. Then read the successive coefficients of a polynomial from input and evaluate the polynomial at x. Note that the stopping condition needs to be specified and by varying it you can have different systems. Reading it from input is one of the obvious variations. Hardcoding it is another. Later on, the coefficients can be in an array, of course.
  * In teaching loops it is important to also give exercises where the correct number of iterations is zero. For example, give x and y, find the number of multiples of 3 that are larger than x but less than y. Don't exclude the initial condition y < x.
  * Nested loops: Once you have the solution to "is X prime?", how many primes are there between a given x and y?
  
  ---
  
  A bit harder:
  
  [Euclid's algorithm](https://en.wikipedia.org/wiki/Euclidean_algorithm).
  
  ---
  
  Extensions:
  
  * Use other similar sums (than the sum of odds) to compute other things.
  * Look at the [Wikipedia article on Taylor Series](https://en.wikipedia.org/wiki/Taylor_series) to get some ideas about how to approximate some interesting functions with sums.
  
  ---
  
  A solution to the square root problem follows, using a personal (executable) pseudocode:
  
  > ```
  >     $ "Computes the integer square root of a non-negative number";
  >     With
  >       value; current; count; odd; // integer variables
  >     Program
  >       Read value;
  >       current <- value;
  >       count <- 0;
  >       odd <- 1;
  >   
  >
  >       While current >= odd {
  >           current <- current - odd;
  >           odd <- odd + 2;
  >           count <- count + 1;
  >       }
  >   
  >
  >       Print "The integer square root of ", value, " is ", count;
  >     End 
  > ```
  
  
  ---
  
  ### Answer by username_3 on 2020-12-21. Score: 4
  
  I'm adding in a second answer to look at a few heftier assignments, worthy of a lab. These were created by a truly fantastic colleague of mine.
  
  The game **Nim** is excellent for a loop with no arrays. You can use just three variables to keep track of the state of the game, and a variable and an `if` statement to deal with the player. (Kids at this level will *often* try to simply copy their code from player 1 for player 2, and won't think to simplify the structure by using a variable -- that's a good segue into the idea of defensive coding, wherein you assume that your code is always *somehow* buggy, and you make efforts not to proliferate the bugs all over the place. That same idea dovetails nicely into function calls as well.)
  
  We also have an **Electronic Piggy Bank** assignment where the user can add in `p` (penny), `n` (nickel), `d` (dime) and `q` (quarter) as many times as they want. The program will keep a running tally of the amount in the piggy bank. The user can then type `exit` to finish up and see the final report. Again, this is a lab that requires keeping track of several variables, and motivated the use of loops and branching, but doesn't require arrays to be effective.
  
  > **Comments:**
  > **username_0**: I feel the piggy bank assignment is bit easy for high school kids. Besides, for prime number I introduce for loop, for the answer about quotient/remainder I can introduce while loop, for piggy back, what is the main purpose ? Keeping track of several variables ?  
  > **username_3**: @username_0 I'm not sure what to tell you, other than that we do it.  `while (! input.equals("exit") )` can be a surprisingly hard structure for HS kids to suss out. Figuring out where to collect input, the placement of the `!`, and that you have to use `.equals` are all minor challenges, but they add up when they're put together like that. And, of course, we're talking about *beginner beginners* here -- if they had background, they wouldn't have to be practicing loops without arrays in the first place. The banking aspect is just a way to practice with strings, really.  
  > **username_0**: On a side note do you explain to them why array index starts from 0 ?  
  > **username_3**: @username_0 Not that early, no, but eventually we do.  (We have the benefit of a multi-year program.)  On our first pass-through, it is a lot about the mechanics and the Big Ideas -- we don't delve much into smaller details until our second big pass, when they're ready to begin to absorb a lot of the logic behind the mechanisms they've built up practical experience with.  
  
  ---
  
  ### Answer by username_0 on 2021-07-15. Score: 1
  
  Now I have another favorite example called "Buy Low, Sell High", all the credit go to this article <https://realpython.com/numpy-array-programming/#buy-low-sell-high>
  
  > Given a stock’s price history as a sequence, and assuming that you are only allowed to make one purchase and one sale, what is the maximum profit that can be obtained? For example, given prices = (20, 18, 14, 17, 20, 21, 15), the max profit would be 7, from buying at 14 and selling at 21.
  
  There are some challenges to the high school kids, e.g. some came up with an idea to do it in 2 loops, first find the min then the max or just 1 loop to find max & min. But what if max comes before min ? And the solution there as "find the difference between each price and a running minimum (element-wise), and then take the max of this sequence" is quite clever.
  
  
  ---
  
  ### Answer by username_4 on 2020-12-23. Score: 1
  
  Write a loop that reverses the characters of a string.
  
  > **Comments:**
  > **username_0**: I will let them do a in-place reverse, otherwise it is too easy. But that introduces another problem, we use python and string is immutable. If I then introduce list and string conversion I fear sidetracking the teaching of loop.  
  
  ---
  
  ### Answer by username_3 on 2020-12-21. Score: 1
  
  Since we introduce loops before we introduce arrays, we will often do simple programs like ask a user how many numbers they want to enter, and then find the sum of the numbers entered.
  
  Similarly, they can practice these concepts a few times to find the maximum, minimum, and average of the numbers entered. Having a few very similar tiny projects like this can be useful as a way to let the kids internalize the structure a little and begin to feel comfortable with it.
  
  You can also have them make a nice, rolling report of compound interest for a retirement calculator.
  
  > **Comments:**
  > **username_0**: I think finding the max, min, avg do have "practical" application.  
  > **username_0**: I have further challenged my students about max & min, check my answer about "Buy Low, Sell High" :D  
  
  ---
  
  