Sub Menu contents

Unit 5

Algorithms & Procedural Abstraction

5.1 Unit Overview

5.2 Logo Part 2 (Skip)

5.3 Search Algorithms

5.4 Sorting Algorithms

5.5 The Pong Game

5.6 Debugging Pong

5.7 Analyzing Algorithms

5.8 Limits of Algorithms

5.9BB Web Searches

5.10 Wrap Up

QR Code for Search Experiment App




QR Code for Sort Experiment App


Analyzing Algorithms

In this lesson we are going to use an App Inventor app to experiment with and 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?.

Unit Objectives


Analyzing Search Algorithms

In this activity you are going to use an App Inventor app to experiment with and analyze the Binary and Sequential search algorithms.

  1. Use the Search Experiment QR Code to the right to download the Search Experiment app. If it states that it is unable to locate the server, just click on the link for the college and it will start the download. The download may take up to two minutes, and it may appear as if the tablet is not downloading. Please be patient. Additionally, note that when you run the app, it may initially display a blank or black screen while it is initializing data. This may take one minute to initialize, please be patient.
  2. 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.
  3. Test each search algorithm on lists of size 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000 90000 and 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".
  4. Create a table on your portfolio and write the search time in milliseconds (ms) for each test case. You should have a total of 20 test cases, 10 for each algorithm [Search 1, and 2] at n=1000, n= 2000, n=3000, n=4000, n=5000, n=6000, n=7000, n=8000, n=9000 and n=10,000.
  5. Use graph paper (print it from online) or a spreadsheet to record and graph your results. Take a picture of your graph (if on paper) and upload it to your portfolio.
  6. Analyze your results to determine which algorithm is 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

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. Use the Sort Experiment QR Code to the right to download the Sort Experiment app. If it states that it is unable to locate the server, just click on the link for the college and it will start the download. The download may take up to two minutes, and it may appear as if the tablet is not downloading. Please be patient.
  2. Test each sort algorithm on lists of size 10, 20, 30, 40, 50, 60, 70, 80 , 90 and 100 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".
  3. Create a table on your portfolio and write the search time in milliseconds (ms) for each test case. You should have a total of 30 test cases, 10 for each algorithm [Sort 1, 2 and 3] at n=10, n= 20, n=30, n=40, n=50, n=60, n=70, n=80, n=90 and n=100.
  4. Use graph paper (print it from online) or a spreadsheet to record and graph your results. Take a picture of your graph (if on paper) and upload it to your portfolio.
  5. Analyze your results to determine which algorithm Which is the bubble sort, and which is the merge sort, 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.

    Make sure that you do the Self-check at this link. Also, make sure that you do the Google Site for 5.7