Engr 691-13: Special Topics on Analysis of Algorithms
Jackson Computer Engineering & Telecommunications Program
Spring Semester 1997

Assignment #3
Due Thursday, 27 February

Note: I changed the due date to 27 February from 20 February.

This assignment consists of a few problems Dr. Wilkins and I decided would fit in with her lecture on 30 January and my planned lecture on 13 February. The problems are adapted from assignments that Dr. Wilkins has given previously.

Note: The symbol ^ is used to mean exponentiation. Below all logarithms ("log") are base 2 unless otherwise noted. (The Brassard and Bratley textbook uses "lg" for base 2 logarithms.) Natural logarithm is denoted by "ln".

1. List the functions below from lowest to highest order. If any two or more are of the same order, indicate which.

   n, 2^n, n log n, ln n, n^2, (log n)^2, n^3, n!, log log n, sqrt(n), n-n^3+7n^5, log n

2. 1. Prove that n^4 is O(2^n).

   2. Let A and B be real numbers such that 0 < A < B. Show that n^A is in O(n^B) but n^B is not in O(n^A).
3. 1. Write an algorithm to find the median of three distinct integers a, b, and c.

   2. How many comparisons does your algorithm do in the worst case? On the average?

   3. How many comparisons are necessary in the worst case to find the median of three numbers? Justify your answer.

4. A simple type of sorting algorithm runs as follows. Given a set of n elements, we start with a linked list of size zero. We repeatedly choose the next element to add to the list; to add the element, we step through the list, comparing with each element, until we reach an element greater than the new element. Determine the function f(n) such that the complexity of this algorithm is Theta(f(n)). Make the argument carefully and distinguish between the O() and Omega() portion of your argument.

5. Suppose you have two sorted arrays, A1 and A2, each of size n. Design an O(log n) algorithm to find the nth largest element of the 2n elements of A1 and A2. (Hint: Try a variation of the binary search.)

UP to ENGR 691 assignments document?