Unit 5 Lab 3: Timing Experiments, Page 3

EK 4.1.1G Knowledge of standard algorithms can help in constructing new algorithms.

LO 4.2.1 in #7

LO 4.2.1 Explain the difference between algorithms that run in a reasonable time and those that do not run in a reasonable time. [P1]
EK 4.2.1A Many problems can be solved in a reasonable time.
EK 4.2.1B Reasonable time means that the number of steps the algorithm takes is less than or equal to a polynomial function (constant, linear, square, cube, etc.) of the size of the input.
EK 4.2.1C Some problems cannot be solved in a reasonable time, even for small input sizes.
EK 4.2.1D Some problems can be solved but not in a reasonable time. In these cases, heuristic approaches may be helpful to find solutions in reasonable time.
EK 4.2.2A A heuristic is a technique that may allow us to find an approximate solution when typical methods fail to find an exact solution.
EK 4.2.2B Heuristics may be helpful for finding an approximate solution more quickly when exact methods are too slow.
EK 4.2.2C Some optimization problems such as 'find the best' or 'find the smallest' cannot be solved in a reasonable time, but approximations to the optimal solution can.

efficiency only: analytically FYTD #4 and empirically FYTD #3
we can do "correctness" on the debugging page.--MR

LO 4.2.4 Evaluate algorithms analytically and empirically for efficiency, correctness, and clarity. [P4]

If it isn't already open, load the project U5L3-timer from the previous page. You will be experimenting with time function with each of these input functions:
- (as you saw on Unit 3 Lab 4: Building a Graphing App)
- (as you saw on Unit 5 Lab 1: List Processing Algorithms)
- (as you saw on Unit 5 Lab 3: Comparing Algorithms)
For each one, what happens to the running time if you double the size of the input?
What does it mean to double the size of the input for numbers from () to ()?

Use the block to build the following two blocks in Snap!. Then, determine which block's algorithm can be executed in a reasonable time, and which cannot.
The list of 2-digit numbers goes from 10 to 99. There's a math operations block that can give you powers of 10.

To classify an algorithm, look at the number of steps it takes to complete the algorithm, compared to the size of the input.

One reason it's worth learning these categories is that in writing programs, you often need to solve a problem for which there are already established solutions. For example, you've learned that searching for something in an unordered list takes linear time, but if the list is sorted, you can search it faster (in sublinear time). So when you're writing a program that needs to search through a list repeatedly, you'll know that it's worthwhile to sort the list before the searching. Knowing about standard algorithms that already exist can help you construct new algorithms.

algorithm efficiency	If you double the size of input, the time...	example algorithm
constant	stays the same (multiplies by 2⁰ which is 1)	`item (87) of ()`
sublinear	multiplies by some number between 1 and 2 (between 2⁰ and 2¹)	binary search: `position of () in sorted list`
linear	multiplies by 2 (which is 2¹)	linear search: `position of () in unsorted list`
quadratic	multiplies by 4 (which is 2²)	some kinds of sorting algorithms
cubic	multiplies by 8 (which is 2³)	some gene mapping algorithms used in biology

Look at some algorithms you've built. Determine whether each algorithm runs in constant time, sublinear time, linear time, quadratic time, or unreasonable time.

For Alphie's way of adding integers, create a graph with the number of integers on the horizontal and the runtime on the vertical. Generate data for the graph by running time function with large inputs to Alphie's way (say, multiples of 100). Then use the techniques from Lab 2 to plot the graph.
What information does this graph tell you about Alphie's algorithm? Is it constant time, linear time, other polynomial time, or is it unreasonable time?

This question is similar to those you will see on the AP CSP exam.

The table below shows the computer time it takes to complete various tasks on the data of different sized towns.

Task	Small Town (population 1,000)	Mid-sized Town (population 10,000)	Large Town (population 100,000)
Entering Data	2 hours	20 hours	200 hours
Backing up Data	0.5 hours	5 hours	50 hours
Searching through Data	5 hours	15 hours	25 hours
Sorting Data	0.01 hour	1 hour	100 hours

Based on the information in the table, which of the following tasks is likely to take the longest amount of time when scaled up for a city of population 1,000,000.

Entering data

As the population size is multiplied by 10, the time needed for entering data is also multiplied by 10, so for a population of 1,000,000, it should take about 10×200=2000 hours.

Backing up data

As the population size is multiplied by 10, time needed for backing up data is multiplied by 10, so for a population of 1,000,000, it should take about 10×50=500 hours.

Searching through data

Searching through the data seems to go up by about 10 hours each time the population is multiplied by 10, so for a population of 1,000,000, it should take about 35 hours.

Sorting data

Correct! As the population size is multiplied by 10, the time needed for the sorting of data is multiplied by 100. So, for a population of 1,000,000, it should take about 100×100=10,000 hours.

Write a paragraph explaining the difference between algorithms that run in a reasonable time and algorithms that require unreasonable time to run.

Classifying Algorithms