Problem 1
What is the difference between searching and sorting?
Problem 1
Modify the selection sort algorithm to sort a list of integers in descending order.
Problem 2
Write a program that automatically generates the table of sample run times for the selection sort algorithm. The program should ask for the smallest and largest value of \(\mathrm{n}\) and the number of measurements and then make all sample runs.
Problem 2
Checking against off-by-one errors. When programming the selection sort algorithm of Section 12.1, a programmer must make the usual choices of < versus \&s, 1en(values) versus len(values) \(-1\), and from versus fron + 1. This is fertile ground for off-by-one errors. Conduct code walkthroughs of the algorithm with lists of length \(0,1,2\), and 3 and check carefully that all index values are correct.
Problem 3
For the following expressions, what is the order of the growth of each? a. \(n^{2}+2 n+1\) b. \(n^{10}+9 n^{9}+20 n^{8}+145 n^{7}\) c. \((n+1)^{4}\) d. \(\left(n^{2}+n\right)^{2}\) e. \(n+0.001 n^{3}\)g. \(n+\log (n)\) h. \(n^{2}+n \log (n)\) i. \(2^{n}+n^{2}\) j. \(\frac{n^{3}+2 n}{n^{2}+0.75}\)
Problem 3
Modify the merge sort algorithm to sort a list in descending order.
Problem 4
We determined that the actual number of visits in the selection sort algorithm is $$ T(n)=\frac{1}{2} n^{2}+\frac{5}{2} n-3 $$ We characterized this function as having \(O\left(n^{2}\right)\) growth. Compute the actual ratios $$ \begin{aligned} &T(2,000) / T(1,000) \\ &T(4,000) / T(1,000) \\ &T(10,000) / T(1,000) \end{aligned} $$ and compare them with $$ \begin{aligned} &f(2,000) / f(1,000) \\ &f(4,000) / f(1,000) \\ &f(10,000) / f(1,000) \end{aligned} $$ where \(f(n)=n^{2}\)
Problem 5
Sort the following growth rates from slowest to fastest growth. \(\begin{array}{ll}O(n) & O(n \log (n)) \\ O\left(n^{3}\right) & O\left(2^{n}\right) \\ O\left(n^{n}\right) & O(\sqrt{n}) \\ O(\log (n)) & O(n \sqrt{n}) \\ O\left(n^{2} \log (n)\right) & O\left(n^{\log (n)}\right)\end{array}\)
Problem 6
Suppose algorithm \(A\) takes five seconds to handle a data set of 1,000 records. If the algorithm \(A\) is an \(O(n)\) algorithm, approximately how long will it take to handle a data set of 2,000 records? Of 10,000 records?
Problem 8
What is the growth rate of the standard algorithm to find the minimum value of a list? Of finding both the minimum and the maximum?
