Analyzing Algorithms¶
Time Estimate: 90 minutes
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
Language Objectives: I will be able to

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.
 

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.
 

Summary¶
In this lesson, you learned how to:
SelfCheck¶
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 
Q3: 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.
blankQ4: 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.
blank 2
 No, try again. Pretend you are trying to guess a number from 115 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 915. Then, 14 is compared with 12, the middle element of the 915 range, and you narrow down to 1315. 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 115 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!
Q5: 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?
Q6: 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 1500, 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.
 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.
Q7: The function shown in this graph is known as the base2 logarithm function, y = log2(x). Which search algorithm behaves like this function?
 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 Tshirt in the unsorted pile, you don't need to compare it to other items in the unsorted pile in order to place it into Tshirt 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 Tshirt in the unsorted pile, you don't need to compare it to other items in the unsorted pile in order to place it into Tshirt 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.
Q8: In talking about sorting algorithms in general, a sort algorithm’s efficiency refers to ______________________.
 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.
Q9: To say that bucket sort is more efficient than bubble sort means that _________________.
 A comparisonbased algorithm.
 True. Bubble sort is a comparisonbased 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^{2} 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.
Q10: Which of the following characteristics is true of bubble sort? Choose all that apply.
 A comparisonbased algorithm.
 This will be a challenging concept to learn, but we can all reach this goal. A bucket sort is not a comparisonbased 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 Tshirt 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 Tshirt 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^{2} 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.
Q11: Which of the following characteristics is true of bucket sort? Choose all that apply.
Sample AP CSP Exam Question¶
 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.
Q12: There are 32 students standing in a classroom. Two different algorithms are given for findingthe average height of the students.
Algorithm AStep 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?
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.