91Ó°ÊÓ

Describe an algorithm that produces the maximum, median, mean, and minimum of a set of three integers. (The median of a set of integers is the middle element in the list when these integers are listed in order of increasing size. The mean of a set of integers is the sum of the integers divided by the number of integers in the set.)

Describe an algorithm for finding both the largest and the smallest integers in a finite sequence of integers.

The ternary search algorithm locates an element in a list of increasing integers by successively splitting the list into three sublists of equal (or as close to equal as possible) size, and restricting the search to the appropriate piece. Specify the steps of this algorithm.

Specify the steps of an algorithm that locates an element in a list of increasing integers by successively splitting the list into four sublists of equal (or as close to equal as possible) size, and restricting the search to the appropriate piece.

Two strings are anagrams if each can be formed from the other string by rearranging its characters. Devise an algorithm to determine whether two strings are anagrams a) by first finding the frequency of each character that appears in the strings. b) by first sorting the characters in both strings.

Show that \(f(x)\) is \(\Theta(g(x))\) if and only if \(f(x)\) is \(O(g(x))\) and \(g(x)\) is \(O(f(x))\)

Show that if \(f(x)\) and \(g(x)\) are functions from the set of real numbers to the set of real numbers, then \(f(x)\) is \(O(g(x))\) if and only if \(g(x)\) is \(\Omega(f(x)) .\)

Given \(n\) real numbers \(x_{1}, x_{2}, \ldots, x_{n},\) find the two that are closest together by a) a brute force algorithm that finds the distance between every pair of these numbers. b) sorting the numbers and computing the least number of distances needed to solve the problem.

Explain what it means for a function to be \(\Omega(1)\)

Show that the greedy algorithm for making change for \(n\) cents using quarters, dimes, nickels, and pennies has \(O(n)\) complexity measured in terms of comparisons needed.