Problem 1
a. Use Gauss's approach to find the following sum: $$ 2+4+6+\ldots+100 $$ b. Use Gauss's approach to find a formula for the sum of the even numbers from 2 to \(2 n\) : $$ 2+4+6+\ldots+2 n $$ Your formula will be an expression involving \(n\).
Problem 2
An English Christmas carol, "The Twelve Days of Christmas, " dates from the late \(1700 \mathrm{~s}\). The 12 verses in the song are cumulative, each verse adding an additional gift given by "my true love." The twelfth verse says "On the twelfth day of Christmas, my true love gave to me ..." 12 Drummers Drumming 11 Pipers Piping 10 Lords-a-Leaping \(\ldots\) and so forth down to ... 3 French Hens 2 Turtle Doves And a Partridge in a Pear Tree. a. Use Gauss's formula to find the total number of gifts given on Day 12 . b. How many total gifts are given over all 12 days? Hint: $$ 1(2)+2(3)+3(4)+\ldots+n(n+1)=\frac{n(n+1)(n+2)}{3} $$
Problem 4
A tennis tournarnsnt has 342 players. A singlo match imolves 2 players. The winner of a match will play the winner of a match in the next round, wheress losers are eliminated from the toumament. The 2 players who have won all previous rounds play in the final game, and the wirner wins the tournament. What is the total number of matches needed to determine the winner? a. Here is one algorithm to answer this question. Compute \(342 / 2=171\) to get the number of pairs (matches) in the first round, which results in 171 winners to go on to the second round. Compute \(171 / 2=85\) with 1 left over, which results in 85 matches in the second round and 85 winners, plus the 1 left over, to go on to the third round. For the third round compute \(86 / 2=43,50\) the third round has 43 matches, and so on. The total number of matches is \(171+85+43+\ldots\) Finish this process to find the total number of matches. b. Here is another algorithm to solve this problem, Each match results in exactly one loser, so there must be the same number of matches as losers in the tournament. Compute the total number of losers in the entire tournament. (Hint: This isf't really a computation; it is a one-sentence argument.) c. What is your opinion on the relative clarity, elegance, and efficiency of the two algorithms?
Problem 6
Here is a list of seven names: Sherman, Jane, Ted, Elise, Raul, Maki, John Search this list for each name in turn, using sequential soserch and courting the number of comparisons for each name. Now take the seven comparison counts and find their average. Did you get a number that you expected? Why?
Problem 7
The American Museum of Natural History in New York City contains more than 32 million specimens and artifacts in its warious collections, including the world's langest collection of dinosaur fossils. Many of these are in storage away from public view, but all must be carefully inventoried. a. Suppose the inventory is unordered (I) and a sequential search is done to locate a specific artifact. Given that the search is executed on a computer that can clo 12,000 comparisons per second, about how much time on the aNerage would the search require? b. Assuming the inventory is sorted, about how much time would a binary search require?
Problem 8
In the Flipping Pancakes box, the original algorithm given requires at most \(2 n-3\) flips in the worst case. The claim is made that the new algorithm, which requires at most \(15 n+5] / 3\) flipa, is a better algorithm. How many pancalces do you need to hawe betore the second algorithm is indeed faster? Use a calculator or spreadsheet.]
Problem 9
Perform a selection sort on the list 7, 4, 2, 9, 6. Show the list after each exchange that has an effect on the list orclering.
Problem 10
The selection sort algorithm could be modified to stop when the unscrted section of the list contains only one number, because that one number must be in the correct position. Show that this modification wrould have no effect on the number of comparisons required to sort an neelement list.
Problem 11
For each of the following lists, perform a bubble sort, and show the list after each exchange. Compare the number of exchanges done here and in the Prectice Problem at the end of Soction \(3.33\). a. \(4,8,2,6\) b. \(12,3,6,8,2,5,7\) c. D, B, G, F, A, C, E, H
Problem 12
Explain why the bubble sort algorithm does \(\Theta\left(n^{2}\right)\) comparisons on an n-element list.
