5.7. Analyzing Algorithms

Time Estimate: 90 minutes

5.7.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.7.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. (slides)

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.
  1. Create a portfolio page named Search Experiment.
  2. 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.

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  1. Create a portfolio page named Sort Experiment.
  2. 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.
  1. 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.
  2. 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.
  3. 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.7.3. Summary

In this lesson, you learned how to:

5.7.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

5.7.5. Sample AP CSP Exam Question

5.7.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