CSC 402

Winter 2015

Craig Miller

• Home
• Basic Information
• Grades and Policies
• Schedule

Weekly Notes

• Week 1
• Week 2
• Week 3
• Week 4
• Week 5
• Week 6
• Week 7
• Week 8
• Week 9
• Week 10

Assignments

• Assignment 1
• Assignment 2
• Assignment 3
• Assignment 4
• Midterm
• Assignment 5
• Assignment 6
• Assignment 7

Assignment 5
Efficiency
Submit before 11:30 PM Saturday February 28

Overview

For this assignment you will evaluate code performance both analytically and empircally.

Analysis Problems

For each of the code segments below, answer the following questions:

1. Which operation (e.g. comparison or statement) will typically be executed more than any operation?
2. For input size n, how many times will this statement be executed?
3. What is the time performance class (see p. 187 for options) of this code segment?

Code segment A

   for (int i = 0; i < n; i += 2)
      sum++;

Code segment B

   for (int i = 0; i < n; i++)
      for (int j = 0; j < n * n; j++)
         sum++;

Code segment C

   for (int i = 0; i < n; i++)
      for (int j = 0; j < i; j++)
         sum++;

Example analysis

Here is an example analysis of a similar code fragment:

   for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
         for (int k = 0; k < 3; k++)
            sum++;

1. "sum++" is repeated most frequently
2. We work the analysis starting from the innermost loop
   • "sum++" is executed 3 times for the k-loop
   • which is then executed 3*n for the j-loop
   • which is then executed 3*n*n for the i-loop
   • 3n^2 overall
3. the segment has a quadratic time complexity, also written as O(n^2)

Empirical study

Choose a problem that has at least two algorithms with difference performance classes. Possible problems include:

• Append an item to the end of a linked list (with and without an end reference)
• Adding an item to an array (at the beginning vs. at the end)
• Sort an array of strings (e.g. Selection sort in package 2.1 vs. Merge sort in package 2.2)
• Find median of integers (use sort vs. linear algorithm)

You may consider other problems, just not one using binary search since we will discuss that in class.

Run experiments for your problem using the two algorithms. Your study should do the following:

• Collect times for both algorithms with different input sizes (e.g. array sizes)
• Test with reasonably representative input
• Show a graph of performances at different sizes
• Describe your process and explain the findings
• Compare the empirical findings to that predicted by theoretical analysis
• Produce practical advice on when the two approaches could be used

Realistically, your report will be about a page in length and include a graph. Make sure that the graph is fully explained with text.

Submission

Submit your answers and report as one document, preferably as a PDF file, to D2L.