Unit 5 Lab 3: Timing Experiments, Page 1

Alphie and Betsy 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. Alphie and Betsy are discussing their different approaches.

Alphie: 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.

Formatting needs clean-up, no? This is a little overwhelming... --MF, 7/3/18

The combine with() items of () block takes an operation (with two blank input slots) and a list as input, and it reports a single result (not a list): the combination of the elements in the list when using the given operation. For example:

Read this out loud as "combine the elements of the list {5, 6, 2, 3} with addition."

combine with (()+()) items of (list {5,6,2,3}) reporting 16

Combine is a higher order function. This means that it is a function that takes a function as input. You've seen several higher order functions already: for each (in Unit 2 Lab 2), keep (in Unit 2 Lab 3), and map (in Unit 3 Lab 1).

You choose the operation, and combine performs that operation by combining all the items in the input list and then reports the result.

Notice that the function used to combine the list items always has two blank input slots. Both map and keep only need one blank in their input function, but with combine, two are required.

Unlike map and keep, combine is mostly used with one of only these six functions:

Among blocks you might write yourself, there are only two likely candidates:
max

Why so few?

The function has to be associative, meaning that it doesn't matter what order you group the items in; (7 + 8) + 1 is the same as 7 + (8 + 1) (work it out yourself), but (7 − 8) − 1 is different from 7 − (8 − 1). So

would be ambiguous.

Alphie 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))}

Betsy: Great! I think we can do it another way too.

Alphie: Cool. How?

Betsy: I was thinking about adding, and I noticed that 1 + 13 = 14 and 2 + 12 = 14 and 3 + 11 = 14...

Alphie: So, you added up fourteens?

Betsy: 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:

Betsy writes on the board:

Betsy: Then I added down and got thirteen fourteens:

Betsy: And 13 times 14 is 182...

Alphie: But the answer is 91.

Betsy: Right. I added each number in twice, so the answer is half of 182, which is 91.

Betsy writes

\frac{13 \times 14}{2}

=91

Alphie: 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 (Alphie calculates) 1275.

Alphie writes

\frac{50 \times 51}{2}

=1275

Betsy: (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...

Betsy writes

\frac{n \times (n + 1)}{2}

.
Then Betsy builds the block, and Alphie helps debug.

Discuss these two algorithms and make a hypothesis: Which algorithm do you think will be more efficient? Why?
For Alphie’s method, use the block numbers from () to () in the Variables palette. You'll need to to see it.
Implement a sum from 1 to algorithm. You can use Alphie’s method (using combine to code sum), you can use Betsy’s formula, or you can build it your own way.

"U5L3-ReporterTimer"
Work with another team to compare Alphie's and Betsy's algorithms across a variety of inputs. Determine which is more efficient (that is, which runs faster).
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 Betsy's algorithm carry out?
2. How many arithmetic operations will Alphie's method use?
3. What you are adding the numbers form 1 to 1000?
4. Do these counts of arithmetic operations make sense when compared to the experimental results in exercise 3?

Comparing Algorithms