Question 1: Consider the problem of finding both the maximum and the minimum. We

Question

Question 1:

Consider the problem of finding both the maximum and the minimum. We will show that you can not find them both in less than (about) 3n/2 comparisons. Consider the run of any algorithm and defined the following sets that depend on the comparison the algorithm chose. Let N be the collection of numbers. We denote n=|N|. After comparisons were done, let N' be the items not compared yet and let n'=|N'|. Let W be all numbers that always were larger when compared (always”won”) in all the comparisons, and let its size be w. Let L be the set of numbers who always ”lost” (where always smaller) when compared and lets its size be L'. Let B be the set of those who both lost least once and won at least once and let b =|B'|. Note that for any algorithm at any time n=n+b+w+L since these sets are disjoint.

1.) Recall that n=|N|, w=|W|, l`=|L|, and consider 3n+ 2w+ 2l`. Show that this term before the algorithm starts is 3n and when the algorithm ends its 4.

2.) Show that the number of comparisons needed to find the maximum and the minimum in the worst case (only using comparisons) is at least [(3n4)/2].

Explanation / Answer

Graph the following expressions. For each expression, state for which values of n that expression is the most efficient. For the following functions: 4n 2 log3 n 3 n 20n 2 log2 n n 2/3 (a) Graph all seven functions on a single plot. 1 (b) Partition the integers n 1 into groups such that all the integers in a group have the same function which yields the smallest values of f(n). (c) Partition the integers n 1 into groups such that all the integers in a group have the same function which yields the largest values of f(n). (d) Arrange the expressions by asymptotic growth rate from slowest to fastest. 2. Show that for any real constants a and b, b > 0, (n + a) b = (n b ) (*) 3. (a) Is 2 n+1 = O(2n )? (b) Is 2 2n = O(2n )? (*) 4. For each of the following, compute how large a problem instance do you need before algorithm A is faster than algorithm B. How much time do the algorithms take on that instance? (a) Algorithm A takes n 2 days to solve a problem of size n. Algorithm B takes n 3 seconds on the same problem. (b) Algorithm A takes n 2 days to solve a problem of size n. Algorithm B takes 2 n seconds on the same problem. 5. Let P be a problem. The worst-case time complexity of P is O(n 2 ). The worstcase time complexity of P is also (n lg n). Let A be an algorithm that solves P. Which subset of the following statements are consistent with this information about the complexity of P? • A has worst-case time complexity O(n 2 ). • A has worst-case time complexity O(n 3/2 ). • A has worst-case time complexity O(n). • A has worst-case time complexity (n 2 ). • A has worst-case time complexity (n 3 ). 6. For each of the following pairs of functions, either f(n) is in O(g(n)), f(n) is in (g(n)), or f(n) = (g(n)). Determine which relationship is correct and briefly explain why. (a) f(n) = log n 2 ; g(n) = log n + 5 (b) f(n) = n; g(n) = log n 2

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.