CPSC 110-08: Computing with Mobile Phones

Homework 9: Analyzing Algorithms
Due: Friday 12/2 (before class)

CS Principles

• IV C17: The student can effectively connect problems and appropriate algorithmic solutions.
• IV D18: The student can evaluate algorithms analytically and empirically.

Empirical Testing

Download the following app and install it on your phone.

	Source code: Efficiency.zip

The app allows you to create random lists of up to 100 integers ranging in value from 1 to 100.

It then provides two buttons, Sort1 and Sort2. One button uses a quadratic sorting algorithm. The other uses a linear sorting algorithm. Each algorithm reports the amount of time in milliseconds that it takes to sort the list. Your job is to figure out which is which and to document your answer.

Run at least 3 trials for each Sort using lists of size 10, 20, 30, 40, and 50 numbers. Then compute the average number of milliseconds required for each sized list. Your results should be presented in tabular form:

List Size (N)	Sort 1 Average	Sort 2 Average
10	-	-
20	-	-
30	-	-
40	-	-
50	-	-

Use the data in your table to back up your conclusion about which sort is which.

Analyzing Algorithms

Review the lecture notes on Analyzing Algorithms.

For each of the following problems, decide whether it can be solved by a linear algorithm and explain briefly why or why not.

1. Compute the sum of a list containing N random integers.

2. Determining if duplicate numbers occur in a list of N random integers.