Tutorial 4, CPSC 331, Winter 2017

home page -  news -  syllabus -  schedule -  assignments -  tutorials -  java -  references -  Mike Jacobson

Tutorial 1 -  Tutorial 2 -  Tutorial 3 -  Tutorial 4 -  Tutorial 5 -  Tutorial 6 -  Tutorial 7 -  Tutorial 8 -  Tutorial 9 -  Tutorial 10 -  Tutorial 11 -  Tutorial 12 -  Tutorial 13 -  Tutorial 14 -  Tutorial 15 -  Tutorial 16 -  Tutorial 17 -  Tutorial 18 -  Tutorial 19 -  Tutorial 20 -  Tutorial 21 -  Tutorial 22 -  Tutorial 23 -  Tutorial 24

 Analysis of Running Time of Algorithms

About This Exercises

This exercise can be used by students to make sure that they understand the basic concepts concerning the analysis of the running times of algorithms that have been discussed in class.

Students should read through this exercise, and spend time trying to solve the problems on it, before attending the fourth tutorial.

Expected Background and Preparation

As noted above, the following problems test comprehension and ability to apply material presented during the lectures on the analysis of the running times of algorithms. An additional longer example is now available online as well. Students may find it to be helpful to study this example before trying to solve the longer problem at the end of this exercise.

Warmup Exercises — To Check That You Understand the Basics

It is to be expected that all of the questions in this first section can be answered by any student who has successfully completed the prerequisites for this course, attended the lectures in which the analysis of running times of algorithms has been discussed, and carefully read through the material about this topic that is now available.

Teaching assistants will not be spending very much time in tutorials discussing these questions! Students should look at them anyway to make sure that they know how to answer them.

Students who do have difficulty with these questions should contact the course instructor to get extra help.

  1. List four kinds of resources that might be limited, and that we might therefore wish to measure when sofware is being developed or used. (One of these is “running time.”) Which of these will we be focussing on in this course?

  2. Describe two ways that we might use to measure ”running time.”

  3. Briefly describe each of the following. What are the strengths, and weaknesses of each of the first two? Under what circumstances might the third be of interest?

    1. Worst Case Analysis
    2. Average Case Analysis
    3. Best Case Analysis

  4. Recall that we introduced the notion of a “loop variant” when we studied proofs of correctness of algorithms, and saw that these were useful when we wanted to prove that algorithms halt.

    Describe how they are useful for the worst-case analysis of the running time of an algorithm as well.

  5. What is a recurrence? How is it used when one is trying to bound the worst-case running time of an algorithm?

  6. Briefly describe how to find an upper bound for the number of steps used by a program, in the worst case, if it is executed when its precondition is satisfied, in each of the following cases.

    1. The program consists of a single assignment statement or is a continue statement.
    2. The program is an if-then-else statement.
    3. The program is a while loop.
    4. The program is a sequence of two smaller programs.
    5. The program is one of the other tests or control structures provided by Java — specifically, an if-then statement, or a do-while or a for loop.
    6. The program includes a main method that calls other methods (included in the program), but recursion is not used.
    7. The program is a “simple” recursive method — it only calls itself, (at most) some fixed number of times.

  7. How can you find a lower bound for the number of steps used by a program, in the worst case, if it is executed when its precondition is satisfied?

Problem To Be Discussed in the Tutorial

The following longer problem will be discussed during the tutorial. Please try to solve it before you attend the tutorial, so that you can compare your solution (if you got one) to the solution presented by the teaching assistant, or so that you can better focus on the part of the exercise that you found to be difficult, otherwise.

  1. As part of the previous tutorial exercise, you tested and debugged a program that would be used to determine whether the entries of a given array are distinct. A corrected version of this program is given below.

    public static boolean distinctEntries ( int[] A ) { for (int i=1; i < A.length; i++ ) { /* * Loop Invariant: * a) i is an integer such that 1 <= i < A.length * b) A[r] is not equal to A[s] for all integers r * and s such that 0 <= r < s < i * Loop Variant: A.length − i */ for (int j=0; j < i; j++ ) { /* * Loop Invariant: * a) i and j are integers such that * 0 <= j < i < A.length * b) A[r] is not equal to A[s] for all * integers r and s such that * 0 <= r < s < i * c) A[r] is not equal to A[i] for every * integer r such that * 0 <= r < j * Loop Variant: i−j */ if (A[j] == A[i]) { return false; }; }; }; return true; }

    1. Analyze the worst case running time of this program.

    2. Try to analyze the best case running time of this program.

    3. What, if anything, can be said about the average (or “expected”) running time of this program, based on what you have discovered?

Last updated:
http://www.cpsc.ucalgary.ca/~jacobs/Courses/cpsc331/W17/tutorials/tutorial4.html