Comparing Algorithms

BH and MF: scrap whole page

We should change the CSS so that sidenotes never extend behind the element they are about; add space to the element if necessary. For example, that "Read this out loud" box shouldn't overlap the orange. --MF, 12/27/17

Brian also wants to change the katex in 5 and make the narrower box light blue here. --MF, 12/27/17

Fundamental concern: this context is too much overhead for teaching the idea of efficiency; the context should be more accessible so efficiency is the only idea they are grappling with. --MF, 9/26/18

PG: I've never loved any part of this lab, but we need the content in some form. This page takes the special case of triangular numbers and shows how the closed form is clearly more efficient than anything else: the positive message is that a bit of forethought (mathematics) can be efficient. The problem is that it is such a special case and that combine gets dismissed so quickly. I've also never been thrilled with the timer.

BH: This whole unit needs rethinking. Limiting the discussion to what the AP requires makes it boring. Bring back activities about all the categories from constant to exponential time, including n log n, etc.
The numbers from A to B block is now in the tools library.

MF: needs formatting edits, but more importantly, the page is too long and the context is too much overhead to teach efficiency

In this lab, you will learn that some ways to solve a problem are faster than others.

On this page, you will compare two algorithms for adding the numbers from 1 to an input number (as shown below).
sum from 1 to (5) reporting 15

Morgan and Jasmine are creating algorithms that take a positive integer as input and report the sum of all integers from 1 to the input number, like this:
sum from 1 to (13) reporting 91
Their two different approaches always give the same outputs for the same inputs. Morgan and Jasmine are discussing their different approaches.
Morgan: I made two new blocks. First, I created a reporter to list of all the integers between and including two integers, and then I used combine to add up the list.
This block is now built-in to Snap (as a tool). Images and instructions should be changed. --MF, 3/11/19
Morgan shows his work:
list from (1) to (7) reporting the list{1,2,3,4,5,6,7
sum of (inputList){report(combine with(()+()) items of (inputList))}
Jasmine: Great! I think we can do it another way too.
Morgan: Cool. How?
Jasmine: I was thinking about adding, and I noticed that 1 + 13 = 14 and 2 + 12 = 14 and 3 + 11 = 14...
Brian and Mary agree to stop using the math example and are thinking about using a search function. --MF, 3/11/19
Morgan: So, you added up fourteens?
Jasmine: Yeah. I wrote down the list from 1 to 13 and then I wrote the same numbers in reverse order—right under my first list, like this:
Jasmine writes on the board:
Jasmine: Then I added down and got thirteen fourteens:
Jasmine: And 13 times 14 is 182...
Morgan: But the answer is 91.
Jasmine: Right. I added each number in twice, so the answer is half of 182, which is 91.
Jasmine writes \frac{13 \times 14}{2}=91.
Morgan: Oh, and if you wanted to add the numbers from 1 to 50, you'd multiply 50 and 51 and divide by 2 to get (Morgan calculates) 1275.
Morgan writes \frac{50 \times 51}{2}=1275.
Jasmine: (smiling) So in general to add the numbers between 1 and some number, n, you multiply the input number by one more than the input number and then you divide the result by 2...
Jasmine writes \frac{n \times (n + 1)}{2}.
Then Jasmine builds the block, and Morgan helps debug.
  1. Discuss these two algorithms and make a hypothesis: Which algorithm do you think will be more efficient? Why?
  2. For Morgan’s method, use the block numbers from () to () in the Variables palette. You'll need to Import Tools to see it.
    Implement a sum from 1 to algorithm. You can use Morgan’s method (using combine to code sum), you can use Jasmine’s formula, or you can build it your own way.
    "U5L3-ReporterTimer"Save your work as U5L3-ReporterTimer
  3. Work with another team to compare Morgan's and Jasmine's algorithms across a variety of inputs. Determine which is more efficient (that is, which runs faster).
  4. In exercise 3, you used timing experiments to find out which algorithm runs faster. You can also use formal reasoning to prove that one algorithm is faster than the other:
    1. When adding the numbers from 1 to 100, how many arithmetic operations (+, –, ×, ÷) will Jasmine's algorithm carry out?
    2. How many arithmetic operations will Morgan's method use?
    3. What if you are adding the numbers from 1 to 1000?
    4. Do these counts of arithmetic operations make sense when compared to the experimental results in exercise 3?
  1. If you built a graphing app, try plotting y= sum from 1 to( x).