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.

(Teacher Tube version)

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

• Slides Part 1
• |
• Slides Part 2
• |
• YouTube Video Analyzing Search
• |
• YouTube Video Analyzing Sort
• |
• Analysis Spreadsheet
• |
• Graph Paper

Analyzing Search Algorithms

Watch the following presentation on analyzing search algorithms to learn how to determine how fast linear search and binary search are.

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)

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:

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-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?

• 2
• No, try again. Pretend you are trying to guess a number from 1-15 using binary search. Always guess the middle element and see if it is higher or lower than your correct number 14. See how many times you need to guess. 
• 3
• Yes, the first time through the loop, 14 is compared with the middle element 8 and is higher, so you narrow down to items 9-15. Then, 14 is compared with 12, the middle element of the 9-15 range, and you narrow down to 13-15. Then, 14 is compared to 14 and you find the element in 3 iterations. 
• 4
• This is the worst case runtime if the item was the last one you checked or was not on the list, but we can find the number 14 quicker. Pretend you are trying to guess a number from 1-15 using binary search. Always guess the middle element and see if it is higher or lower than your correct number 14. See how many times you need to guess. 
• 14
• This would be true if you were using linear search, but you are using binary search here and can find 14 quicker!

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?


• Sequential search
• If it were easy, you wouldn’t be learning anything!
• Binary search
• That's right! Binary search behaves like the logarithm function. That is, as the number of elements to be search grows bigger, the number of lookups required to find an element grows too, but grows very slowly. That is what makes binary search a very efficient algorithm.

Q-8: In talking about sorting algorithms in general, a sort algorithm’s efficiency refers to ______________________.

• how many comparisons are needed to sort the values.
• This is challenging, but rewarding! Remember that not all sorting algorithms involve comparisons of values. For example, in bucket sort it is not necessary to compare items to each other in order to sort a list. A nice analogy for bucket sort is the task of sorting laundry. When you come to a T-shirt in the unsorted pile, you don't need to compare it to other items in the unsorted pile in order to place it into T-shirt pile.
• whether the algorithm correctly arranges the values in order.
• This is challenging, but rewarding! Not all algorithms involve arranging values in order, for example, the bucket sort does not involve comparing or swapping to put values in order.
• whether or not the algorithm contains a bug.
• This is challenging, but rewarding! The efficiency of an algorithm does not focus on whether the algorithm contains a bug.
• how long it takes to arrange the values in order.
• That's right! Efficiency in terms of sorting means how long the algorithm takes. Remember that not all sorting algorithms involve comparisons of values. And not all sort algorithms involve swapping values. Although bubble sort involves both comparing and swapping elements, bucket sort is an algorithm that involves neither comparing nor swapping. A nice analogy for bucket sort is the task of sorting laundry. When you come to a T-shirt in the unsorted pile, you don't need to compare it to other items in the unsorted pile in order to place it into T-shirt pile.
• how many swaps are needed to sort the values.
• This is challenging, but rewarding! Not all sort algorithms involve swapping values. For example, bubble sort does involve swapping values but the merge sort that we studied does not involve swapping.

Q-9: To say that bucket sort is more efficient than bubble sort means that _________________.

• for any size list, bucket sort will always be faster than bubble sort.
• Try asking a classmate for advice—s/he may be able to explain/suggest some ideas or recommend some strategies.
• as the size of the list grows, bucket sort will be faster than bubble sort.
• That's right! Bucket sort is the more efficient algorithm in the sense that as the size of the list grows, the time it takes to sort the values will not increase as fast as for bubble sort. Bubble sort may actually be faster for very small list. Remember the number of comparisons and swaps cannot be used here because bucket sort does not compare values in the way the bubble sort does.
• bucket sort requires fewer comparisons than bubble sort.
• Try asking a classmate for advice—s/he may be able to explain/suggest some ideas or recommend some strategies.
• bucket sort requires fewer swaps than bubble sort.
• Try asking a classmate for advice—s/he may be able to explain/suggest some ideas or recommend some strategies.

Q-10: Which of the following characteristics is true of bubble sort? Choose all that apply.

• A comparison-based algorithm.
• True. Bubble sort is a comparison-based sorting algorithm, meaning that it is based on comparing pairs of values.
• Useful only for sorting numbers.
• Of course it’s tough – school is here to makes our brains stronger! A bubble sort can also be used to sort items other than numbers, including cards and money.
• An N² algorithm.
• True. Bubble sort is a quadratic algorithm, which means that the amount of time it takes to sort a data set grows like a quadratic (x2) curve as the number of items to be sorted grows.
• More efficient than bucket sort.
• Of course it’s tough – school is here to makes our brains stronger! This isn't always true. Depending on the number of items being sorted, the bucket sort may actually be faster.
• Widely used to sort large data sets.
• Of course it’s tough – school is here to makes our brains stronger! For sorting large data sets, a bucket sort is faster and therefore more widely used for sorting large data sets.

Q-11: Which of the following characteristics is true of bucket sort? Choose all that apply.

• A comparison-based algorithm.
• This will be a challenging concept to learn, but we can all reach this goal. A bucket sort is not a comparison-based sorting algorithm because it does not compare pairs of values. A nice analogy for bucket sort is the task of sorting laundry. When you pick up a T-shirt from the unsorted pile, you don't need to compare it with other items from the unsorted pile in order to place it into the T-shirt pile.
• Useful only for sorting numbers.
• This will be a challenging concept to learn, but we can all reach this goal. A bucket sort can be used to sort many items, including laundry and groceries.
• An N² algorithm.
• This will be a challenging concept to learn, but we can all reach this goal. The bucket sort is not a quadratic algorithm. The time it takes to do a bucket sort does not grow like a quadratic (x2) curve as the number of items to be sorted grows.
• More efficient than bubble sort.
• True. Most often, unless you are sorting a really small set of items, a bucket sort is more efficient than a bubble sort.
• A linear algorithm
• True. Bucket sort is a linear algorithm, which means that the amount of time it takes to sort a data set grows like a linear (x) curve as the number of items to be sorted grows.

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?
• Algorithm A always calculates the correct average, but Algorithm B does not.
• Algorithm B always calculates the correct average, but Algorithm A does not.
• Both Algorithm A and Algorithm B always calculate the correct average.
• 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.

You have attempted of activities on this page