| home page - news - syllabus - schedule - assignments - tutorials - tests - 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 |
| Analysis of Running Time of Algorithms |
This exercise is based on material presented during the lectures on Wednesday, September 17 and Friday, September 19.
The objective of this exercise is to give you practice in bounding the running times of algorithms using the techniques that have been described in class.
A question at the end of the exercise, that you should be able to complete independently, is intended to help you to familiarize yourself with a Java tool that can be used to time the execution of (parts of) Java programs.
Please read through and try to solve the problems on this exercise (including the last one, if time permits) before attending the tutorials on Wednesday, September 24.
Consider the following “Bubble Sort” algorithm. This should receive an input array A with length n as input. It reorders the elements of the input array, sorting them in increasing order. A version of this algorithm (which might be presented slightly differently) will be studied later on in this course.
for i from 0 to n−2 do j := n-1 while j > i do if A[j] < A[j−1] then temp := A[j] A[j] := A[j−1] A[j−1] := temp end if j := j−1 end do end do
The algorithm ensures that the first j elements of A are sorted, and are all less than or equal to the last n−j elements, after the outer loop has been executed j times.
Use the techniques that were discussed in class to find an upper bound for the worst-case running time of this algorithm when it is run on an input of size n. Use the length of the array as the definition of “input size” when you analyze this algorithm.
The following fact might be useful as you answer this and the next part of this question: If i is a positive integer then the sum of the first i positive integers is i(i+1)/2. This is greater than i2/2 and it is less than or equal to i2.
Try to find a lower bound for the best-case running time of this algorithm as well.
What, if anything, can you deduce about the expected running time (that is, the average-case running time) of this algorithm, based on the results of the first parts of this question?
Try to identify the assertions (about what is expected just before each line of pseudocode is executed, etc.) that would be used in a proof of correctness of the above algorithm — given a pre-condition asserting that the program’s input is of the expected type, and given a post-condition that the input array has been sorted on termination.
Consider the gcd algorithm and program that has been considered in the last few exercises. Recall that this includes includes a loop in which the values of two integers, p and q, are modified.
One way to prove termination of the loop is to consider a loop variant f(p, q) whose values is q if p ≥ q and whose values is q+1 otherwise.
Recall that, when an algorithm’s input consists of a constant number of integers, the sum of either the number of bits used in the binary representations of the absolute values of these integers, or the number of digits used in decimal representations of these values, can be used as the “input size;” each of these is a linear function of the other.
What kind of bound on the running of the algorithm can be obtained, as a function of the size of the input, if the above loop variant is used? Is this bound very useful?
Suppose, instead, that we define f(p, q) to the sum of the number of bits in a binary representation of p and the number of bits in a binary representation of q, when p ≥ q, and where we define the number of bits in a binary representation of 0 to be 0. The value of the function should be extended to include the case p < q as in previous exercises.
Show that an execution of the loop body decreases the value of this function by at least one, in each of the following three cases — a different argument will be needed for each.
p is less than q. Note that this is only possible during the first execution of the loop body.
p is greater than or equal to q, and the length of the binary representation of p is the same as the length of the binary representation of q. (Notice that the remainder obtained when dividing p by q in this case is p − q; how large can the length of the binary representation of this remainder be?)
p is greater than or equal to q and the length of the binary representation of p is strictly greater than the length of the binary representation of q.
Use the above to show that this function, f(p, q), could be used as a loop variant as well. What kind of bound on the worst-case running time of the algorithm is obtained using this loop invariant, instead of the one that was described in the first part of this question?
If “arbitrarily large” integers are being supplied as input to a program (and functions that support extended-precision integer arithmetic are being used) then it is not realistic to assume that integer arithmetic has unit cost.
Suppose that integer addition and subtraction has cost that is linear in the sizes of the input integers in the worst case, and multiplication and division with remainder have quadratic cost (ie, cost linear in m2 for input size m).
What kind of a bound on worst-case running time could be obtained for the gcd algorithm, if these charges for integer arithmetic are used?
This problem is to be solved independently by students when time permits. Read the information about the Java profiler JRat that is available on the course web page.
Write a Java program that implements the “Bubble Sort” algorithm that is discussed in the first question on this exercise.
Using the above profiler to monitor execution times, run this program on a sequence of arrays of various sizes, measuring the time used by your program when it is run on each input. Is the information that you have obtained using the profiler consistent with the analysis you performed at the beginning of this exercise?
If you do not have time to implement “Bubble Sort” then you should run the profiler with a version of the gcd program that that has been considered in the last few exercises. If you use Java’s long data type to represent integers then you should be able to use integer inputs whose size is large enough to produce some meaningful and interesting results.
Finally, try to measure the number of statements executed by your programs without using a profiler, by adding instructions that keep track of this. Is the information you obtain this way consistent with information about running times that you have already obtained?
|
This page last modified:
http://www.cpsc.ucalgary.ca/~jacobs/cpsc331/F08/tutorials/tutorial4.html |