Chapter 5.8 - Analyzing Algorithms
Time Estimate: 90 minutes
5.8.1. Introduction and Goals
Searching and Sorting Experiments.In this lesson we are going to use an App Inventor app to analyze the algorithms we have been studying. You will be running two different apps, one to test the search algorithms and one to test the sorting algorithms.
This activity will resemble that of a scientific investigation. You'll run the apps repeatedly on different lists of data, record the running times of the algorithms, tabulate and graph your data, and then analyze the results. Can you figure out from the results, which algorithm is which?
Another way to look at this activity is as quality assurance (QA). Many careers in the computing field start with assignments in QA. This is where you help software developers test and debug their apps.
Learning Objectives: I will learn to
conduct an empirical (experimental) investigation of basic search and sort algorithms
determine the efficiency for basic search and sort algorithms depending on input size
deepen my understanding of search and sort algorithms
Language Objectives: I will be able to
represent data in a graph then analyze and make conclusions about the algorithms being run based on my data
use target vocabulary, such as efficiency and instance of a problem while experimenting with search and sort algorithms with the support of concept definitions and vocabulary notes from this lesson
5.8.2. Learning Activities
Analyzing Search Algorithms
Watch the following presentation on analyzing search algorithms to learn how to determine how fast linear search and binary search are.
Activity: 5.8.2.1 YouTube (Omh4VtutCdQ)
Search Experiment
Empirical Search Analysis. In this activity you are going to use an App Inventor app to experiment with and analyze the binary and sequential search algorithms.
Create a portfolio page named Search Experiment.
On an Android device, use the AI Companion app to scan and install the Search Experiment app (APK) from the QR code.
If you are using the emulator or an iOS device, you can download the aia file and import it into App Inventor and then Connect.
NOTE: When you run this app it may initially display a blank screen while it is initializing some data. This may take a minute. Please wait.
You will be performing a worst case analysis of the algorithms. Whenever you press the search button, the app will search for a number that is not in the list.
Test each search algorithm on lists of size 1000, 2000, ..., 10,000 numbers. NOTE: Because these algorithms involve loops, you may see an ANR (App Not Responding) popup informing you that the app is not responding and giving you the option to "wait" or stop the app. Choose "wait". It takes awhile to generate all the numbers.
Use this spreadsheet to enter the data and graph your results or empty graph paper. Put the data results and your graph in your portfolio.
Analyze your results to determine which algorithm is which. Which is the binary and which is the sequential search? Provide a clear description, referring to your graph and your tabulated data, to explain how you arrived at your conclusion.
Analyzing Sort Algorithms
Watch the following presentation on analyzing sort algorithms to learn how fast bubble sort, merge sort, and bucket sort are. (slides)
Activity: 5.8.2.2 YouTube (YmCzraw7IcA)
Sort Experiment
Empirical Sort Analysis. In this activity you are going to use an App Inventor app to experiment with and analyze the bubble, merge, and bucket sort algorithms.
Create a portfolio page named Sort Experiment.
Use the Barcode Scanner app -- you can download it from the Play Store if you don't have it -- to download the SortExperiment app (APK) from the QR code.
If you are using the emulator or an iOS device, you can download the aia file and import it into App Inventor.
Test each sort algorithm on lists of size 10, 20, ..., 100 numbers. These are called instances of the problem. An instance of a problem also includes specific input. For example, sorting is a problem, sorting the list (2,3,1,7) is an instance of the problem. NOTE: Because these algorithms involve loops, you may see an ANR (App Not Responding) popup informing you that the app is not responding and giving you the option to "wait" or stop the app. Choose "wait". It takes a while to generate all the numbers.
Use this spreadsheet to enter the data and graph your results or use empty graph paper. Put the data results and your graph in your portfolio.
Analyze your results to determine which algorithm is which. Which is the bubble, and which is the merge, and which is the bucket sort? Provide a clear description, referring to your graph and your tabulated data, to explain how you arrived at your conclusion.
5.8.3. Summary
In this lesson, you learned how to:
Learning Objective AAP-2.B: Represent a step-by-step algorithmic process using sequential code statements.
Clarity and readability are important considerations when expressing an algorithm in a programming language.
Learning Objective AAP-4.A.a: For determining the efficiency of an algorithm: a. Explain the difference between algorithms that run in reasonable time and those that do not.
Learning Objective AAP-4.A.b: For determining the efficiency of an algorithm: b. Identify situations where a heuristic solution may be more appropriate.
A problem is a general description of a task that can (or cannot) be solved algorithmically. An instance of a problem also includes specific input. For example, sorting is a problem; sorting the list (2,3,1,7) is an instance of the problem.
A decision problem is a problem with a yes/no answer (e.g., is there a path from A to B?). An optimization problem is a problem with the goal of finding the 'best' solution among many (e.g., what is the shortest path from A to B?).
Efficiency is an estimation of the amount of computational resources used by an algorithm. Efficiency is typically expressed as a function of the size of the input. EXCLUSION STATEMENT (EK AAP-4.A.3): Formal analysis of algorithms (Big-O) and formal reasoning using mathematical formulas are outside the scope of this course and the AP Exam.
An algorithm’s efficiency is determined through formal or mathematical reasoning.
An algorithm's efficiency can be informally measured by determining the number of times a statement or group of statements executes.
Different correct algorithms for the same problem can have different efficiencies.
Algorithms with a polynomial efficiency or slower (constant, linear, square, cube, etc.) are said to run in a reasonable amount of time. Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time.
Some problems cannot be solved in a reasonable amount of time because there is no efficient algorithm for solving them. In these cases, approximate solutions are sought.
A heuristic is an approach to a problem that produces a solution that is not guaranteed to be optimal but may be used when techniques that are guaranteed to always find an optimal solution are impractical. EXCLUSION STATEMENT (AAP-4.A.9): Specific heuristic solutions are outside the scope of this course and the AP Exam.
5.8.4. Self-Check
Here is a table of some of the technical terms discussed in this lesson. Hover over the terms to review the definitions.
efficiency
more efficient
instance of a problem
linear or sequential search
binary search
sorting algorithm
Q-3: According to the following table, how many lookups would be required in the worst case to find a number in list of 10000 elements using linear search? Type your answer in the text box.
Q-4: According to the following table, how many lookups would be required in the worst case to find a number in a sorted list of 10000 elements using binary search? Type your answer in the text box.
Q-5: If you were using binary search to find the number 14 in the following list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], how many iterations would be required to find 14 in the list?
A. 4
B. 3
C. 14
D. 2
Q-6: For a list of 500 numbers, at most how many iterations would the loop in binary search run to find a number? For example, if this was a guessing game, at most how many guesses would it take using binary search to guess a secret number from 1-500, if after each guess you were told whether your guess was too high or too low or just right? Type your answer into the text box.
Q-7: The function shown in this graph is known as the base-2 logarithm function, y = log2(x). Which search algorithm behaves like this function?
A. Sequential search
B. Binary search
Q-8: In talking about sorting algorithms in general, a sort algorithm’s efficiency refers to ______________________.
A. whether the algorithm correctly arranges the values in order.
B. whether or not the algorithm contains a bug.
C. how long it takes to arrange the values in order.
D. how many swaps are needed to sort the values.
E. how many comparisons are needed to sort the values.
Q-9: To say that bucket sort is more efficient than bubble sort means that _________________.
A. bucket sort requires fewer swaps than bubble sort.
B. for any size list, bucket sort will always be faster than bubble sort.
C. bucket sort requires fewer comparisons than bubble sort.
D. as the size of the list grows, bucket sort will be faster than bubble sort.
Q-10: Which of the following characteristics is true of bubble sort? Choose all that apply.
A. More efficient than bucket sort.
B. An N2 algorithm.
C. Widely used to sort large data sets.
D. Useful only for sorting numbers.
E. A comparison-based algorithm.
Q-11: Which of the following characteristics is true of bucket sort? Choose all that apply.
A. More efficient than bubble sort.
B. A comparison-based algorithm.
C. A linear algorithm
D. An N2 algorithm.
E. Useful only for sorting numbers.
5.8.5. Sample AP CSP Exam Question
Q-12: There are 32 students standing in a classroom. Two different algorithms are given for findingthe average height of the students.
Algorithm A
Step 1: All students stand.
Step 2: A randomly selected student writes his or her height on a card and is seated.
Step 3: A randomly selected standing student adds his or her height to the value on the card,records the new value on the card, and is seated. The previous value on the card is erased.
Step 4: Repeat step 3 until no students remain standing.
Step 5: The sum on the card is divided by 32. The result is given to the teacher.
Algorithm B
Step 1: All students stand.
Step 2: Each student is given a card. Each student writes his or her height on the card.
Step 3: Standing students form random pairs at the same time. Each pair adds the numberswritten on their cards and writes the result on one student’s card; the other student isseated. The previous value on the card is erased.
Step 4: Repeat step 3 until one student remains standing.
Step 5: The sum on the last student’s card is divided by 32. The result is given to the teacher.
Which of the following statements is true?
A. Both Algorithm A and Algorithm B always calculate the correct average.
B. Algorithm B always calculates the correct average, but Algorithm A does not.
C. Algorithm A always calculates the correct average, but Algorithm B does not.
D. Neither Algorithm A nor Algorithm B calculates the correct average.
5.8.6. Reflection: For Your Portfolio
Answer the following portfolio reflection questions as directed by your instructor. Questions are also available in this Google Doc where you may use File > Make a Copy to make your own editable copy.
Present the results and the analysis you did for the search experiment in this lesson.
Paste the table of running times you observed.
Paste the graph you created.
Write the conclusions you reached regarding the search algorithms. Provide a clear description, referring to your graphs and your data and graphs, to explain how you arrived at your conclusions.
Present the results and the analysis you did for the sort experiment in this lesson.
Paste the table of running times you observed.
Paste the graph you created.
Write the conclusions you reached regarding the sort algorithms. Provide a clear description, referring to your graphs and your data and graphs, to explain how you arrived at your conclusions.
Portfolio Reflection Questions
Make a copy of this document in your Portfolio Assignments folder and answer these questions in the spaces below. Once complete, turn in this assignment according to the steps given by your teacher.
5.8 Analyzing Algorithms Curriculum Page
Answer the following questions:
1. Present the results and the analysis you did for the search experiment in this lesson.
a. Paste the table of running times you observed.
b. Paste the graph you created.
c. Write the conclusions you reached regarding the search algorithms. Provide a clear description, referring to your graphs and your data and graphs, to explain how you arrived at your conclusions.
Answer
2. Present the results and the analysis you did for the sort experiment in this lesson.
a. Paste the table of running times you observed.
b. Paste the graph you created.
c. Write the conclusions you reached regarding the sort algorithms. Provide a clear description, referring to your graphs and your data and graphs, to explain how you arrived at your conclusions.
Answer
Last updated